Mean Fist Passage Time and Average Trapping Time for Random Walks on Weighted Networks
JING Xingli1, ZHAO Caihong1, LING Xiang2
1.Jiyuan Vocational and Technical College, Jiyuan 454650, China; 2.School of Automotive and Transportation Engineering, Hefei University of Technology, Hefei 230009, China
Abstract：Random walk is a fundamental mechanism for studying dynamics on networks. Random walk on the weighted network has also been widely concerned. In this paper, the mean first-passage time and average trapping time are studied based on the spectral graph theory for random walks on weighted networks. This is different from the Ref. [11], which is concerned with the mean first return time. The main results can be stated as following: the mean first-passage time and average trapping time are related to the size of the network, the degree of trapping point, and the weighted parameter θ and the average degree of the network. Our simulation results are in good agreement with the analytical results.
景兴利, 赵彩红, 凌翔. 加权网络上随机行走的平均首到达时间与平均吸收时间[J]. 复杂系统与复杂性科学, 2018, 15(4): 25-30.
JING Xingli, ZHAO Caihong, LING Xiang. Mean Fist Passage Time and Average Trapping Time for Random Walks on Weighted Networks. Complex Systems and Complexity Science, 2018, 15(4): 25-30.
[1]Montroll E W. Random walks on lattices. III. calculation of first-passage times with application to exciton trapping on photosynthetic units[J]. Journal of Mathematical Physics, 1969, 10(4): 753765. [2]Bar-Haim A, Klafter J, Kopelman R. Dendrimers as controlled artificial energy antennae[J]. Journal of the American Chemical Society, 1997, 119(26): 61976198. [3]Bar-Haim A, Klafter J. Geometric versus energetic competition in light harvesting by dendrimers[J]. The Journal of Physical Chemistry B, 1998, 102(10): 16621664. [4]Zhang Z, Julaiti A, Hou B, et al. Mean first-passage time for random walks on undirected networks[J]. The European Physical Journal B, 2011, 84(4): 691697. [5]Lin Y, Julaiti A, Zhang Z. Mean first-passage time for random walks in general graphs with a deep trap[J]. The Journal of Chemical Physics, 2012, 137(12): 124104. [6]Xing C, Zhang Y, Ma J, et al. Exact solutions for average trapping time of random walks on weighted scale-free networks[J]. Fractals, 2017, 25(2): 1750013. [7]Bellingeri M, Cassi D. Robustness of weighted networks[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 489: 4755. [8]Zhu Y X, Wang W, Tang M, et al. Social contagions on weighted networks[J]. Physical Review E, 2017, 96(1): 012306. [9]童丽艳,刘阳,孙伟刚,等.广义伪分形网络上随机游走的平均首达时间的精确幂律[J].应用数学与计算数学学报,2012,26(2):176184. Tong Liyan, Liu Yang, Sun Weigang, et al. Exact scaling for mean first-passage time of random walks on generalized pseudofractal web [J].Commun Appl Math Comput, 2012, 26(2):176184. [10] 盛益彬,章忠志.加权无标度伪分形网络的谱及其应用[DB/OL].[20180126].https://doi.org/10.19678/J.ISSN.10003428.0049583. Sheng Yibin, Zhang Zhongzhi Spectrum of weighted pseudofractal scale-free network and its application[DB/OL]. [20180126].Computer Engineering, 2018. https://doi.org/10.19678/J.ISSN.10003428.0049583. [11] Jing X L, Ling X, Long J, et al. Mean first return time for random walks on weighted networks[J]. International Journal of Modern Physics C, 2015, 26(6): 1550068. [12] Haynes C P, Roberts A P. Global first-passage times of fractal lattices[J]. Physical Review E, 2008, 78(4): 041111. [13] Zhang Z, Wu B, Chen G. Complete spectrum of the stochastic master equation for random walks on treelike fractals[J]. Europhysics Letters, 2011, 96(4): 40009. [14] Meyer B, Agliari E, Bénichou O, et al. Exact calculations of first-passage quantities on recursive networks[J]. Physical Review E, 2012, 85(2): 026113. [15] Zhang Z, Yang Y, Gao S. Role of fractal dimension in random walks on scale-free networks[J]. The European Physical Journal B, 2011, 84(2): 331338. [16] Zhang Z, Yang Y, Lin Y. Random walks in modular scale-free networks with multiple traps[J]. Physical Review E, 2012, 85(1): 011106. [17] Zhang Z, Shan T, Chen G. Random walks on weighted networks[J]. Physical Review E, 2013, 87(1): 012112. [18] Lin Y, Zhang Z. Random walks in weighted networks with a perfect trap: an application of Laplacian spectra[J]. Physical Review E, 2013, 87(6): 062140. [19] Wu A, Xu X, Wu Z, et al. Walks on weighted networks[J]. Chinese Physics Letters, 2007, 24(2): 577. [20] Barrat A, Barthelemy M, Pastor-Satorras R, et al. The architecture of complex weighted networks[J]. Proceedings of the National Academy of Sciences, 2004, 101(11): 37473752. [21] Macdonald P J, Almaas E, Barabási A L. Minimum spanning trees of weighted scale-free networks[J]. Europhysics Letters, 2005, 72(2): 308. [22] Kemeny J, Snell J, Finite Markov Chains[M]. New York: Springer, 1976. [23] Grinstead C, Snell J. Introduction to Probability[M]. Providence, RI: American Mathematical Society, 1997. [24] Lin Y, Zhang Z. Random walks in weighted networks with a perfect trap: an application of Laplacian spectra[J]. Physical Review E, 2013, 87(6): 062140. [25] Barabási A L, Albert R. Emergence of scaling in random networks[J]. science, 1999, 286(5439): 509512.
