An Exact Numerical Approach to Calculate the First Passage Time for General Random Walks on a Network
XIE Yan-Bo1, LI Yu-Jian2, LI Ming1, XI Zhen-Dong2, WANG Bing-Hong1,3,4**
1Department of Modern Physics, University of Science and Technology of China, Hefei 230026 2Department of Satellite Measurement and Control on Sea of China, Jiangyin 214400 3College of Physics and Electronic Information Engineering, Wenzhou University, Wenzhou 325035 4School of Science, Southwest University of Science and Technology, Mianyang 621010
Abstract:We present an exact numerical method to calculate the mean first passage time for the random walk on the network between any source node and any target which contains an arbitrary number of nodes. For the network with the average degree <k>~O(1) and the effective diameter D ~lnN or less, the efficiency of our numerical approach is found to exceed all other general numerical methods presented in the literature. Our method can also calculate the average of any function of the first passage time, provided it is finite.
. [J]. 中国物理快报, 2013, 30(11): 110504-110504.
XIE Yan-Bo, LI Yu-Jian, LI Ming, XI Zhen-Dong, WANG Bing-Hong. An Exact Numerical Approach to Calculate the First Passage Time for General Random Walks on a Network. Chin. Phys. Lett., 2013, 30(11): 110504-110504.
[1] Van Kampen N G 1992 Stochastic Processes in Physics and Chemistry (Amsterdam: North-Holland Personal Library)[2] Redner S 2001 A Guide to First-Passage Processes (Cambridge: Cambridge University Press)[3] Noh J D and Rieger H 2004 Phys. Rev. Lett.92 118701[4] Condamin S, B énichou O and Moreau M 2005 Phys. Rev. Lett.95 260601[5] Aldous D and Fill J 2002 Reversible Markov Chains and Random Walks on Graphs[6] Erd?s P and Rényi A 1959 Publicationes Mathematicae6 290[7] Watts D J and Stragatz S H 1998 Nature393 440[8] Barabási A L and Albert R 1999 Science286 509[9] Bar-Haim A and Klatter J 1998 J. Chem. Phys.109 5187[10] Xie Y B, Wang B H, Yang W S and Wang W N 2004 Chin. Sci. Bull.49 432[11] Yang H X, Wang W X, Xie Y B, Lai Y C and Wang B H 2011 Phys. Rev. E 83 016102