Mean first-passage time for random walks on undirected networks

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

67 Scopus Citations
View graph of relations

Author(s)

  • Zhongzhi Zhang
  • Alafate Julaiti
  • Baoyu Hou
  • Hongjuan Zhang
  • Guanrong Chen

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)691-697
Journal / PublicationEuropean Physical Journal B
Volume84
Issue number4
Publication statusPublished - Dec 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. © 2011 EDP Sciences, SIF, Springer-Verlag Berlin Heidelberg.

Citation Format(s)

Mean first-passage time for random walks on undirected networks. / Zhang, Zhongzhi; Julaiti, Alafate; Hou, Baoyu et al.
In: European Physical Journal B, Vol. 84, No. 4, 12.2011, p. 691-697.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review