Eur. Phys. J. B 84, 691-697 (2011)
https://doi.org/10.1140/epjb/e2011-20834-1

Regular Article

Mean first-passage time for random walks on undirected networks

¹ School of Computer Science, Fudan University, Shanghai 200433, P.R. China
² Shanghai Key Lab of Intelligent Information Processing, Fudan University, Shanghai 200433, P.R. China
³ Department of Mathematics, College of Science, Shanghai University, Shanghai 200444, P.R. China
⁴ 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

Abstract

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 N^1−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.