arXiv Analytics

Sign in

arXiv:1209.6165 [cond-mat.stat-mech]AbstractReferencesReviewsResources

Mean first-passage time for random walks in general graphs with a deep trap

Yuan Lin, Alafate Julaiti, Zhongzhi Zhang

Published 2012-09-27Version 1

We provide an explicit formula for the global mean first-passage time (GMFPT) for random walks in a general graph with a perfect trap fixed at an arbitrary node, where GMFPT is the average of mean first-passage time to the trap over all starting nodes in the whole graph. The formula is expressed in terms of eigenvalues and eigenvectors of Laplacian matrix for the graph. We then use the formula to deduce a tight lower bound for the GMFPT in terms of only the numbers of nodes and edges, as well as the degree of the trap, which can be achieved in both complete graphs and star graphs. We show that for a large sparse graph the leading scaling for this lower bound is proportional to the system size and the reciprocal of the degree for the trap node. Particularly, we demonstrate that for a scale-free graph of size $N$ with a degree distribution $P(d)\sim d^{-\gamma}$ characterized by $\gamma$, when the trap is placed on a most connected node, the dominating scaling of the lower bound becomes $N^{1-1/\gamma}$, which can be reached in some scale-free graphs. Finally, we prove that the leading behavior of upper bounds for GMFPT on any graph is at most $N^{3}$ that can be reached in the bar-bell graphs. This work provides a comprehensive understanding of previous results about trapping in various special graphs with a trap located at a specific location.

Comments: Definitive version accepted for publication in The Journal of Chemical Physics
Journal: J. Chem. Phys. 137, 124104 (2012)
Related articles: Most relevant | Search more
arXiv:1303.4607 [cond-mat.stat-mech] (Published 2013-03-19)
Exact Statistics of the Gap and Time Interval Between the First Two Maxima of Random Walks
arXiv:1012.5786 [cond-mat.stat-mech] (Published 2010-12-28)
Time transformation for random walks in the quenched trap model
arXiv:1301.0876 [cond-mat.stat-mech] (Published 2013-01-05)
Optimal scale-free network with a minimum scaling of transport efficiency for random walks with a perfect trap