搜索

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

无标度立体Koch网络上随机游走的平均吸收时间

邢长明 刘方爱 徐如志

引用本文:
Citation:

无标度立体Koch网络上随机游走的平均吸收时间

邢长明, 刘方爱, 徐如志

Exact solution for mean trapping time of random walk on a scale-free Koch network

Xing Chang-Ming, Liu Fang-Ai, Xu Ru-Zhi
PDF
导出引用
  • 作为一种基本的动力学过程,复杂网络上的随机游走是当前学术界研究的热点问题, 其中精确计算带有陷阱的随机游走过程的平均吸收时间(mean trapping time, MTT)是该领域的一个难点. 这里的MTT定义为从网络上任意一个节点出发首次到达设定陷阱的平均时间. 本文研究了无标度立体Koch网络上带有一个陷阱的随机游走问题, 解析计算了陷阱置于网络中度最大的节点这一情形的网络MTT指标. 通过重正化群方法,利用网络递归生成的模式,给出了立体Koch网络上MTT的精确解, 所得计算结果与数值解一致,并且从所得结果可以看出,立体Koch网络的MTT随着网络节点数N呈线性增长. 最后,将所得结果与之前研究的完全图、规则网络、Sierpinski网络和T分形网络进行比较, 结果表明Koch网络具有较高的传输效率.
    As a basic dynamical process, random walk on networks is fundamental to many branches of science, and has attracted much attention. A difficult problem in the study of random walk is how to obtain the exact solution for the mean trapping time (MTT) of this process. The MTT is defined as the mean time for the walker staring from any node in the network to first reach the trap node. In this paper, we study random walk on the Koch network with a trap located at the highest degree node and calculate the solution for MTT. The accurate expression for the MTT is obtained through the recurrence relation and the structure properties of the Koch network. We confirm the correctness of the MTT result by direct numerical calculations based on the Laplacian matrix of Koch network. It can be seen from the obtained results that in the large limit of network size, the MTT increases linearly with the size of network increasing. Comparison between the MTT result of the Koch network with that of the other networks, such as complete graph, regular lattices, Sierpinski fractals, and T-graph, shows that the Koch has a high transmission efficiency.
    • 基金项目: 国家自然科学基金(批准号: 71171122, 90612003); 山东省自然科学基金(批准号: ZR2010FM003, 2009ZRB019PF)和山东高校科研发展计划(批准号: J11LG11)资助的课题.
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 71171122, 90612003), the Natural Science Foundation of Shandong Province, China (Grant Nos. ZR2010FM003, 2009ZRB019PF), and the University Research and Development Program of Shandong Province, China (Grant No. J11LG11).
    [1]

    Albert R, Jeong H, Barabasi A L 1999 Nature 401 130

    [2]

    Cami A, Deo N 2008 Networks 51 211

    [3]

    Faloutsos M, Faloutsos P, Faloutsos C 1999 Comput. Commun. Rev. 29 251

    [4]

    Xu T, Chen R, He Y 2004 Int. J. Mod. Phys. B 18 2599

    [5]

    Guimerá R, Amaral L A N 2004 Eur. Phys. J. B 38 381

    [6]

    Dorogovtsev S N, Goltsev A V, Mendes J F F 2008 Rev. Mod. Phys. 80 1275

    [7]

    Spitzer F 1964 Principles of Random Walk (1st Ed.) (Princeton, N. J.: van Nostrand) p402

    [8]

    Lloyd A L, May R M 2001 Science 292 1316

    [9]

    Shlesinger M F 2006 Nature 443 281

    [10]

    Pandit S A, Amritkar R E 2001 Phys. Rev. E 63 041104

    [11]

    Noh J D, Rieger H 2004 Phys. Rev. Lett. 92 118701

    [12]

    Lee S M, Yook S H, Kim Y 2008 Physica A 387 3033

    [13]

    Fouss F, Pirotte A, Renders J, Saerens M 2007 IEEE T. Knowl. Data En. 19 355

    [14]

    Berkhin P 2005 Internet Mathematics 2 73

    [15]

    Zhang Z Z, Li X T, Lin Y, Chen G R 2011 J. Stat. Mech. 2011 08013

    [16]

    Bénichou O, Coppey M, Moreau M, Suet P H, Voituriez R 2005 Phys. Rev. Lett. 94 198101

    [17]

    Loverdo C, Bénichou O, Moreau M, Voituriez R 2008 Nat. Phys. 4 134

    [18]

    Montroll E W 1969 J. Math. Phys. 10 753

    [19]

    Kozak J J, Balakrishnan V 2002 Phys. Rev. E 65 021105

    [20]

    Kozak J J, Balakrishnan V 2002 Int. J. Bifurcation Chaos Appl. Sci. Eng. 12 2379

    [21]

    Agliari E 2008 Phys. Rev. E 77 011128

    [22]

    Zhang Z Z, Qi Y, Zhou S G, Xie W L, Guan J H 2009 Phys. Rev. E 79 021127

    [23]

    Wu S Q, Zhang Z Z, Chen G R 2011 Eur. Phys. J. B 82 91

    [24]

    Zhang Z Z, Guan J H, Xie W L, Qi Y, Zhou S G 2009 Europhys. Lett. 86 10006

    [25]

    Zhang Z Z, Zhou S G, Xie W L, Chen L C, Lin Y, Guan J H 2009 Phys. Rev. E 79 061113

    [26]

    Liu J X, Kong X M 2010 Acta Phys. Sin. 59 2244 (in Chinese) [刘甲雪, 孔祥木 2010 物理学报 59 2244]

    [27]

    Zhang Z Z, Gao S Y, Chen L C, Zhou S G, Zhang H J, Gan J H 2010 J. Phys. A: Math. Theor. 43 395101

    [28]

    Zhang Z Z, Gao S Y, Xie W L 2010 Chaos 20 043112

    [29]

    Zhang Z Z, Gao S Y 2011 Euro. Phys. J. B 80 209

    [30]

    Wu B, Zhang Z Z, Chen G R 2012 J. Phys. A: Math. Theor. 45 025102

    [31]

    Newman M E J 2002 Phys. Rev. Lett. 89 208701

    [32]

    Kemeny J G, Snell J L 1976 Finite Markov Chains (lst Ed.) (New York: Springer) p210

  • [1]

    Albert R, Jeong H, Barabasi A L 1999 Nature 401 130

    [2]

    Cami A, Deo N 2008 Networks 51 211

    [3]

    Faloutsos M, Faloutsos P, Faloutsos C 1999 Comput. Commun. Rev. 29 251

    [4]

    Xu T, Chen R, He Y 2004 Int. J. Mod. Phys. B 18 2599

    [5]

    Guimerá R, Amaral L A N 2004 Eur. Phys. J. B 38 381

    [6]

    Dorogovtsev S N, Goltsev A V, Mendes J F F 2008 Rev. Mod. Phys. 80 1275

    [7]

    Spitzer F 1964 Principles of Random Walk (1st Ed.) (Princeton, N. J.: van Nostrand) p402

    [8]

    Lloyd A L, May R M 2001 Science 292 1316

    [9]

    Shlesinger M F 2006 Nature 443 281

    [10]

    Pandit S A, Amritkar R E 2001 Phys. Rev. E 63 041104

    [11]

    Noh J D, Rieger H 2004 Phys. Rev. Lett. 92 118701

    [12]

    Lee S M, Yook S H, Kim Y 2008 Physica A 387 3033

    [13]

    Fouss F, Pirotte A, Renders J, Saerens M 2007 IEEE T. Knowl. Data En. 19 355

    [14]

    Berkhin P 2005 Internet Mathematics 2 73

    [15]

    Zhang Z Z, Li X T, Lin Y, Chen G R 2011 J. Stat. Mech. 2011 08013

    [16]

    Bénichou O, Coppey M, Moreau M, Suet P H, Voituriez R 2005 Phys. Rev. Lett. 94 198101

    [17]

    Loverdo C, Bénichou O, Moreau M, Voituriez R 2008 Nat. Phys. 4 134

    [18]

    Montroll E W 1969 J. Math. Phys. 10 753

    [19]

    Kozak J J, Balakrishnan V 2002 Phys. Rev. E 65 021105

    [20]

    Kozak J J, Balakrishnan V 2002 Int. J. Bifurcation Chaos Appl. Sci. Eng. 12 2379

    [21]

    Agliari E 2008 Phys. Rev. E 77 011128

    [22]

    Zhang Z Z, Qi Y, Zhou S G, Xie W L, Guan J H 2009 Phys. Rev. E 79 021127

    [23]

    Wu S Q, Zhang Z Z, Chen G R 2011 Eur. Phys. J. B 82 91

    [24]

    Zhang Z Z, Guan J H, Xie W L, Qi Y, Zhou S G 2009 Europhys. Lett. 86 10006

    [25]

    Zhang Z Z, Zhou S G, Xie W L, Chen L C, Lin Y, Guan J H 2009 Phys. Rev. E 79 061113

    [26]

    Liu J X, Kong X M 2010 Acta Phys. Sin. 59 2244 (in Chinese) [刘甲雪, 孔祥木 2010 物理学报 59 2244]

    [27]

    Zhang Z Z, Gao S Y, Chen L C, Zhou S G, Zhang H J, Gan J H 2010 J. Phys. A: Math. Theor. 43 395101

    [28]

    Zhang Z Z, Gao S Y, Xie W L 2010 Chaos 20 043112

    [29]

    Zhang Z Z, Gao S Y 2011 Euro. Phys. J. B 80 209

    [30]

    Wu B, Zhang Z Z, Chen G R 2012 J. Phys. A: Math. Theor. 45 025102

    [31]

    Newman M E J 2002 Phys. Rev. Lett. 89 208701

    [32]

    Kemeny J G, Snell J L 1976 Finite Markov Chains (lst Ed.) (New York: Springer) p210

  • [1] 韩忠明, 李胜男, 郑晨烨, 段大高, 杨伟杰. 基于动态网络表示的链接预测. 物理学报, 2020, 69(16): 168901. doi: 10.7498/aps.69.20191162
    [2] 汪丽娜, 成媛媛, 臧臣瑞. 基于seasonal-trend-loess方法的符号化时间序列网络. 物理学报, 2019, 68(23): 238901. doi: 10.7498/aps.68.20190794
    [3] 胡耀光, 王圣军, 金涛, 屈世显. 度关联无标度网络上的有倾向随机行走. 物理学报, 2015, 64(2): 028901. doi: 10.7498/aps.64.028901
    [4] 吴腾飞, 周昌乐, 王小华, 黄孝喜, 谌志群, 王荣波. 基于平均场理论的微博传播网络模型. 物理学报, 2014, 63(24): 240501. doi: 10.7498/aps.63.240501
    [5] 李雨珊, 吕翎, 刘烨, 刘硕, 闫兵兵, 常欢, 周佳楠. 复杂网络时空混沌同步的Backstepping设计. 物理学报, 2013, 62(2): 020513. doi: 10.7498/aps.62.020513
    [6] 刘金良. 具有随机节点结构的复杂网络同步研究. 物理学报, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
    [7] 周婷婷, 金宁德, 高忠科, 罗跃斌. 基于有限穿越可视图的时间序列网络模型. 物理学报, 2012, 61(3): 030506. doi: 10.7498/aps.61.030506
    [8] 高忠科, 金宁德, 杨丹, 翟路生, 杜萌. 多元时间序列复杂网络流型动力学分析. 物理学报, 2012, 61(12): 120510. doi: 10.7498/aps.61.120510
    [9] 高湘昀, 安海忠, 方伟. 基于复杂网络的时间序列双变量相关性波动研究. 物理学报, 2012, 61(9): 098902. doi: 10.7498/aps.61.098902
    [10] 钭斐玲, 胡延庆, 黎勇, 樊瑛, 狄增如. 空间网络上的随机游走. 物理学报, 2012, 61(17): 178901. doi: 10.7498/aps.61.178901
    [11] 崔爱香, 傅彦, 尚明生, 陈端兵, 周涛. 复杂网络局部结构的涌现:共同邻居驱动网络演化. 物理学报, 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
    [12] 姜志宏, 王晖, 高超. 一种基于随机行走和策略连接的网络演化模型. 物理学报, 2011, 60(5): 058903. doi: 10.7498/aps.60.058903
    [13] 刘甲雪, 孔祥木. 无标度立体Koch网络的建立及其结构性质研究. 物理学报, 2010, 59(4): 2244-2249. doi: 10.7498/aps.59.2244
    [14] 陈华良, 刘忠信, 陈增强, 袁著祉. 复杂网络的一种加权路由策略研究. 物理学报, 2009, 58(9): 6068-6073. doi: 10.7498/aps.58.6068
    [15] 李涛, 裴文江, 王少平. 无标度复杂网络负载传输优化策略. 物理学报, 2009, 58(9): 5903-5910. doi: 10.7498/aps.58.5903
    [16] 王丹, 于灏, 井元伟, 姜囡, 张嗣瀛. 基于感知流量算法的复杂网络拥塞问题研究. 物理学报, 2009, 58(10): 6802-6808. doi: 10.7498/aps.58.6802
    [17] 吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 物理学报, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [18] 宋青松, 冯祖仁, 李人厚. 用于混沌时间序列预测的多簇回响状态网络. 物理学报, 2009, 58(7): 5057-5064. doi: 10.7498/aps.58.5057
    [19] 许 丹, 李 翔, 汪小帆. 复杂网络病毒传播的局域控制研究. 物理学报, 2007, 56(3): 1313-1317. doi: 10.7498/aps.56.1313
    [20] 李 季, 汪秉宏, 蒋品群, 周 涛, 王文旭. 节点数加速增长的复杂网络生长模型. 物理学报, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
计量
  • 文章访问数:  6739
  • PDF下载量:  722
  • 被引次数: 0
出版历程
  • 收稿日期:  2012-03-31
  • 修回日期:  2012-04-20
  • 刊出日期:  2012-10-05

/

返回文章
返回