Mean first-passage time for random walks on undirected networks |
| |
Authors: | Zhongzhi Zhang Alafate Julaiti Baoyu Hou Hongjuan Zhang Guanrong Chen |
| |
Institution: | 1.School of Computer Science,Fudan University,Shanghai,P.R. China;2.Shanghai Key Lab of Intelligent Information Processing,Fudan University,Shanghai,P.R. China;3.Department of Mathematics, College of Science,Shanghai University,Shanghai,P.R. China;4.Department of Electronic Engineering,City University of Hong Kong,Hong Kong,P.R. China |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|