TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.1, Jan
uary 20
14
, pp. 771 ~
777
DOI: http://dx.doi.org/10.11591/telkomni
ka.v12i1.3071
771
Re
cei
v
ed Ma
y 1, 2013; Re
vised July 1
8
, 2013; Accept
ed Augu
st 28
, 2013
Analysis of Brownian Particles for Finding the Shortest
Path in Networks
Bin Hu
1,2
, Jia-li Xu
2
, Huan-
y
an Qian*
,1
1
School of Co
mputer Scie
nc
e and T
e
chno
l
o
g
y
, Nan
jin
g U
n
iversit
y
of Sci
ence a
nd T
e
chnol
og
y,
Xi
ao
lin
g
w
e
i
20
0, Nanj
ing, Ch
i
na, 210
00
0
2
Colle
ge of Info
rmation Sci
enc
e and T
e
chno
l
o
g
y
, Nan
jin
g A
g
ricult
ural U
n
iv
ersit
y
,Na
n
j
i
ng,
W
e
iga
ng 1, Na
njin
g, Chi
na, 2
100
95
*Corres
p
o
ndi
n
g
author, e-ma
i
l
:h
yqi
an@
njust
.
edu.cn
A
b
st
r
a
ct
In this pa
per, w
e
propos
e a
meth
od to
ana
ly
z
e
the sh
orte
st path findi
ng
betw
een tw
o nod
es
i
n
compl
e
x n
e
tw
orks. In this
method, w
e
first
find th
at
sin
g
l
e
Brow
ni
an
pa
rticle fol
l
ow
s the sh
ortest p
a
th
betw
een so
urc
e
no
de
i
and d
e
stinati
on n
o
d
e
j
in the
prob
a
b
ility of
1
1
[(
)
(
)
]
ij
i
j
n
dd
ia
a
Bj
Bj
w
here
ij
d
denot
es the s
hortest path st
eps betw
e
e
n
tw
o nodes. T
o
be co
mp
are
d
w
i
th single
par
ticle util
i
z
a
t
io
n,
then w
e
s
peci
a
lly
an
aly
z
e
t
h
e
multi
p
le
p
a
rticles. W
e
co
mpute th
e pr
ob
a
b
ility
of
m
particl
es
’
taki
ng t
h
e
shortest path
b
e
tw
een
i
and
j
w
hen
s
particl
es
starts simult
a
neo
usly fro
m
the so
urce a
nd
hea
d to the
destin
a
tio
n
as
1
11
{
(
)
}
(
[
()
()
])
(
(
()
)
)
ij
ij
i
j
nn
dd
d
mm
s
m
ij
s
i
a
i
a
aa
PS
s
t
C
B
j
B
j
B
j
. It
’
s
very clear
that there
mus
t
be particl
es takin
g
t
he sh
ortest path to ar
rive at the d
e
s
t
inatio
n in th
e mu
ltipl
e
partic
l
es
envir
on
me
nt. And w
i
th the nu
mb
er of
m
incre
a
s
ing, the arriv
i
ng pro
b
a
b
il
ity first arise and th
en dro
p
dow
n
rapi
dly unti
l
to z
e
r
o
. In the en
d, w
e
make th
e exper
i
m
ents
and co
nfir
m ou
r theoretic
a
l
an
alysis. Our results
w
ould
provi
d
e
valu
abl
e
usag
e
for so
me a
ppl
i
c
ations
such
a
s
find
ing
the
o
p
timal r
outi
ng
i
n
w
i
rel
e
ss se
n
s
or
networks.
Ke
y
w
ords
: sh
ortest path; Brow
nian p
a
rticl
e
; netw
o
rks
Copy
right
©
2014 In
stitu
t
e o
f
Ad
van
ced
En
g
i
n
eerin
g and
Scien
ce. All
rig
h
t
s reser
ve
d
.
1. Introduc
tion
Network searchi
ng play
s an important role
in data exchange, resource
utilization,
informatio
n
share
an
d
so
on
whi
c
h m
a
ke
s the
meth
od of fin
d
ing
the
sho
r
test
p
a
th be
com
e
a
key
r
e
sear
ch ar
ea in c
o
mplex networks
[1, 2].
At present th
e sh
orte
st pa
th finding st
rat
egie
s
in co
mplex networks
are
usuall
y
base
d
on pa
ssing
p
a
ckets. T
he p
a
ckets
are ini
t
iated fr
om th
e so
urce
nod
e and
pa
ssed
its’ neig
hbo
rs.
Such p
r
o
c
e
s
s are re
peate
d
until t
hese packet
s
arrive at the desti
nation no
de.
So the sho
r
t
e
st
path ha
s be
e
n
found at th
e sam
e
time. Inspired by
this ide
a
, there are th
ree m
a
in strategie
s
of
finding th
e
sh
ortest
path
b
e
twee
n n
ode
s in
net
wo
rks. The
s
e
s
a
r
e
the Bre
a
k First Sea
r
ch
(BFS)
[3], the Rand
om Wal
k
(RW) [4] and
so
me local se
arch meth
od
s that utilize hig
h
deg
ree n
o
d
e
s.
Among th
em,
BFS ha
s
hi
gh a
c
cu
racy,
but i
s
ha
s
high
flux of
i
nquiri
ng data
pa
ckets on
th
e
netwo
rk [5],
whi
c
h
ha
s g
r
eat imp
a
ct
o
n
the
utiliz
ati
on of
network
re
sou
r
ces.
Although
the
local
sea
r
ch meth
ods
can
red
u
c
e the flux of inquirin
g
pa
ckets, the a
ccura
cy of them mainly dep
end
on the net
wo
rk top
o
logy. RW i
s
an im
p
o
rtant proc
ess in complex
netwo
rks.
In rece
nt years RW
attract
s
extensive attentio
n. First pa
ssage time is
t
he ch
aracte
ri
stic of RW a
nd often u
s
e
d
to
solve the
sh
ortest
path fi
nding
pro
b
le
m [6, 7, 8,
9, 10, 11, 1
2
]. But most
of them a
r
e
just
con
s
tru
c
ted o
n
the basi
s
of
single Brown
i
an parti
cle.
In this passage, besides t
he si
ngle B
r
owni
an particle utiliz
ation, we
will al
so
use the
multiple Brownian
parti
cle
s
to an
alyze
th
e p
r
oble
m
of
sho
r
test
path
finding. By
a
nalyzin
g
singl
e
particl
e’s ran
dom
wal
k
ing,
we
find
that
this pa
rticle
follows the
shorte
st p
a
th
betwe
en
so
u
r
ce
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 2302-4046
TELKOM
NIKA
Vol. 12, No
. 1, Janua
ry 2014: 771 – 7
7
1
772
node
i
and destin
a
tion n
ode
j
in th
e
probability
of
1
1
[(
)
(
)
]
ij
i
j
n
dd
ia
a
Bj
Bj
wher
e
ij
d
denote
s
the sho
r
test path
steps bet
we
en two nod
e
s
. Unde
r this basis ,we finally dedu
ce
that
with
s
parti
cle
s
’ ran
dom
wal
k
ing
on th
e n
e
twork, the
r
e
are
m
pa
rticle
s
first a
rriv
i
ng
a
t
the targ
et
node in the p
r
oba
bility of
1
11
{
(
)
}
(
[
()
()
])
(
(
()
)
)
ij
ij
i
j
nn
dd
d
mm
s
m
ij
ij
s
i
a
i
a
aa
PS
s
d
C
B
j
B
j
B
j
.
From
the
ele
m
entary
mat
hematical
kn
owle
dge,
we
ca
n i
n
fer th
at with
s
and
0
m
,
{(
)
}
0
ij
PS
s
t
.So
w
e
ca
n
ea
s
ily c
onc
lu
de th
a
t
00
{(
)
}
1
{
(
)
}
1
ij
ij
m
i
j
i
j
m
PS
s
d
PS
s
d
. So we m
a
y con
c
lu
de
that there
must b
e
partic
l
es
tak
i
ng the s
h
ortest path to
arrives at the de
stination.[13,14
,15]
2. Rese
arch
Metho
d
2.1. Shortes
t
Path Finding of Single Bro
w
n
i
an Par
t
icle
We fi
rst
pay
attention to t
he
sho
r
test
p
a
th findin
g
of
a
singl
e Bro
w
nia
n
p
a
rticl
e
on
a
gene
ric net
work.
The
net
work
co
uld
b
e
ba
si
cally
consi
dered
as a
con
n
e
c
ted
and
un
dire
ct
ed
grap
h G(m,n) whe
r
e m de
notes the
nu
mber of
e
d
g
e
s an
d n de
notes the
nu
mber of n
o
d
e
s. If
node
i
and
j
are
con
n
e
c
te
d with at le
a
s
t one
edg
e, we let
1
ij
n
and
1
ji
n
, otherwise
0
ij
n
and
0
ji
n
.
W
e
a
l
s
o
a
s
s
u
m
e
a
l
l
0
ii
n
.So the adjace
n
t matrix of such network i
s
expre
s
sed by
N
with all ent
ries
,,
1
,
2
,
.
.
.
ij
ni
j
n
.The vari
able
i
d
is use
d
to stand fo
r the
degree of no
de
i
and so
1
N
ii
j
j
dn
.Whe
n we sel
e
ct the node
i
as the start positio
n for o
n
e
sing
e Bro
w
ni
an Particl
e
ra
ndom wand
ering on the ne
tw
ork, it is cl
ear that the p
o
ssibility of the
particl
e’s tran
sferring to an
y neighbo
ring
node is
1
i
d
.Thu
s it’s ea
sy to see the M
a
rkov transition
matrix
P
of such netwo
rk
co
uld be calcula
t
ed as follo
w:
PN
D
(1)
w
h
er
e
11
1
1
n
nn
n
nn
N
nn
is th
e adj
acent
matrix an
d
1
1
0
1
0
0
0
n
d
D
d
is the
diago
nal matrix.
No
w let’s
ran
domly sel
e
ct
on the n
e
two
r
k
node
i
as the source
an
d nod
e
j
a
s
the
destin
a
tion. T
he pa
rticle
st
arts from the
sou
r
ce no
de
and ta
ke
ran
domized
wal
k
on the n
e
twork
to the de
stin
ation. The
ra
ndom va
riabl
e
ij
S
stan
ds for t
he nu
mbe
r
of
step
s the
pa
rticle
uses to
get to the destinatio
n no
de
j
from the sou
r
ce no
de
i
for the firs
t time. So expres
s
i
on
{}
ij
PS
t
denote
s
th
e
prob
ability th
at the pa
rticl
e
firs
t
arrives at the d
e
stin
ation at the
e
x
act
t’th step. Accordin
g to the famou
s
C-K equation, we can infer that
11
2
1
12
1
12
1
...
{
}
...
,
,
.....,
t
t
ij
i
j
t
PS
t
p
p
p
j
(2)
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Analysis of Browni
an Parti
c
les for findin
g
t
he sho
r
test
path in netwo
rks (Hua
n-ya
n Qian)
773
whe
r
e
11
2
1
,
.....,
t
ij
pp
p
are e
n
try items
of matrix
P
.To calcul
ate the
{}
ij
PS
t
,
we first int
r
od
uce
s
th
e oth
e
r
mat
r
ix
()
Bh
.
()
Bh
is
a
c
qui
red
by
si
mply ma
king
the
'
ht
h
colum
n
of matrix
P
to z
e
ro. So
12
1
1
(
)
(
,
,
...,
,
0
,
,
....,
)
hh
n
B
hp
p
p
p
p
(3)
And we can calcul
ate
{}
ij
PS
t
as
1
{}
(
(
)
)
n
t
ij
i
a
a
PS
t
B
j
(4)
In equ
ation(4
)
,
{}
ij
PS
t
denote
s
t
he p
r
ob
ability of the
sin
g
le
parti
cle fi
rst
rea
c
hin
g
node
j
after se
tting out from node
i
beyond
t steps. Then
we ca
n ea
sil
y
infer that
{}
{
1
)
(
)
ij
i
j
i
j
PS
t
P
S
t
P
S
t
(5)
Acco
rdi
ng
to the
ba
sic kn
owle
dge of
p
r
oba
b
ility theory, the me
a
n
first
rea
c
hi
ng ste
p
s
ij
X
can be
cal
c
ul
ated by
00
0
()
(
(
1
)
(
)
)
(
1
)
(
2)
....
(
)
ij
i
j
ij
i
j
tt
ij
i
j
i
j
t
X
tP
S
t
t
P
S
t
P
S
t
PS
PS
PS
t
(6)
And we can finally get
1
1
()
()
n
ij
i
h
h
X
I
Bj
(7)
whe
r
e
I
is the identity matrix and
1
()
I
Bj
denote
s
the inverse
operation.
2.2. Shortes
t
Path Finding of
Multiple Bro
w
nian P
a
rticles
Suppo
sing
ij
d
denote
s
the
sh
ortest
path
b
e
twee
n n
ode
i and
j, we
ca
n cl
early
se
e
that
singl
e particl
e
follows this
link in the
probability of
1
1
[(
)
(
)
]
ij
i
j
n
dd
ia
a
Bj
Bj
according
ab
ove
discu
ssi
on. B
a
se
d o
n
thi
s
, we
can fu
rther i
n
ve
stig
a
t
e the
sho
r
te
st path
probl
em of m
u
ltipl
e
Brownian p
a
rticle. Like fo
rmer de
scripti
on,
we rand
o
m
ly sele
ct on
the netwo
rk
node
i
as th
e
sou
r
ce and
n
ode
j
as the d
e
stinatio
n. All particl
es
sim
u
ltaneo
usly start from the
sou
r
ce node
and go to th
e destin
a
tion
node. Vari
a
b
le
s
stan
ds f
o
r the n
u
mbe
r
of parti
cle
s
wal
k
ing o
n
th
e
netwo
rk a
nd
variable
m
den
otes th
e
num
ber of p
a
rti
c
le
s
whi
c
h
ta
ke t
he
s
h
ortes
t
to firs
t
arrive
at
the destin
a
tio
n
node. Rand
om variabl
e
()
ij
Ss
expre
s
ses th
e step
s that
m
arrivin
g
parti
cle take
from sou
r
ce
node
i
to de
st
ination n
ode
j
.Let
b
ij
X
be the
numbe
r of
st
eps th
e b’th
Brownian
particl
e take
s to get to the
destin
a
tion fo
r the firs
t time. It’s obvious that all the particl
es’
wal
k
in
g
are ind
epe
nd
ent. So we ca
n get
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 2302-4046
TELKOM
NIKA
Vol. 12, No
. 1, Janua
ry 2014: 771 – 7
7
1
774
11
1
{
(
)
}
{
}
...
{
}
{
}
....
{
}
s
mm
s
ij
ij
i
j
ij
ij
m
P
S
s
t
P
P
X
t
P
X
t
P
PX
t
P
PX
t
(8)
Acco
rdi
ng to Eq.(4) an
d (5
),
1
11
{
(
)
}
(
(
(
)
)
)
(
[
(
)
(
)
]
)
,
0
,
1
,
2....
nn
mt
s
m
t
t
m
ij
s
i
a
i
a
aa
PS
s
t
C
B
j
B
j
B
j
m
(9)
It’s very clea
r that when
0
m
,
0
1
{(
)
}
(
(
(
)
)
)
n
ts
ij
s
i
a
a
PS
s
t
C
B
j
.With
s
,
{(
)
}
0
ij
PS
s
t
.So we
can
e
a
sily
con
c
lu
d
e
that
00
{(
)
}
1
{
(
)
}
1
ij
m
i
j
m
P
S
st
P
S
st
.
That is to say
there mu
st be particl
es a
r
rive at the destination in t steps
whe
n
s
.
We
also
ca
n
also
comp
ute
the m
ean
first rea
c
hin
g
steps of m
u
ltipl
e
Bro
w
ni
an
p
a
rticle
s
as:
00
1
()
(
(
)
)
(
(
(
)
)
)
n
ts
i
j
ij
ij
tt
a
Xs
P
S
s
t
B
j
(10
)
3. Results a
nd Analy
s
is
As a
ch
eck o
f
our
analysi
s
above,
we p
e
rfor
m
ed t
w
o
experim
ents.
In first exp
e
riment,
we
use
a
small ra
ndo
m
tree-li
ke
mod
e
l to test th
e
sh
orte
st pat
h finding
bot
h in the
case of
singl
e Brownian parti
cle
and in the case ofmul
t
iple Browni
an parti
cles.
And in secon
d
experim
ent, we will use a
mesh-li
k
e model.
3.1. Tree-Lik
e
Net
w
o
r
k
Analy
s
is
From
mod
e
l as Figu
re 1, we ca
n see
that
the
sh
orte
st path
st
ep
s betwe
en so
urce nod
e
1 and destination node 12
are
4. So
it’s
very easy to
cal
c
ulate th
e probability
of singl
e
particl
e
’s
taking
su
ch shorte
st path is 0.033
3.
Figure 1.
T
r
e
e
-like network model
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Analysis of Browni
an Parti
c
les for findin
g
t
he sho
r
test
path in netwo
rks (Hua
n-ya
n Qian)
775
Figure 2. Single parti
cle’
s first arrivi
ng at
the destinati
on in t’th step
s
Figure 3.
Arri
ving prob
abili
ty in multiple
particl
es e
n
vironm
ent with
the numbe
r o
f
s
Figure 4. The probability of taking the sh
ortest path wi
th the increase of m
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 2302-4046
TELKOM
NIKA
Vol. 12, No
. 1, Janua
ry 2014: 771 – 7
7
1
776
3.2. Mesh-Li
ke Model
The Mesh-li
k
e model ha
s been wi
de
ly used now
adays, espe
cially in wire
less sen
s
o
r
netwo
rks. Fig
u
re 5 give
s a simple exa
m
ple.
Figure 5. Mesh-like network model
From ab
ove model, we
ca
n see that the
s
horte
st path
steps bet
we
en sou
r
ce no
de 5 and
destin
a
tion n
ode 9
are 3.
So it’s very e
a
sy to
ca
lcul
ate the p
r
ob
a
b
ility of singl
e pa
rticle’
s
ta
king
su
ch shorte
st
path is 0.05
Figure 6. Single parti
cle’
s first arriving at
the destinati
on in t’th step
s
Figure 7.
Arri
ving prob
abili
ty in multiple
particl
es e
n
vironm
ent with
the numbe
r o
f
s
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Analysis of Browni
an Parti
c
les for findin
g
t
he sho
r
test
path in netwo
rks (Hua
n-ya
n Qian)
777
Figure 8. The probability of taking the shor
test path wi
th the increase of myy
4. Conclusio
n
In this pape
r, we analyze the sho
r
test
path
finding
with the use of single an
d
multiple
Brownian p
a
rticle in detail.
From a
bove
analysi
s
, we
can
ea
sily ge
t a con
c
lu
sio
n
that there
must
be pa
rticle
s to take the
sh
ortest p
a
th in
multiple
parti
cle
s
’ usage a
nd it is more efficient than
the
singl
e parti
cl
e’s ap
plicatio
n. In our exa
m
ple, it
has
at least in
cre
a
se
d its’ findi
ng probability
as
much
as fou
r
times. In spi
t
e of this, the numb
e
r of
particl
es
whi
c
h ta
ke the
sho
r
test p
a
th
in
multiple e
n
vironment
are l
i
mited. In o
u
r
ex
p
e
rim
ent, wh
en
100
p
a
rticle
s sim
u
l
t
aneou
sly
sta
r
t
from the so
urce no
de, no
more tha
n
15
particle
s
take the sho
r
test
path.
Referen
ces
[1]
R Alb
e
rt, H Je
ong, a
nd A
L
B
a
rab
á
si. T
he Diameter
of W
o
rld W
i
de
W
eb.
Nature (
Lon
do
n). 199
9; 40
1:
130-
131.
[2]
Broder
A, Kum
a
r R, Maghou
l F
,
Raghav
an P
,
Rajago
pa
lan
S, Stata R,
T
o
mkins
A
& W
i
ener
.
Comput.
Netw
orks
. 200
0; 33: 309-
320.
[3]
SJ Yang. Expl
orin
g compl
e
x net
w
o
rks b
y
w
a
lkin
g on th
em. Ph
y
s
. Rev. E 71, 016
10
7(20
05)
[4]
DJ Watts, PS
Dodds and MEJ Ne
w
m
an. Id
e
n
tit
y
a
nd se
arc
h
in soc
i
al
net
w
o
rks.
Scienc
e
. 2002; 2
96:
302-
130
5.
[5]
Shao-P
i
ng W
a
ng, W
en-Ji
ang
Pei. F
i
rst pass
age tim
e
of mu
ltiple
Bro
w
n
i
a
n
particl
es on
n
e
t
w
o
r
ks
w
i
t
h
app
licati
ons.
P
h
ysica A
. 200
8
;
387: 469
9-47
08.
[6]
BD Hug
hes. R
and
om
w
o
rks a
nd Ra
nd
om en
vironme
n
t. Oxford: Clar
end
on
Press. 1996(2
)
.
[7]
HC Gu and D
Q
Li. Equatio
n of Mathematic
al Ph
ys
ics. Ch
i
na T
e
rtiar
y
Ed
ucatio
n pu
blic
a
t
ions, 2nd
ed.,
200
2.
[8]
MEJ Ne
w
m
an.
in Han
dbo
ok o
f
Graphs and
Net
w
or
ks. ed
ited b
y
S Bornh
o
ldt an
d HG Schuster, W
ile
y-
VCH, Berli
n
. 2003.
[9]
Ne
w
m
a
n
MEJ. "T
he structure an
d functio
n
of
comple
x
n
e
t
w
o
r
ks". SIAM Revie
w
.
45(
2): 167
–25
6.
doi:1
0.11
37/S0
036
14
450
34
24
80.
[10]
P Erdos a
nd A
Ren
y
i. On th
e
evol
ution
of ra
ndom
grap
h, Publ. Math
. Inst. Hun
g
. Acad.
Sci. 196
0; 5:
17-6
0
.
[11]
Xi
a
Xi
n, Z
hu
shu
x
i
n
. A Sur
v
e
y
on
W
e
ight
ed N
e
t
w
ork M
easur
ement
a
nd Mo
del
in
g.
TELKOMNIKA
Indon
esi
an Jou
r
nal of Electric
al Eng
i
ne
eri
n
g
.
2013; 1
1
(1): 1
81-1
86.
[12]
Y Shen. Dete
ct local comm
uniti
es in
n
e
t
w
orks
w
i
t
h
an
outsid
e
rate coefficie
n
t.
Physica A
. 2
0
13;
392(
12): 28
21-
282
9.
[13]
Y She
n
, W
J
Pei, K W
a
n
g
, T
ao Li, Sha
o
-pi
ng W
a
ng.
Recurs
ive filt
ration m
e
tho
d
for detecti
n
g
communit
y
stru
cture in net
w
o
r
ks.
Physica A
. 200
8; 387(
26): 666
3-66
70.
[14]
Z
hu sh
u
x
in,
H
u
bi
n.
H
y
b
r
id
F
eature S
e
lect
ion B
a
se
d o
n
Improved
GA
for the Intrus
io
n Det
e
ction
Sy
s
t
e
m
.
T
E
LK
OMNIKA Indon
esia
n Journ
a
l o
f
Electrical Eng
i
ne
erin
g
. 201
3; 11(4): 172
5-1
730.
Evaluation Warning : The document was created with Spire.PDF for Python.