Random walks in generalized delayed recursive trees

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

中国物理B ›› 2013, Vol. 22 ›› Issue (10): 108904-108904.doi: 10.1088/1674-1056/22/10/108904

• INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY • 上一篇下一篇

Random walks in generalized delayed recursive trees

孙伟刚^a, 张静远^a, 陈关荣^b

a Institute of Applied Mathematics and Engineering Computations, Hangzhou Dianzi University, Hangzhou 310018, China;
b Department of Electronic Engineering, City University of Hong Kong, SAR, Hong Kong, China

收稿日期:2013-03-08 修回日期:2013-04-13 出版日期:2013-08-30 发布日期:2013-08-30
基金资助:
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).

Random walks in generalized delayed recursive trees

Sun Wei-Gang (孙伟刚)^a, Zhang Jing-Yuan (张静远)^a, Chen Guan-Rong (陈关荣)^b

a Institute of Applied Mathematics and Engineering Computations, Hangzhou Dianzi University, Hangzhou 310018, China;
b Department of Electronic Engineering, City University of Hong Kong, SAR, Hong Kong, China

Received:2013-03-08 Revised:2013-04-13 Online:2013-08-30 Published:2013-08-30
Contact: Sun Wei-Gang E-mail:wgsun@hdu.edu.cn
Supported by:
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).

摘要/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.

关键词: mean first-passage time, random walk, delayed recursive tree

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.

Key words: mean first-passage time, random walk, delayed recursive tree

中图分类号: (Structures and organization in complex systems)

89.75.Fb

89.75.Hc (Networks and genealogical trees) 05.40.Fb (Random walks and Levy flights)

孙伟刚, 张静远, 陈关荣. Random walks in generalized delayed recursive trees[J]. 中国物理B, 2013, 22(10): 108904-108904.

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

参考文献 29

[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

Random walks in generalized delayed recursive trees

Random walks in generalized delayed recursive trees

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 29

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Pengli Lu(卢鹏丽), Yuntian Chen(陈云天), Teng Zhang(张腾), and Yonggang Liao(廖永刚). Biased random walk with restart for essential proteins prediction[J]. 中国物理B, 2022, 31(11): 118901-118901.
[2]	罗亮, 易鸣. Ergodicity recovery of random walk in heterogeneous disordered media[J]. 中国物理B, 2020, 29(5): 50503-050503.
[3]	张子静, 王峰, 宋杰, 赵远. The effect of phase fluctuation and beam splitter fluctuation on two-photon quantum random walk[J]. 中国物理B, 2020, 29(2): 20503-020503.
[4]	吕来水, 张琨, 张婷, 麻孟越. Nodes and layers PageRank centrality for multilayer networks[J]. 中国物理B, 2019, 28(2): 20501-020501.
[5]	张佳政, 李娜, 陈唯. Diffusional inhomogeneity in cell cultures[J]. 中国物理B, 2018, 27(2): 28705-028705.
[6]	濮存来, 李杰, 陈荣斌, 许忠奇. Multiple-predators-based capture process on complex networks[J]. 中国物理B, 2017, 26(3): 38901-038901.
[7]	刘艳平, 张晓翠, 吴宇宁, 刘雯, 李翔, 刘如川, 刘雳宇, 帅建伟. Derivation of persistent time for anisotropic migration of cells[J]. 中国物理B, 2017, 26(12): 128707-128707.
[8]	张红, 李国华. Anomalous transport in fluid field with random waiting time depending on the preceding jump length[J]. 中国物理B, 2016, 25(11): 110504-110504.
[9]	张宇超, 鲍皖苏, 汪翔, 付向群. Decoherence in optimized quantum random-walk search algorithm[J]. 中国物理B, 2015, 24(8): 80307-080307.
[10]	Ekrem Aydıner. Rotational stretched exponential relaxation in random trap-barrier model[J]. 中国物理B, 2015, 24(7): 70501-070501.
[11]	张宇超, 鲍皖苏, 汪翔, 付向群. Effects of systematic phase errors on optimized quantum random-walk search algorithm[J]. 中国物理B, 2015, 24(6): 60304-060304.
[12]	张宇超, 鲍皖苏, 汪翔, 付向群. Optimized quantum random-walk search algorithm for multi-solution search[J]. 中国物理B, 2015, 24(11): 110309-110309.
[13]	罗亮, 汤雷翰. Sub-diffusive scaling with power-law trapping times[J]. 中国物理B, 2014, 23(7): 70514-070514.
[14]	Clement Ampadu. Averaging in SU(2) open quantum random walk[J]. 中国物理B, 2014, 23(3): 30302-030302.
[15]	李敏, 张永生, 郭光灿. Average position in quantum walks with a U(2) coin[J]. 中国物理B, 2013, 22(3): 30310-030310.