Search

Article

x

留言板

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

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

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

Li Yong Dou Fei-Ling Fan Ying Di Zeng-Ru

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
Get Citation
  • 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.
    • 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] Dou Fei-Ling, Hu Yan-Qing, Li Yong, Fan Ying, Di Zeng-Ru. Random walks on spatial networks. Acta Physica Sinica, 2012, 61(17): 178901. doi: 10.7498/aps.61.178901
    [2] Qian Jiang-Hai, Han Ding-Ding. Gravity model for spatial network based on optimal expected traffic. Acta Physica Sinica, 2009, 58(5): 3028-3033. doi: 10.7498/aps.58.3028
    [3] Liu Gang, Li Yong-Shu. Study on the congestion phenomena in complex network based on gravity constraint. Acta Physica Sinica, 2012, 61(10): 108901. doi: 10.7498/aps.61.108901
    [4] Cui Ai-Xiang, Fu Yan, Shang Ming-Sheng, Chen Duan-Bing, Zhou Tao. Emergence of local structures in complex network:common neighborhood drives the network evolution. Acta Physica Sinica, 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
    [5] Xu Dan, Li Xiang, Wang Xiao-Fan. An investigation on local area control of virus spreading in complex networks. Acta Physica Sinica, 2007, 56(3): 1313-1317. doi: 10.7498/aps.56.1313
    [6] Li Yu-Shan, Lü Ling, Liu Ye, Liu Shuo, Yan Bing-Bing, Chang Huan, Zhou Jia-Nan. Spatiotemporal chaos synchronization of complex networks by Backstepping design. Acta Physica Sinica, 2013, 62(2): 020513. doi: 10.7498/aps.62.020513
    [7] Wang Bing-Hong, Zhou Tao, Wang Wen-Xu, Li Ji, Jiang Pin-Qun. Growing complex network model with acceleratingly increasing number of nodes. Acta Physica Sinica, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
    [8] Wang Dan, Yu Hao, Jing Yuan-Wei, Jiang Nan, Zhang Si-Ying. Study on the congestion in complex network based on traffic awareness algorithm. Acta Physica Sinica, 2009, 58(10): 6802-6808. doi: 10.7498/aps.58.6802
    [9] Lü Ling, Zhang Chao. Chaos synchronization of a complex network with different nodes. Acta Physica Sinica, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [10] Li Tao, Pei Wen-Jiang, Wang Shao-Ping. Optimal traffic routing strategy on scale-free complex networks. Acta Physica Sinica, 2009, 58(9): 5903-5910. doi: 10.7498/aps.58.5903
  • Citation:
Metrics
  • Abstract views:  2956
  • PDF Downloads:  366
  • Cited By: 0
Publishing process
  • Received Date:  10 November 2011
  • Accepted Date:  03 June 2012
  • Published Online:  20 November 2012

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

  • 1. Department of Systems Science, School of Management and Center for Complexity Research, Beijing Normal University, Beijing 100875, China
Fund Project:  Project supported by the Fundamental Research Funds for the Central Universities and NSFC (Grants Nos. 60974084, 61174150) and NCET-09-0228.

Abstract: 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.

Reference (20)

Catalog

    /

    返回文章
    返回