Random Walks On Complex Networks: Department of Physics, Chungnam National University, Daejeon 305-764, Korea
Random Walks On Complex Networks: Department of Physics, Chungnam National University, Daejeon 305-764, Korea
Random Walks On Complex Networks: Department of Physics, Chungnam National University, Daejeon 305-764, Korea
j
lim
t-
P
ij
(t), i.e., the innite time limit [21].
An explicit expression for the transition probability P
ij
(t)
to go from node i to node j in t steps follows by iterating
Eq. (1)
P
ij
(t)
X
j
1
;...;j
t1
A
ij
1
K
i
A
j
1
j
2
K
j
1
A
j
t1
j
K
j
t1
: (2)
Comparing the expressions for P
ij
and P
ji
one sees im-
mediately that
K
i
P
ij
(t) K
j
P
ji
(t): (3)
This is a direct consequence of the undirectedness of the
network. For the stationary solution, Eq. (3) implies that
K
i
P
j
K
j
P
i
, and therefore one obtains
P
i
K
i
N
; (4)
with N
P
i
K
i
. Note that the stationary distribution is,
up to normalization, equal to the degree of the node i
the more links a node has to other nodes in the network,
the more often it will be visited by a random walker.
How fast is the random walk motion? To answer to this
question, we study the MFPT. The rst-passage probabil-
ity F
ij
(t) from i to j after t steps satises the relation
P
ij
(t)
t0
ij
+
X
t
t
/
0
P
jj
(t t
/
)F
ij
(t
/
): (5)
The Kronecker delta symbol insures the initial condition
P
ij
(0)
ij
[F
ij
(0) is set to zero]. Introducing the
Laplace transform
~
ff(s)
P
t0
e
st
f(t), Eq. (5) becomes
~
PP
ij
(s)
ij
+
~
FF
ij
(s)
~
PP
jj
(s), and one has
~
FF
ij
(s) j
~
PP
ij
(s)
ij
|=
~
PP
jj
(s): (6)
In nite networks the random walk is recurrent [12], so
the MFPT is given by (T
ij
)
P
t0
tF
ij
(t)
~
FF
/
ij
(0).
Since all moments R
(n)
ij
P
t0
t
n
P
ij
(t) P
j
of the
exponentially decaying relaxation part of P
ij
(t) are nite,
one can expand
~
PP
ij
as a series in s as
~
PP
ij
(s)
K
j
N(1 e
s
)
+
X
n0
(1)
n
R
(n)
ij
s
n
n!
: (7)
Inserting this series into Eq. (6) and expanding it as a
power series in s, we obtain that
(T
ij
)
(
N
K
j
; for j i
N
K
j
jR
(0)
jj
R
(0)
ij
|; for j i
: (8)
A similar expression is derived in Ref. [12] for the MFPT
of the random walk in periodic lattices.
It is very interesting to note that the average return
time (T
ii
) does not depend on the details of the global
structure of the network. It is determined only by the total
number of links and the degree of the node. Since it is
inversely proportional to the degree, the heterogeneity in
connectivity is well reected in this quantity. In a SF
network with degree distribution P(K) K
, the MFPT
to the origin T
o
also follows a power-law distribution
P(T
o
) T
(2)
o
. The MFPT to the origin distributes
uniformly in the special case with 2.
Random walk motions between two nodes are asym-
metric. The difference between (T
ij
) and (T
ji
) for i j
can be written as [using Eq. (8)]
(T
ij
) (T
ji
) N
R
(0)
jj
K
j
R
(0)
ii
K
i
R
(0)
ij
K
j
R
(0)
ji
K
i
;
where the last term vanishes due to Eq. (3). Therefore we
obtain
(T
ij
) (T
ji
) C
1
j
C
1
i
; (9)
where C
i
is dened as
C
i
P
i
; (10)
where P
i
K
i
=N and the characteristic relaxation time
i
of the node i is given by
i
R
(0)
ii
X
t0
P
ii
(t) P
i
: (11)
We call C
i
the random walk centrality since it quanties
how central a node i is located regarding its potential to
receive information randomly diffusing over the network.
To be more precise: Consider two nodes i and j with C
i
>
C
j
. Assume that each of them launches a signal simulta-
neously, which is wandering over the network. Based on
Eq. (9), one expects that the node with larger RWC will
receive the signal emitted by its partner earlier. Hence,
the RWC can be regarded as a measure for effectiveness
in communication between nodes. In a homogeneous net-
work with translational symmetry, all nodes have the
same value of the RWC. On the other hand, in a hetero-
geneous network the RWC has a distribution, which leads
to the asymmetry in the random dynamic process.
The RWC is determined by the degree K and . The
order of magnitude of the characteristic relaxation time
is related to the second largest eigenvalue (nota bene [21])
of the time evolution operator in (1): P
ii
(t) P
i
+
P
N
2
a
()
i
b
()
i
t
, where a
()
and b
()
are the left and right
P H YS I CA L R E VI E W L E T T E RS
week ending
19 MARCH 2004 VOLUME 92, NUMBER 11
118701-2 118701-2
eigenvectors, respectively, of the time evolution operator
belonging to the eigenvalue
i
a
(2)
i
b
(2)
i
t
2
and
i
- a
(2)
i
b
(2)
i
=} ln}
2
}}. Thus the relaxation time
i
has a
node dependence only through the weight factor, which is
presumably weak. On the other hand, the degree depen-
dence is explicit.
We examined the distribution of the RWC in the
Barabasi-Albert (BA) network [22]. This is a model for
a growing SF network; at each time step, a new node is
added creating m links with other nodes which are se-
lected with the probability proportional to their degree.
We grew the network, solved the master equation numeri-
cally with the initial condition P
i
(t 0)
ik
, and cal-
culated the relaxation time
k
for each k. Figure 1(a)
shows the plot of vs K in the BA network of N 10
4
nodes grown with the parameter m 2. The degree is
distributed broadly over the range 2 K & 400. On the
other hand, the relaxation time turns out to be distributed
very narrowly within the range 1 & & 2. We also
studied BA networks of different sizes, but did not nd
any signicant broadening of the distribution of . So the
RWC distribution is mainly determined by the degree
distribution. In Fig. 1(b) we show the plot of C vs K in the
same BA network. It shows that the RWC is roughly
proportional to the degree. Note, however, that the
RWC is not increasing monotonically with the degree
due to the uctuation of as seen in Fig. 1(a).
The RWC is useful when one compares the random
walk motions between two nodes, e.g., i and j with C
i
>
C
j
. On average a random walker starting at j arrives at i
before another walker starting at i arrives at j. Now
consider an intermediate node k, which may be visited
by both random walkers. Since (T
ij
) > (T
ji
), it is likely
that a random walker starting at node k will arrive at
node i earlier than at node j. Although this argument is
not exact since we neglected the time spent on the journey
to the intermediate node, it indicates that nodes with
larger RWC may be typically visited earlier than nodes
with smaller RWC by the random walker. If we interpret
the random walker as an information messenger, nodes
with larger RWC are more efcient in receiving informa-
tion than nodes with smaller RWC.
We performed numerical simulations to study the rela-
tion between the RWC and this efciency. To quantify it,
we consider a situation where initially all nodes in a
network are occupied by different random walkers. They
start to move at time t 0, and we measure n
i
, the
fraction of walkers which have passed through the node
i, as a function of time t. It is assumed that the walkers do
not interact with each other. They may be regarded as a
messenger delivering information to each node it visits.
Then, with the information distribution uniformly ini-
tially, n
i
is proportional to the amount of information
acquired by each node. The argument in the previous
paragraph suggests that typically nodes with larger val-
ues of RWC have larger value of n
i
at any given time.
The BA network [22] and the hierarchical network of
Ravasz and Barabasi [23] were considered in the simula-
tions. The hierarchical network is a deterministic network
growing via iteration; at each iteration the network is
multiplied by a factor M. The emergent network is scale
free when M 3. Since it is a deterministic network,
several structural properties are known exactly [24]. We
measured n
i
in the BA network with m 2 and N 512
nodes and in the hierarchical network with M 5 and
N 5
4
nodes for 0 t 2048, which are presented in
the left and the right column of Fig. 2, respectively. The
FIG. 1. (a) vs K and (b) C vs K calculated in the Barabasi-
Albert network with N 10 000 and m 2. The straight line
in (b) has the slope 1.
FIG. 2 (color online). Time evolution of the fraction of
walkers n that pass through a node as a function of (from
top to bottom) the node index i, the node degree K and the
RWC C of the BA network (left column) and the hierarchical
network (right column). The value of n at each time t is
represented in the gray scale/color code depicted at the right
border of each plot.
P H YS I CA L R E VI E W L E T T E RS
week ending
19 MARCH 2004 VOLUME 92, NUMBER 11
118701-3 118701-3
value of n
i
is indicated in gray scale (color code) accord-
ing to the reference shown in Fig. 2.
The time evolution of n
i
is presented in three different
ways. In the rst row, the nodes are arranged in ascending
order of the node index i. In the BA network, the node
index corresponds to the time step at which the node is
added to the network. The indexing scheme for the hier-
archical network is explained in Ref. [24]. In the second
row, the nodes are arranged in descending order of the
degree K and in the third row they are arranged in
descending order of the RWC C. At a given time t, the
plot in the rst row shows that n is nonmonotonous and
very irregular as a function of the node index. As a
function of the degree it becomes smooth, but still non-
monotonic tendencies remain. However, as a function of
the RWC, it becomes much smoother and almost monoto-
nous. We calculated for each node i the time
/
i
at which n
i
becomes greater than 1=2. In the BA network, among all
node pairs (i; j) satisfying
/
i
<
/
j
, only 3% violate the
relation C
i
> C
j
, whereas the number of pairs that violate
the relation K
i
> K
j
is 5 times larger.
In summary, we studied the random walk processes in
complex networks. We derive an exact expression for the
mean rst-passage time [see Eq. (8)]. The MFPTs be-
tween two nodes differ for the two directions in general
heterogeneous networks. We have shown that this differ-
ence is determined by the random walk centrality C
dened in Eq. (10). Among random walk motions be-
tween two nodes, the walk to the node with larger value
of C is faster than the other. Furthermore, it is argued that
in a given time interval nodes with larger values of C are
visited by more random walkers which were distributed
uniformly initially. We conrmed this by numerical simu-
lations on the BA and the hierarchical network. One may
regard the random walkers as informations diffusing
through the network. Our results imply that information
does not distribute uniformly in heterogeneous networks;
the information is centralized to nodes with larger values
of C. The nodes with high values of C have the advantage
of being aware of new information earlier than other
nodes. On the other hand, it also implies that such nodes
are heavily loaded within an information distribution or
transport process. If the network has a nite capacity, the
heavily loaded nodes may cause congestions [17]. There-
fore much care should be taken of the nodes with high C
values in network management. In the current work, we
consider the random walks on undirected networks. The
generalization to directed networks would be interesting.
And in order to study congestion, the random walk mo-
tions with many interacting random walkers would
also be interesting. We leave such generalizations to a
future work.
Acknowledgement: This work was supported by the
Deutsche Forschungsgemeinschaft (DFG) and by the
European Communitys Human Potential Programme
under Contract No. HPRN-CT-2002-00307,
DYGLAGEMEM.
[1] D. J. Watts and S. H. Strogatz, Nature (London) 393, 440
(1998).
[2] R. Albert and A.-L. Barabasi, Rev. Mod. Phys. 74, 47
(2002).
[3] S. N. Dorogovtsev and J. F. F. Mendes, Adv. Phys. 51,
1079 (2002).
[4] R. Albert, H. Jeong, and A.-L. Barabasi, Nature
(London) 401, 130 (1999).
[5] R. Albert, H. Jeong, and A.-L. Barabasi, Nature
(London) 406, 378 (2000).
[6] R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, Phys.
Rev. Lett. 85, 4626 (2000).
[7] R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett. 86,
3200 (2001).
[8] S. N. Dorogovtsev, A.V. Goltsev, and J. F. F. Mendes,
Phys. Rev. E 66, 016104 (2002).
[9] F. Igloi and L. Turban, Phys. Rev. E 66, 036140 (2002).
[10] M. E. J. Newman, Phys. Rev. E 64, 016131 (2001); 64,
016132 (2001).
[11] K.-I. Goh, B. Kahng, and D. Kim, Phys. Rev. Lett. 87,
278701 (2001);K.-I. Goh, E. S. Oh, H. Jeong, B. Kahng,
and D. Kim, Proc. Natl. Acad. Sci. U.S.A. 99, 12583
(2002).
[12] R. D. Hughes, Random Walks: Random Walks and
Random Environments (Clarendon, Oxford, 1995), Vol. 1.
[13] S. Jespersen, I. M. Sokolov, and A. Blumen, Phys. Rev. E
62, 4405 (2000); B. Tadic, Eur. Phys. J. B 23, 221 (2001);
H. Zhou, cond-mat/0302030.
[14] J. D. Noh and H. Rieger (unpublished).
[15] L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A.
Huberman, Phys. Rev. E 64, 046135 (2001).
[16] R. Guimera, A. D az-Guilera, F. Vega-Redondo,
A. Cabrales, and A. Arenas, Phys. Rev. Lett. 89,
248701 (2002).
[17] P. Holme, cond-mat/0301013.
[18] In this denition, all links are assumed to be equivalent.
Evolution of the shortest path in weighted networks is
discussed in Ref. [19].
[19] J. D. Noh and H. Rieger, Phys. Rev. E 66, 066127 (2002).
[20] In weighted networks, the hopping probability may be
written as
~
AA
ij
=
~
KK
i
, where
~
AA
ij
w
ij
A
ij
and
~
KK
i
P
j
~
AA
ij
with a weight w
ij
> 0. All results in this Letter remain
valid as long as the weight is symmetric, i.e.,
~
AA
ij
~
AA
ji
.
[21] The limit exists if and only if the network contains an
odd loop. Then all other eigenvalues of the time evolution
operator satisfy }} <1, otherwise there exists an eigen-
value 1, for which the innite time limit does not
exist. In such cases, one may redene the RW model
setting A
ii
1 to make the limit exist.
[22] A.-L. Barabasi and R. Albert, Science 286, 509 (1999).
[23] E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai, and
A.-L. Barabasi, Science 297, 1551 (2002); E. Ravasz and
A.-L. Barabasi, Phys. Rev. E 67, 026112 (2003).
[24] J. D. Noh, Phys. Rev. E 67, 045103(R) (2003).
P H YS I CA L R E VI E W L E T T E RS
week ending
19 MARCH 2004 VOLUME 92, NUMBER 11
118701-4 118701-4