搜索

x

留言板

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

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

二维有限能量约束下最优导航问题的理论分析

黎勇 钭斐玲 樊瑛 狄增如

引用本文:
Citation:

二维有限能量约束下最优导航问题的理论分析

黎勇, 钭斐玲, 樊瑛, 狄增如

Theoretical analysis on optimal navigation with total energy restriction in a two-dimensional lattice

Li Yong, Dou Fei-Ling, Fan Ying, Di Zeng-Ru
PDF
导出引用
  • 最近, Li 等研究了在Kleinberg导航模型中引入总能量=cN约束后的最优导航问题, 其中为网络中所有长程连边的长度之和, c为正常数, N为网络节点总数.他们通过在1维和2维导航模型中的模拟结果推测, 在有限能量约束下Kleinberg导航模型中按照幂律方式添加长程连边的最优幂指数应该是=d+1, 其中d为导航模型的维数.本文在平均场理论下, 建立了2维有限能量约束下的导航过程的动态微分方程, 通过对该方程进行数学分析以及数值求解, 从理论上证明了当网络规模足够大且总能量相对较小时, 2维有限能量约束下的最优导航幂指数确实为=3, 这一结果证实了Li等之前的推测.
    Recently, a certain total energy constraint =cN was introduced into the Kleinberg's navigation model, where is the total length of the long-range connections, c is a positive constant and N is the network size. The simulation results obtained in the one and two-dimensional cases indicate that with total cost restricted the optimal power-law exponent for adding extra long-range links between any two nodes seems to be =d+1, where d is the dimension of the underlying lattice in this paper. Based on mean field theory, the navigation process on the 2-dimensional cost constrained navigation model can be described by dynamical equations. Based on our theoretical analysis and the numerical results of the dynamical equations, we prove that for large networks and comparatively small total energy, the optimal power-law exponent is =3 for the two-dimensional case. Our results can perfectly correspond to simulations reported previously.
    • 基金项目: 中央高校基本科研业务费专项资金、国家自然科学基金(批准号: 60974084, 61174150)和NCET-09-0228资助的课题.
    • Funds: Project supported by the Fundamental Research Funds for the Central Universities and NSFC (Grants Nos. 60974084, 61174150) and NCET-09-0228.
    [1]

    Li S B, Wu J J, Gao Z Y, Lin Y, Fu B B 2011 Acta Phys. Sin. 60 050701 (in Chinese) [李树彬, 吴建军, 高自友, 林勇, 傅白白 2011 物理学报 60 050701]

    [2]

    Xu D, Li X, Wang X F 2007 Acta Phys. Sin. 56 1313 (in Chinese) [许丹, 李翔, 汪小帆 2007 物理学报 56 1313]

    [3]

    Watts D J, Strogatz S H 1998 Nature 393 6684

    [4]

    Barabasi A L, Albert R 1999 Science 286 509

    [5]

    Girvan M, Newman M E J 2004 Proc. Natl. Acad. Sci. 99 7821

    [6]

    Du H F, Li S Z, Marcus W F, Yue Z S, Yang X S, 2007 Acta Phys. Sin. 56 6886 (in Chinese) [杜海峰, 李树茁, Marcus W F, 悦中山, 杨绪松 2007 物理学报 56 6886]

    [7]

    Milgram S 1967 Psycholgy Today 2 60

    [8]

    Travers J, Milgram S 1969 Sociometry 32 425

    [9]

    Dodds P S, Muhamad R, Watts D J 2003 Science 301 827

    [10]

    Kleinberg J 2000 Nature 406 845

    [11]

    Kleinberg J 2000 Proceedings of the thirty-second annual ACM symposium on Theory of computing 163-170

    [12]

    Roberson M R, Ben-Avraham D 2006 Phys. Rev. E 74 17101

    [13]

    Martel C, Nguyen V 2004 Proceedings of the Symposium on Principles of Distributed Computing, ed. Kutten, S. (ACM Press, New York) 179-188

    [14]

    Carmi S, Carter S, Sun J, Ben-Avraham D 2009 Phys. Rev. Lett. 102 238702

    [15]

    Caretta Cartozo C, De Los Rios P 2009 Phys. Rev. Lett. 102 238702

    [16]

    Yang H, Nie Y C, Zeng A, Fan Y, Hu Y Q, Di Z R 2010 EPL 89 5800

    [17]

    Li G, Reis S D S, Moreira A A, Havlin S, Stanley H E, Andrade Jr. J S 2010 Phys. Rev. Lett. 104 018701

    [18]

    Bianconi G, Pin P, Marsilli M 2009 Proc. Natl. Acad. Sci. 106 11433

    [19]

    Li Y, Zhou D, Hu Y Q, Zhang J, Di Z R 2010 EPL 92 58002

    [20]

    Hu Y Q, Li Y, Di Z R, Fan Y 2010 arXiv: 1010.18

  • [1]

    Li S B, Wu J J, Gao Z Y, Lin Y, Fu B B 2011 Acta Phys. Sin. 60 050701 (in Chinese) [李树彬, 吴建军, 高自友, 林勇, 傅白白 2011 物理学报 60 050701]

    [2]

    Xu D, Li X, Wang X F 2007 Acta Phys. Sin. 56 1313 (in Chinese) [许丹, 李翔, 汪小帆 2007 物理学报 56 1313]

    [3]

    Watts D J, Strogatz S H 1998 Nature 393 6684

    [4]

    Barabasi A L, Albert R 1999 Science 286 509

    [5]

    Girvan M, Newman M E J 2004 Proc. Natl. Acad. Sci. 99 7821

    [6]

    Du H F, Li S Z, Marcus W F, Yue Z S, Yang X S, 2007 Acta Phys. Sin. 56 6886 (in Chinese) [杜海峰, 李树茁, Marcus W F, 悦中山, 杨绪松 2007 物理学报 56 6886]

    [7]

    Milgram S 1967 Psycholgy Today 2 60

    [8]

    Travers J, Milgram S 1969 Sociometry 32 425

    [9]

    Dodds P S, Muhamad R, Watts D J 2003 Science 301 827

    [10]

    Kleinberg J 2000 Nature 406 845

    [11]

    Kleinberg J 2000 Proceedings of the thirty-second annual ACM symposium on Theory of computing 163-170

    [12]

    Roberson M R, Ben-Avraham D 2006 Phys. Rev. E 74 17101

    [13]

    Martel C, Nguyen V 2004 Proceedings of the Symposium on Principles of Distributed Computing, ed. Kutten, S. (ACM Press, New York) 179-188

    [14]

    Carmi S, Carter S, Sun J, Ben-Avraham D 2009 Phys. Rev. Lett. 102 238702

    [15]

    Caretta Cartozo C, De Los Rios P 2009 Phys. Rev. Lett. 102 238702

    [16]

    Yang H, Nie Y C, Zeng A, Fan Y, Hu Y Q, Di Z R 2010 EPL 89 5800

    [17]

    Li G, Reis S D S, Moreira A A, Havlin S, Stanley H E, Andrade Jr. J S 2010 Phys. Rev. Lett. 104 018701

    [18]

    Bianconi G, Pin P, Marsilli M 2009 Proc. Natl. Acad. Sci. 106 11433

    [19]

    Li Y, Zhou D, Hu Y Q, Zhang J, Di Z R 2010 EPL 92 58002

    [20]

    Hu Y Q, Li Y, Di Z R, Fan Y 2010 arXiv: 1010.18

  • [1] 林泓, 夏永祥, 蒋路茸. 基于最短路径长度的空间网络路由. 物理学报, 2022, 71(6): 068901. doi: 10.7498/aps.71.20211621
    [2] 尹宁, 徐桂芝, 周茜. 磁刺激穴位复杂脑功能网络构建与分析. 物理学报, 2013, 62(11): 118704. doi: 10.7498/aps.62.118704
    [3] 刘金良. 具有随机节点结构的复杂网络同步研究. 物理学报, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
    [4] 李雨珊, 吕翎, 刘烨, 刘硕, 闫兵兵, 常欢, 周佳楠. 复杂网络时空混沌同步的Backstepping设计. 物理学报, 2013, 62(2): 020513. doi: 10.7498/aps.62.020513
    [5] 丁益民, 杨昌平. 考虑人类流动行为的动态复杂网络研究. 物理学报, 2012, 61(23): 238901. doi: 10.7498/aps.61.238901
    [6] 吕天阳, 谢文艳, 郑纬民, 朴秀峰. 加权复杂网络社团的评价指标及其发现算法分析. 物理学报, 2012, 61(21): 210511. doi: 10.7498/aps.61.210511
    [7] 周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. 物理学报, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
    [8] 郝崇清, 王江, 邓斌, 魏熙乐. 基于稀疏贝叶斯学习的复杂网络拓扑估计. 物理学报, 2012, 61(14): 148901. doi: 10.7498/aps.61.148901
    [9] 吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. 物理学报, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [10] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [11] 刘刚, 李永树. 基于引力约束的复杂网络拥塞问题研究. 物理学报, 2012, 61(10): 108901. doi: 10.7498/aps.61.108901
    [12] 钭斐玲, 胡延庆, 黎勇, 樊瑛, 狄增如. 空间网络上的随机游走. 物理学报, 2012, 61(17): 178901. doi: 10.7498/aps.61.178901
    [13] 崔爱香, 傅彦, 尚明生, 陈端兵, 周涛. 复杂网络局部结构的涌现:共同邻居驱动网络演化. 物理学报, 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
    [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(3): 1462-1466. doi: 10.7498/aps.58.1462
    [17] 王丹, 于灏, 井元伟, 姜囡, 张嗣瀛. 基于感知流量算法的复杂网络拥塞问题研究. 物理学报, 2009, 58(10): 6802-6808. doi: 10.7498/aps.58.6802
    [18] 钱江海, 韩定定. 基于预期流优化的空间网络引力模型. 物理学报, 2009, 58(5): 3028-3033. doi: 10.7498/aps.58.3028
    [19] 许 丹, 李 翔, 汪小帆. 复杂网络病毒传播的局域控制研究. 物理学报, 2007, 56(3): 1313-1317. doi: 10.7498/aps.56.1313
    [20] 李 季, 汪秉宏, 蒋品群, 周 涛, 王文旭. 节点数加速增长的复杂网络生长模型. 物理学报, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
计量
  • 文章访问数:  6978
  • PDF下载量:  377
  • 被引次数: 0
出版历程
  • 收稿日期:  2011-11-10
  • 修回日期:  2012-06-03
  • 刊出日期:  2012-11-05

/

返回文章
返回