搜索

x

留言板

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

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

复杂网络谱粗粒化方法的改进算法

周建 贾贞 李科赞

引用本文:
Citation:

复杂网络谱粗粒化方法的改进算法

周建, 贾贞, 李科赞

Improved algorithm of spectral coarse graining method of complex network

Zhou Jian, Jia Zhen, Li Ke-Zan
PDF
导出引用
  • 大规模网络的同步问题是网络科学的重要研究课题之一.粗粒化方法提供了一种将大规模网络转化为小规模网络,同时又能较好地保持原始网络的拓扑性质或动态特性的研究途径,其中比较有代表性的谱粗粒化方法能较好地保持初始网络的同步能力.然而,谱粗粒化方法在实际计算中计算量大、对实际大规模网络可执行性差.本文提出一种改进的谱粗粒化算法,能大幅减少计算量,同时获得更好的谱粗粒化效果.通过理论分析和大量的数值仿真实验验证了所提改进算法的粗粒化效果和计算量都明显优于原谱粗粒化方法.
    Complex network as a key approach to understanding many complex systems, such as biological, chemical, physical, technological and social systems, is ubiquitous in nature and society. Synchronization of large-scale complex networks is one of the most important issues in network science. In the last two decades, much attention has been paid to the synchronization of complex dynamic networks, especially the meso-scale networks. However, many real networks consist of even hundreds of millions of nodes. Analyzing the synchronization of such large-scale coupled complex dynamic networks often generate a large number of coupled differential equations, which may make many synchronization algorithms inapplicable for meso-scale networks due to the complexities of simulation experiments. Coarse graining method can map the large-scale networks into meso-scale networks while preserving some of topological properties or dynamic charac-teristics of the original network. Especially, the spectral coarse-graining scheme, as a typical coarse graining method, is proposed to reduce the network size while preserving the synchronization capacity of the initial network. Nevertheless, plenty of studies demonstrate that the components of eigenvectors for the eigenvalue of the coupling matrix, which can depict the ability to synchronizing networks, distribute unevenly. Most of the components distribute concentrically and the intervals are small, while some other components distribute dispersedly and the intervals are large, which renders the applications of original spectral coarse graining method unsatisfactory. Inspired by the adaptive clustering, we propose an improved spectral coarse graining algorithm, which clusters the same or the similar nodes in the network according to the distance between the components of eigenvectors for the eigenvalue of network coupling matrices, so that the nodes with the same or the similar dynamic properties can be effectively clustered together. Compared with the original spectral coarse graining algorithm, this method can improve the accuracy of the result of clustering. Meanwhile, our method can greatly reduce algorithm complexity, and obtain better spectral coarse graining result. Finally, numerical simulation experiments are implemented in four typical complex networks: NW network, ER network, BA scale-free network and clustering network. The comparison of results demonstrate that our method outperforms the original spectral coarse graining approach under various criteria, and improves the effect of coarse graining and the ability to synchronize networks.
      通信作者: 贾贞, jjjzzz0@163.com
    • 基金项目: 国家自然科学基金(批准号:61563013,61663006)资助的课题.
      Corresponding author: Jia Zhen, jjjzzz0@163.com
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 61563013, 61663006).
    [1]

    Pecora L M, Carroll T L 1998 Phys. Rev. Lett. 80 2109

    [2]

    Jost J, Joy M P 2001 Phys. Rev. E 65 016201

    [3]

    Wang X F, Chen G R 2002 IEEE Trans. Circuits-I 49 54

    [4]

    Barahona M, Pecora L M 2002 Phys. Rev. Lett. 89 054101

    [5]

    Wang X F, Chen G R 2002 Int. J. Bifurcat. Chaos 12 187

    [6]

    Motter A E, Zhou C S, Kurths J 2005 Phys. Rev. E 71 016116

    [7]

    Nishikawa T, Motter A E 2006 Physica D 224 77

    [8]

    Zhou J, Lu J A, Lu J H 2006 IEEE Trans. Auto. Control 51 652

    [9]

    Arenas A, Daz-Guilera A, Kurths J, Moreno Y, Zhou C S 2008 Phys. Rep. 469 93

    [10]

    Zhu T X, Wu Y, Xiao J H 2012 Acta Phys. Sin. 61 040502 (in Chinese) [朱廷祥, 吴晔, 肖井华 2012 物理学报 61 040502]

    [11]

    Xu M M, Lu J A, Zhou J 2016 Acta Phys. Sin. 65 028902 (in Chinese) [徐明明, 陆君安, 周进 2016 物理学报 65 028902]

    [12]

    Kurkcuoglu O, Jernigan R L, Doruker P 2004 Polymer 45 649

    [13]

    Marrink S J, Vries A H D, Mark A E 2004 J. Phys. Chem. B 108 750

    [14]

    Bornholdt S 2005 Science 310 449

    [15]

    Chen J, Lu J A, Lu X F, Wu X Q, Chen G R 2013 Commun. Nonlinear Sci. 18 3036

    [16]

    Zeng A, L L Y 2011 Phys. Rev. E 83 056123

    [17]

    Saunders M G, Voth G A 2013 Annu. Rev. Biophys. 42 73

    [18]

    Kim B J 2004 Phys. Rev. Lett. 93 168701

    [19]

    Chen H S, Hou Z H, Xin H W, Yan Y J 2010 Phys. Rev. E 82 011107

    [20]

    Gfeller D, Rios P D L 2007 Phys. Rev. Lett. 99 038701

    [21]

    Gfeller D, Rios P D L 2008 Phys. Rev. Lett. 100 174104

    [22]

    Chen G R, Wang X F, Li X, L J H 2009 Some Recent Advances in Complex Networks Synchronization (Heidelberg: Springer) pp3-16

    [23]

    Lu J A, Liu H, Chen J 2016 Synchronization in Complex Dynamical Networks (Beijing: Higher Education Press) pp120-125 (in Chinese) [陆君安, 刘慧, 陈娟 2016 复杂动态网络的同步(北京:高等教育出版社) 第120125页]

    [24]

    Kuramoto Y 1975 Lect. Notes Phys. 39 420

    [25]

    Acebrn J A, Bonilla L L, Prez Vicente C J, Ritort F, Spigler R 2005 Rev. Mod. Phys. 77 137

  • [1]

    Pecora L M, Carroll T L 1998 Phys. Rev. Lett. 80 2109

    [2]

    Jost J, Joy M P 2001 Phys. Rev. E 65 016201

    [3]

    Wang X F, Chen G R 2002 IEEE Trans. Circuits-I 49 54

    [4]

    Barahona M, Pecora L M 2002 Phys. Rev. Lett. 89 054101

    [5]

    Wang X F, Chen G R 2002 Int. J. Bifurcat. Chaos 12 187

    [6]

    Motter A E, Zhou C S, Kurths J 2005 Phys. Rev. E 71 016116

    [7]

    Nishikawa T, Motter A E 2006 Physica D 224 77

    [8]

    Zhou J, Lu J A, Lu J H 2006 IEEE Trans. Auto. Control 51 652

    [9]

    Arenas A, Daz-Guilera A, Kurths J, Moreno Y, Zhou C S 2008 Phys. Rep. 469 93

    [10]

    Zhu T X, Wu Y, Xiao J H 2012 Acta Phys. Sin. 61 040502 (in Chinese) [朱廷祥, 吴晔, 肖井华 2012 物理学报 61 040502]

    [11]

    Xu M M, Lu J A, Zhou J 2016 Acta Phys. Sin. 65 028902 (in Chinese) [徐明明, 陆君安, 周进 2016 物理学报 65 028902]

    [12]

    Kurkcuoglu O, Jernigan R L, Doruker P 2004 Polymer 45 649

    [13]

    Marrink S J, Vries A H D, Mark A E 2004 J. Phys. Chem. B 108 750

    [14]

    Bornholdt S 2005 Science 310 449

    [15]

    Chen J, Lu J A, Lu X F, Wu X Q, Chen G R 2013 Commun. Nonlinear Sci. 18 3036

    [16]

    Zeng A, L L Y 2011 Phys. Rev. E 83 056123

    [17]

    Saunders M G, Voth G A 2013 Annu. Rev. Biophys. 42 73

    [18]

    Kim B J 2004 Phys. Rev. Lett. 93 168701

    [19]

    Chen H S, Hou Z H, Xin H W, Yan Y J 2010 Phys. Rev. E 82 011107

    [20]

    Gfeller D, Rios P D L 2007 Phys. Rev. Lett. 99 038701

    [21]

    Gfeller D, Rios P D L 2008 Phys. Rev. Lett. 100 174104

    [22]

    Chen G R, Wang X F, Li X, L J H 2009 Some Recent Advances in Complex Networks Synchronization (Heidelberg: Springer) pp3-16

    [23]

    Lu J A, Liu H, Chen J 2016 Synchronization in Complex Dynamical Networks (Beijing: Higher Education Press) pp120-125 (in Chinese) [陆君安, 刘慧, 陈娟 2016 复杂动态网络的同步(北京:高等教育出版社) 第120125页]

    [24]

    Kuramoto Y 1975 Lect. Notes Phys. 39 420

    [25]

    Acebrn J A, Bonilla L L, Prez Vicente C J, Ritort F, Spigler R 2005 Rev. Mod. Phys. 77 137

  • [1] 王振华, 刘宗华. 复杂网络上的部分同步化: 奇异态、遥同步与集团同步. 物理学报, 2020, 69(8): 088902. doi: 10.7498/aps.69.20191973
    [2] 杨青林, 王立夫, 李欢, 余牧舟. 基于相对距离的复杂网络谱粗粒化方法. 物理学报, 2019, 68(10): 100501. doi: 10.7498/aps.68.20181848
    [3] 阮逸润, 老松杨, 王竣德, 白亮, 侯绿林. 一种改进的基于信息传播率的复杂网络影响力评估算法. 物理学报, 2017, 66(20): 208901. doi: 10.7498/aps.66.208901
    [4] 徐明明, 陆君安, 周进. 两层星形网络的特征值谱及同步能力. 物理学报, 2016, 65(2): 028902. doi: 10.7498/aps.65.028902
    [5] 董泽芹, 侯凤贞, 戴加飞, 刘新峰, 李锦, 王俊. 基于Kendall改进的同步算法癫痫脑网络分析. 物理学报, 2014, 63(20): 208705. doi: 10.7498/aps.63.208705
    [6] 刘金良. 具有随机节点结构的复杂网络同步研究. 物理学报, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
    [7] 梁义, 王兴元. 结点含时滞的具有零和非零时滞耦合的复杂网络混沌同步. 物理学报, 2013, 62(1): 018901. doi: 10.7498/aps.62.018901
    [8] 李雨珊, 吕翎, 刘烨, 刘硕, 闫兵兵, 常欢, 周佳楠. 复杂网络时空混沌同步的Backstepping设计. 物理学报, 2013, 62(2): 020513. doi: 10.7498/aps.62.020513
    [9] 柳爽, 吕翎, 李钢. 一类不确定复杂网络的滑模追踪同步. 物理学报, 2012, 61(16): 160507. doi: 10.7498/aps.61.160507
    [10] 杨浦, 郑志刚. 基于动力学同步的复杂网络结构识别速度研究. 物理学报, 2012, 61(12): 120508. doi: 10.7498/aps.61.120508
    [11] 王健安. 时变时滞耦合两个不同复杂网络的自适应广义同步. 物理学报, 2012, 61(2): 020509. doi: 10.7498/aps.61.020509
    [12] 吕天阳, 谢文艳, 郑纬民, 朴秀峰. 加权复杂网络社团的评价指标及其发现算法分析. 物理学报, 2012, 61(21): 210511. doi: 10.7498/aps.61.210511
    [13] 吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. 物理学报, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [14] 吕翎, 李钢, 徐文, 吕娜, 范鑫. 复Ginzburg-Landau方程时空混沌的网络同步与参量辨识. 物理学报, 2012, 61(6): 060507. doi: 10.7498/aps.61.060507
    [15] 曾长燕, 孙梅, 田立新. 基于自适应-脉冲控制方法实现时变耦合驱动-响应复杂网络的投影同步. 物理学报, 2010, 59(8): 5288-5292. doi: 10.7498/aps.59.5288
    [16] 卞秋香, 姚洪兴. 非线性耦合多重边赋权复杂网络的同步. 物理学报, 2010, 59(5): 3027-3034. doi: 10.7498/aps.59.3027
    [17] 李春彪, 胡文. 改进恒Lyapunov指数谱混沌系统的同步方法与特性研究. 物理学报, 2010, 59(2): 801-815. doi: 10.7498/aps.59.801
    [18] 王丹, 于灏, 井元伟, 姜囡, 张嗣瀛. 基于感知流量算法的复杂网络拥塞问题研究. 物理学报, 2009, 58(10): 6802-6808. doi: 10.7498/aps.58.6802
    [19] 吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 物理学报, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [20] 敬晓丹, 吕翎. 非线性耦合完全网络的时空混沌同步. 物理学报, 2009, 58(11): 7539-7543. doi: 10.7498/aps.58.7539
计量
  • 文章访问数:  6098
  • PDF下载量:  459
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-10-02
  • 修回日期:  2016-11-21
  • 刊出日期:  2017-03-05

/

返回文章
返回