Random walks in generalized delayed recursive trees

doi:10.1088/1674-1056/22/10/108904

Abstract Recently a great deal of effort has been made to explicitly determine the mean first-passage time (MFPT) between two nodes averaged over all pairs of nodes on a fractal network. In this paper, we first propose a family of generalized delayed recursive trees characterized by two parameters, where the existing nodes have a time delay to produce new nodes. We then study the MFPT of random walks on this kind of recursive tree and investigate the effect of the time delay on the MFPT. By relating random walks to electrical networks, we obtain an exact formula for the MFPT and verify it by numerical calculations. Based on the obtained results, we further show that the MFPT of delayed recursive trees is much shorter, implying that the efficiency of random walks is much higher compared with the non-delayed counterpart. Our study provides a deeper understanding of random walks on delayed fractal networks.

Keywords: mean first-passage time random walk delayed recursive tree

Received: 08 March 2013
Revised: 13 April 2013
Accepted manuscript online:

PACS:	89.75.Fb	(Structures and organization in complex systems)
	89.75.Hc	(Networks and genealogical trees)
	05.40.Fb	(Random walks and Levy flights)

Fund: Project supported by the National Natural Science Foundation of China (Grant Nos. 61203155 and 11232005), the Natural Science Foundation of Zhejiang Province, China (Grant No. LQ12F03003), and the Hong Kong Research Grants Council under the GRF Grant CityU (Grant No. 1109/12).

Corresponding Authors: Sun Wei-Gang
E-mail: wgsun@hdu.edu.cn

Cite this article:

Sun Wei-Gang (孙伟刚), Zhang Jing-Yuan (张静远), Chen Guan-Rong (陈关荣) Random walks in generalized delayed recursive trees 2013 Chin. Phys. B 22 108904

[1]	Kozak J J and Balakrishnan V 2002 Phys. Rev. E 65 021105
[2]	Weber S, Klafter J and Blumen A 2010 Phys. Rev. E 82 051129
[3]	Dorogovtsev S N, Goltsev A V and Mendes J F F 2002 Phys. Rev. E 65 066122
[4]	Andrade J S, Herrmann H J, Andrade R F S and da Silva L R 2005 Phys. Rev. Lett. 94 018702
[5]	Huang Z G, Xu X J, Wu Z X and Wang Y H 2006 Eur. Phys. J. B 51 549
[6]	Zhang J Y, Sun W G and Chen G R 2012 Chin. Phys. B 21 038901
[7]	Comellas F and Miralles A 2010 Phys. Rev. E 81 061103
[8]	Zhang Z Z, Wu B and Chen G R 2011 Europhys. Lett. 96 40009
[9]	Agliari E 2008 Phys. Rev. E 77 011128
[10]	Zhang Z Z, Lin Y, Zhou S G, Wu B and Guan J H 2009 New. J. Phys. 11 103043
[11]	Barabási A L, Ravasz E and Vicsek T 2001 Physica A 299 559
[12]	Comellas F, Ozón J and Peters J G 2000 Inf. Process. Lett. 76 83
[13]	Zou Z Y, Liu P, Lei L and Gao J Z 2012 Chin. Phys. B 21 028904
[14]	Comellas F 2007 Physics and Theoretical Computer Science (IOP Press, Books online) pp. 275-293
[15]	Haynes C P and Roberts A P 2008 Phys. Rev. E 78 041111
[16]	Agliari E, Burioni R, Cassi D and Neri F M 2007 Theor. Chem. Account 118 855
[17]	Condamin S, Bènichou O, Tejedor V, Voituriez R and Klafter J 2007 Nature 450 77
[18]	Hwang S, Lee D S and Kahng B 2012 Phys. Rev. Lett. 109 088701
[19]	Meyer B, Agliari E, Bènichou O and Voituriez R 2012 Phys. Rev. E 85 026113
[20]	Tejedor V, Bènichou O and Voituriez R 2009 Phys. Rev. E 80 065104
[21]	Sun W G, Wu Y Q, Chen G R and Wang Q Y 2011 J. Stat. Mech. P10032
[22]	Stachowiak G 2000 Lecture Notes in Computer Science (Berlin: Springer-Verlag) pp. 535-548
[23]	Jung S, Kim S and Kahng B 2002 Phys. Rev. E 65 056101
[24]	Cantú A G and Abad E 2008 Phys. Rev. E 77 031121
[25]	Doyle P G and Snell J L 2000 arXiv: math/0001057v1
[26]	Klein D J and Randić M 1993 J. Math. Chem. 12 81
[27]	Gobel F and Jagers A 1974 Stoch. Proc. Appl. 2 311
[28]	Wang R, Sun W G, Tong L Y and Li C P 2012 The 8th IEEE/ASME International Conference on Mechatronic and Embedded Systems and Applications, July 8-10, 2012, Suzhou, China, p. 137
[29]	Guo L and Cai X 2009 Chin. Phys. Lett. 26 088901

[1]	Biased random walk with restart for essential proteins prediction Pengli Lu(卢鹏丽), Yuntian Chen(陈云天), Teng Zhang(张腾), and Yonggang Liao(廖永刚). Chin. Phys. B, 2022, 31(11): 118901.
[2]	Ergodicity recovery of random walk in heterogeneous disordered media Liang Luo(罗亮), Ming Yi(易鸣). Chin. Phys. B, 2020, 29(5): 050503.
[3]	The effect of phase fluctuation and beam splitter fluctuation on two-photon quantum random walk Zijing Zhang(张子静), Feng Wang(王峰), Jie Song(宋杰), Yuan Zhao(赵远). Chin. Phys. B, 2020, 29(2): 020503.
[4]	Nodes and layers PageRank centrality for multilayer networks Lai-Shui Lv(吕来水), Kun Zhang(张琨), Ting Zhang(张婷), Meng-Yue Ma(麻孟越). Chin. Phys. B, 2019, 28(2): 020501.
[5]	Diffusional inhomogeneity in cell cultures Jia-Zheng Zhang(张佳政), Na Li(李娜), Wei Chen(陈唯). Chin. Phys. B, 2018, 27(2): 028705.
[6]	Multiple-predators-based capture process on complex networks Rajput Ramiz Sharafat, Cunlai Pu(濮存来), Jie Li(李杰), Rongbin Chen(陈荣斌), Zhongqi Xu(许忠奇). Chin. Phys. B, 2017, 26(3): 038901.
[7]	Derivation of persistent time for anisotropic migration of cells Yan-Ping Liu(刘艳平), Xiao-Cui Zhang(张晓翠), Yu-Ling Wu(吴宇宁), Wen Liu(刘雯), Xiang Li(李翔), Ru-Chuan Liu(刘如川), Li-Yu Liu(刘雳宇), Jian-Wei Shuai(帅建伟). Chin. Phys. B, 2017, 26(12): 128707.
[8]	Anomalous transport in fluid field with random waiting time depending on the preceding jump length Hong Zhang(张红), Guo-Hua Li(李国华). Chin. Phys. B, 2016, 25(11): 110504.
[9]	Decoherence in optimized quantum random-walk search algorithm Zhang Yu-Chao (张宇超), Bao Wan-Su (鲍皖苏), Wang Xiang (汪翔), Fu Xiang-Qun (付向群). Chin. Phys. B, 2015, 24(8): 080307.
[10]	Rotational stretched exponential relaxation in random trap-barrier model Ekrem Aydıner. Chin. Phys. B, 2015, 24(7): 070501.
[11]	Effects of systematic phase errors on optimized quantum random-walk search algorithm Zhang Yu-Chao (张宇超), Bao Wan-Su (鲍皖苏), Wang Xiang (汪翔), Fu Xiang-Qun (付向群). Chin. Phys. B, 2015, 24(6): 060304.
[12]	Optimized quantum random-walk search algorithm for multi-solution search Zhang Yu-Chao (张宇超), Bao Wan-Su (鲍皖苏), Wang Xiang (汪翔), Fu Xiang-Qun (付向群). Chin. Phys. B, 2015, 24(11): 110309.
[13]	Sub-diffusive scaling with power-law trapping times Luo Liang (罗亮), Tang Lei-Han (汤雷翰). Chin. Phys. B, 2014, 23(7): 070514.
[14]	Averaging in SU(2) open quantum random walk Clement Ampadu. Chin. Phys. B, 2014, 23(3): 030302.
[15]	Average position in quantum walks with a U(2) coin Li Min (李敏), Zhang Yong-Sheng (张永生), Guo Guang-Can (郭光灿). Chin. Phys. B, 2013, 22(3): 030310.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Random walks in generalized delayed recursive trees

Cite this article:

Online attention