https://doi.org/10.1140/epjb/e2011-20834-1
Regular Article
Mean first-passage time for random walks on undirected networks
1
School of Computer Science, Fudan University,
Shanghai
200433, P.R.
China
2
Shanghai Key Lab of Intelligent Information Processing, Fudan
University, Shanghai
200433, P.R.
China
3
Department of Mathematics, College of Science, Shanghai
University, Shanghai
200444, P.R.
China
4
Department of Electronic Engineering, City University of Hong
Kong, Hong Kong,
P.R. China
a e-mail: zhangzz@fudan.edu.cn
b
e-mail: eegchen@cityu.edu.hk
Received:
14
September
2011
Published online:
23
November
2011
In this paper, by using two different techniques we derive an explicit formula for the mean first-passage time (MFPT) between any pair of nodes on a general undirected network, which is expressed in terms of eigenvalues and eigenvectors of an associated matrix similar to the transition matrix. We then apply the formula to derive a lower bound for the MFPT to arrive at a given node with the starting point chosen from the stationary distribution over the set of nodes. We show that for a correlated scale-free network of size N with a degree distribution P(d) ~ d−γ, the scaling of the lower bound is N1−1/γ. Also, we provide a simple derivation for an eigentime identity. Our work leads to a comprehensive understanding of recent results about random walks on complex networks, especially on scale-free networks.
© EDP Sciences, Società Italiana di Fisica and Springer-Verlag, 2011