搜索

x

留言板

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

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

基于相对距离的复杂网络谱粗粒化方法

杨青林 王立夫 李欢 余牧舟

引用本文:
Citation:

基于相对距离的复杂网络谱粗粒化方法

杨青林, 王立夫, 李欢, 余牧舟

A spectral coarse graining algorithm based on relative distance

Yang Qing-Lin, Wang Li-Fu, Li Huan, Yu Mu-Zhou
PDF
HTML
导出引用
  • 复杂网络的同步作为一种重要的网络动态特性, 在通信、控制、生物等领域起着重要的作用. 谱粗粒化方法是一种在保持原始网络的同步能力尽量不变情况下将大规模网络约简为小规模网络的算法. 此方法在对约简节点分类时是以每个节点对应特征向量分量间的绝对距离作为判断标准, 在实际运算中计算量大, 可执行性较差. 本文提出了一种以特征向量分量间相对距离作为分类标准的谱粗粒化改进算法, 能够使节点的合并更加合理, 从而更好地保持原始网络的同步能力. 通过经典的三种网络模型(BA无标度网络、ER随机网络、NW小世界网络)和27种不同类型实际网络的数值仿真分析表明, 本文提出的算法对比原来的算法能够明显改善网络的粗粒化效果, 并发现互联网、生物、社交、合作等具有明显聚类结构的网络在采用谱粗粒化算法约简后保持同步的能力要优于电力、化学等模糊聚类结构的网络.
    As a key approach to understanding complex systems (e.g. biological, physical, technological and social systems), the complex networks are ubiquitous in the whole world. Synchronization in complex networks is significant for a more in-depth understanding of the dynamic characteristics of the networks, where tremendous efforts have been devoted to their mechanism and applications in the last two decades. However, many real-world networks consist of hundreds of millions of nodes. Studying the synchronization of such large-scale complex networks often requires solving a huge number of coupled differential equations, which brings great difficulties to both computation and simulation. Recently, a spectral coarse graining approach was proposed to reduce the large-scale network into a smaller one while maintaining the synchronizability of the original network. The absolute distance between the eigenvector components corresponding to the minimum non-zero eigenvalues of the Laplacian matrix is used as a criterion for classifying the nodes without considering the influence of the relative distance between eigenvector components in an original spectral coarse graining method. By analyzing the mechanism of the spectral coarse graining procedure in preserving the synchronizability of complex networks, we prove that the ability of spectral coarse graining to preserve the network synchronizability is related to the relative distance of the eigenvector components corresponding to the merged nodes. Therefore, the original spectral coarse graining algorithm is not satisfactory enough in node clustering. In this paper, we propose an improved spectral coarse graining algorithm based on the relative distance between eigenvector components, in which we consider the relative distance between the components of eigenvectors for the eigenvalues of network coupling matrix while clustering the same or similar nodes in the network, thereby improving the clustering accuracy and maintaining the better synchronizability of the original network. Finally, numerical experiments on networks of ER random, BA scale-free, WS small-world and 27 different types of real-world networks are provided to demonstrate that the proposed algorithm can significantly improve the coarse graining effect of the network compared with the original algorithm. Furthermore, it is found that the networks with obvious clustering structure such as internet, biological, social and cooperative networks have better ability to maintain synchronization after reducing scale by spectral coarse-grained algorithm than the networks of fuzzy clustering structure such as power and chemical networks.
      通信作者: 王立夫, wlfk@qq.com
    • 基金项目: 河北省自然科学基金(批准号: F2016501023, F2017501041)、中央高校基本科研业务费(批准号: N172304030)和国家自然科学基金(批准号: 61402088)资助的课题.
      Corresponding author: Wang Li-Fu, wlfk@qq.com
    • Funds: Project supported by the Nature Science Foundation of Hebei Province, China (Grant Nos. F2016501023, F2017501041), Fundamental Research Funds for the Central Universities, China (Grant No. N172304030), and the National Natural Science Foundation of China (Grant No. 61402088).
    [1]

    Watts D J 2004 Annu. Rev. Sociol. 30 243Google Scholar

    [2]

    Pecora L M, Carroll Y L 1998 Phys. Rev. Lett. 80 2109Google Scholar

    [3]

    Fink K S, Johnson G, Carroll T, Mar D, Pecora L 2000 Phys. Rev. E 61 5080Google Scholar

    [4]

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

    [5]

    Belykh I V, Belykh V N 2004 Physica D 195 159Google Scholar

    [6]

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

    [7]

    Nishikawa T, Motter A E 2006 Physica D 224 77Google Scholar

    [8]

    Arenas A, Díaz-Guilera A, Kurths J, Moreno Y, Zhou C S 2008 Phys. Rep. 469 93Google Scholar

    [9]

    朱廷祥, 吴晔, 肖井华 2012 物理学报 61 040502Google Scholar

    Zhu T X, Wu Y, Xiao J H 2012 Acta Phys. Sin. 61 040502Google Scholar

    [10]

    孙娟, 李晓霞, 张金浩, 申玉卓, 李艳雨 2017 物理学报 66 188901Google Scholar

    Sun J, Li X X, Zhang J H, Shen Y Z, Li Y Y 2017 Acta Phys. Sin. 66 188901Google Scholar

    [11]

    Wei J, Wu X Q, Lu J A, Wei X 2017 Europhys. Lett. 120 20005Google Scholar

    [12]

    Chen C, Liu S, Shi X Q, Chaté H, Wu Y L 2017 Nature 542 210Google Scholar

    [13]

    王宇娟, 涂俐兰, 宋帅, 李宽洋 2018 物理学报 67 050504Google Scholar

    Wang Y J, Xu L L, Song S, Li K Y 2018 Acta Phys. Sin. 67 050504Google Scholar

    [14]

    郑广超, 刘崇新, 王琰 2018 物理学报 67 050502Google Scholar

    Zheng G C, Liu C X, Wang Y 2018 Acta Phys. Sin. 67 050502Google Scholar

    [15]

    Shen J, Tang L K 2018 Chin. Phys. B 27 100503Google Scholar

    [16]

    Ma X J, Huang L, Lai Y C, Wang Y, Zheng Z 2008 Chaos 18 043109Google Scholar

    [17]

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

    [18]

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

    [19]

    周建, 贾贞, 李科赞 2017 物理学报 66 060502Google Scholar

    Zhou J, Jia Z, Li K Z 2017 Acta Phys. Sin. 66 060502Google Scholar

    [20]

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

    [21]

    Wang P, Xu S 2017 Physica A 478 168Google Scholar

    [22]

    郭世泽, 陆哲明 2012 复杂网络基础理论(北京: 科学出版社)第183—187页

    Guo S Z, Lu Z M 2012 Complex Network Basic Theory (Beijing: Science Press) pp183-187 (in Chinese)

    [23]

    Barabási A L, Albert R 1999 Science 286 509Google Scholar

    [24]

    Erdös P, Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17

    [25]

    Watts D J, Strogatz S H 1998 Nature 393 440Google Scholar

    [26]

    Newman M E J, Watts D J 1999 Phys. Lett. A 263 341Google Scholar

    [27]

    Ahmed N, Rossi R A, Zhou R http://networkrepository.com/index.php [2018-9-14]

    [28]

    Kunegis J http://konect.uni-koblenz.de/ [2018-9-14]

    [29]

    罗筱如 2012 硕士学位论文 (重庆: 西南大学)

    Luo X R 2012 M.S. Thesis (Chongqing:Southwest University) (in Chinese)

    [30]

    Ai J, Zhao H, Kathleen M C, Su Z, Li H 2013 Chin. Phys. B 22 078902Google Scholar

    [31]

    Ravasz E, Somera A L, Mongru D A, Oltvai Z N, Barabási A L 2002 Science 297 1551Google Scholar

    [32]

    Xiong F, Wang X M, Cheng J J 2016 Chin. Phys. B 25 108904Google Scholar

  • 图 1  合并节点的过程

    Fig. 1.  The processing of merging nodes.

    图 2  15个节点并为14个节点的两种方案

    Fig. 2.  Two schemes of merging 15 nodes into 14 nodes.

    图 3  采用ISCG与ISCGR算法获得谱粗粒化网络对${\lambda _2}$的保持情况 (a) BA无标度网络; (b) ER随机网络; (c) NW小世界网络

    Fig. 3.  The maintaining of ${\lambda _2}$ obtained by using ISCG and ISCGR algorithms in coarse graining metwork: (a) BA network; (b) ER network; (c) NW network.

    图 4  采用ISCG算法与ISCGR算法获得谱粗粒化网络对${{{\lambda _N}} /{{\lambda _2}}}$的保持情况 (a) BA无标度网络; (b) ER随机网络; (c) NW小世界网络

    Fig. 4.  The maintaining of ${{{\lambda _N}} /{{\lambda _2}}}$ obtained by using ISCG and ISCGR algorithms in coarse graining metwork: (a) BA network; (b) ER network; (c) NW network.

    图 5  分别采用ISCG与ISCGR算法对实际网络进行粗粒化后保持${\lambda _2}$情况的对比图

    Fig. 5.  The maintaining of ${\lambda _2}$ obtained by using ISCG and ISCGR algorithms for real-world networks in coarse graining network.

    表 1  分别采用ISCG和ISCGR算法对实际网络约简后${\lambda _2}$的保持情况统计表

    Table 1.  The Statistics table of maintaining ${\lambda _2}$ obtained by using ISCG and ISCGR algorithms for some real-world networks in coarse graining network.

    种类网络节点文献Δλ2 (30%N)Δλ2 (20%N)Δλ2 (10%N)Δλ2 (2%N)
    ISCGISCGRISCGISCGRISCGISCGRISCGISCGR
    化学DD_g1327899[27]2.06%1.77%7.66%7.17%34.90%23.46%187%173%
    DD_g10467071646[27]1.40%1.31%7.27%6.62%42.92%17.81%191%94%
    合作netscience379914[27]0.13%0.13%1.05%1.05%5.79%5.46%49.74%39.41%
    ca-GrQc415813422[27]00000.03%0.03%0.34%0.20%
    社交ia-infect-dublin4102765[27]0.91%0.95%3.59%2.46%13.47%14.37%104%51%
    moreno_crime8291473[28]0.01%0.01%0.39%0.24%3.02%2.32%13.34%13.05%
    socfb-Sim81151832988[28]00000023.65%11.82%
    ia-email-univ11335451[27]00000.07%0.06%0.26%0.16%
    电力东北电网5870[29]8.14%5.78%24.36%18.63%54.65%54.65%
    IEEE162162280[29]2.35%2.10%16.94%8.68%27.70%25.65%113%113%
    IEEE145145422[29]0.85%0.80%4.14%3.16%17.85%14.22%240%230%
    生物diseasome5161188[27]0.22%0.11%0.79%0.67%2.58%2.02%33.45%15.82%
    互联网Route views647412572[28]00000.07%0.07%1.07%0.57%
    Wiki-vote8892914[27]0.02%0.01%0.07%0.05%0.17%0.17%0.61%0.49%
    技术bibd_12_44952951[27]0.02%0.01%0.20%0.06%0.80%0.41%29.02%19.73%
    G180019176[27]00000.27%0.19%0.56%0.55%
    GD00_c6381020[27]0.02%0.02%0.27%0.27%1.50%1.15%4.29%2.75%
    dwt_100510053808[27]2.17%0.49%4.25%1.61%23.93%10.83%129%92%
    dwt_5035032762[27]4.94%3.68%9.33%6.18%44.00%21.32%138%117%
    数学130bit5846058[27]0.01%00.02%0.01%0.68%0.36%1.51%1.15%
    ash6086081212[27]0.74%0.40%6.95%1.10%18.29%13.73%51.99%30.57%
    bibd_12_57927860[27]0.02%00.07%0.03%0.35%0.11%25.14%5.84%
    jagmesh310893136[27]0.31%0.10%1.44%1.13%16.86%9.25%192%127%
    frb45-21-1945386854[27]0.03‱00.23‱0.04‱0.51‱0.28‱1.39‱1.34‱
    kneser_6_2_16762017[27]0.03%0.01%0.16%0.13%1.83%0.44%81%30%
    EX15604368[27]000.03%0.03%3.08%0.41%123%26%
    随机G4310009990[27]000.01%00.13%0.11%0.95%0.50%
    下载: 导出CSV
  • [1]

    Watts D J 2004 Annu. Rev. Sociol. 30 243Google Scholar

    [2]

    Pecora L M, Carroll Y L 1998 Phys. Rev. Lett. 80 2109Google Scholar

    [3]

    Fink K S, Johnson G, Carroll T, Mar D, Pecora L 2000 Phys. Rev. E 61 5080Google Scholar

    [4]

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

    [5]

    Belykh I V, Belykh V N 2004 Physica D 195 159Google Scholar

    [6]

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

    [7]

    Nishikawa T, Motter A E 2006 Physica D 224 77Google Scholar

    [8]

    Arenas A, Díaz-Guilera A, Kurths J, Moreno Y, Zhou C S 2008 Phys. Rep. 469 93Google Scholar

    [9]

    朱廷祥, 吴晔, 肖井华 2012 物理学报 61 040502Google Scholar

    Zhu T X, Wu Y, Xiao J H 2012 Acta Phys. Sin. 61 040502Google Scholar

    [10]

    孙娟, 李晓霞, 张金浩, 申玉卓, 李艳雨 2017 物理学报 66 188901Google Scholar

    Sun J, Li X X, Zhang J H, Shen Y Z, Li Y Y 2017 Acta Phys. Sin. 66 188901Google Scholar

    [11]

    Wei J, Wu X Q, Lu J A, Wei X 2017 Europhys. Lett. 120 20005Google Scholar

    [12]

    Chen C, Liu S, Shi X Q, Chaté H, Wu Y L 2017 Nature 542 210Google Scholar

    [13]

    王宇娟, 涂俐兰, 宋帅, 李宽洋 2018 物理学报 67 050504Google Scholar

    Wang Y J, Xu L L, Song S, Li K Y 2018 Acta Phys. Sin. 67 050504Google Scholar

    [14]

    郑广超, 刘崇新, 王琰 2018 物理学报 67 050502Google Scholar

    Zheng G C, Liu C X, Wang Y 2018 Acta Phys. Sin. 67 050502Google Scholar

    [15]

    Shen J, Tang L K 2018 Chin. Phys. B 27 100503Google Scholar

    [16]

    Ma X J, Huang L, Lai Y C, Wang Y, Zheng Z 2008 Chaos 18 043109Google Scholar

    [17]

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

    [18]

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

    [19]

    周建, 贾贞, 李科赞 2017 物理学报 66 060502Google Scholar

    Zhou J, Jia Z, Li K Z 2017 Acta Phys. Sin. 66 060502Google Scholar

    [20]

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

    [21]

    Wang P, Xu S 2017 Physica A 478 168Google Scholar

    [22]

    郭世泽, 陆哲明 2012 复杂网络基础理论(北京: 科学出版社)第183—187页

    Guo S Z, Lu Z M 2012 Complex Network Basic Theory (Beijing: Science Press) pp183-187 (in Chinese)

    [23]

    Barabási A L, Albert R 1999 Science 286 509Google Scholar

    [24]

    Erdös P, Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17

    [25]

    Watts D J, Strogatz S H 1998 Nature 393 440Google Scholar

    [26]

    Newman M E J, Watts D J 1999 Phys. Lett. A 263 341Google Scholar

    [27]

    Ahmed N, Rossi R A, Zhou R http://networkrepository.com/index.php [2018-9-14]

    [28]

    Kunegis J http://konect.uni-koblenz.de/ [2018-9-14]

    [29]

    罗筱如 2012 硕士学位论文 (重庆: 西南大学)

    Luo X R 2012 M.S. Thesis (Chongqing:Southwest University) (in Chinese)

    [30]

    Ai J, Zhao H, Kathleen M C, Su Z, Li H 2013 Chin. Phys. B 22 078902Google Scholar

    [31]

    Ravasz E, Somera A L, Mongru D A, Oltvai Z N, Barabási A L 2002 Science 297 1551Google Scholar

    [32]

    Xiong F, Wang X M, Cheng J J 2016 Chin. Phys. B 25 108904Google Scholar

  • [1] 谭索怡, 祁明泽, 吴俊, 吕欣. 复杂网络链路可预测性: 基于特征谱视角. 物理学报, 2020, 69(8): 088901. doi: 10.7498/aps.69.20191817
    [2] 王振华, 刘宗华. 复杂网络上的部分同步化: 奇异态、遥同步与集团同步. 物理学报, 2020, 69(8): 088902. doi: 10.7498/aps.69.20191973
    [3] 孙娟, 李晓霞, 张金浩, 申玉卓, 李艳雨. 多层单向耦合星形网络的特征值谱及同步能力分析. 物理学报, 2017, 66(18): 188901. doi: 10.7498/aps.66.188901
    [4] 周建, 贾贞, 李科赞. 复杂网络谱粗粒化方法的改进算法. 物理学报, 2017, 66(6): 060502. doi: 10.7498/aps.66.060502
    [5] 梁义, 王兴元. 结点含时滞的具有零和非零时滞耦合的复杂网络混沌同步. 物理学报, 2013, 62(1): 018901. doi: 10.7498/aps.62.018901
    [6] 任卓明, 刘建国, 邵凤, 胡兆龙, 郭强. 复杂网络中最小K-核节点的传播能力分析. 物理学报, 2013, 62(10): 108902. doi: 10.7498/aps.62.108902
    [7] 刘金良. 具有随机节点结构的复杂网络同步研究. 物理学报, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
    [8] 李雨珊, 吕翎, 刘烨, 刘硕, 闫兵兵, 常欢, 周佳楠. 复杂网络时空混沌同步的Backstepping设计. 物理学报, 2013, 62(2): 020513. doi: 10.7498/aps.62.020513
    [9] 冯聪, 邹艳丽, 韦芳琼. 簇间连接方式不同的簇网络的同步过程研究. 物理学报, 2013, 62(7): 070506. doi: 10.7498/aps.62.070506
    [10] 王丹, 郝彬彬. 一类高聚类系数的加权无标度网络及其同步能力分析. 物理学报, 2013, 62(22): 220506. doi: 10.7498/aps.62.220506
    [11] 梁义, 王兴元. 基于低阶矩阵最大特征值的复杂网络牵制混沌同步. 物理学报, 2012, 61(3): 038901. doi: 10.7498/aps.61.038901
    [12] 柳爽, 吕翎, 李钢. 一类不确定复杂网络的滑模追踪同步. 物理学报, 2012, 61(16): 160507. doi: 10.7498/aps.61.160507
    [13] 杨浦, 郑志刚. 基于动力学同步的复杂网络结构识别速度研究. 物理学报, 2012, 61(12): 120508. doi: 10.7498/aps.61.120508
    [14] 王健安. 时变时滞耦合两个不同复杂网络的自适应广义同步. 物理学报, 2012, 61(2): 020509. doi: 10.7498/aps.61.020509
    [15] 吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. 物理学报, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [16] 王丹, 井元伟, 郝彬彬. 扩展HK网络结构与同步能力的研究. 物理学报, 2012, 61(22): 220511. doi: 10.7498/aps.61.220511
    [17] 王丹, 井元伟, 郝彬彬. 加权方式对网络同步能力的影响. 物理学报, 2012, 61(17): 170513. doi: 10.7498/aps.61.170513
    [18] 曾长燕, 孙梅, 田立新. 基于自适应-脉冲控制方法实现时变耦合驱动-响应复杂网络的投影同步. 物理学报, 2010, 59(8): 5288-5292. doi: 10.7498/aps.59.5288
    [19] 吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 物理学报, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [20] 马晓娟, 王延, 郑志刚. 叶子节点对于网络同步能力影响的研究. 物理学报, 2009, 58(7): 4426-4430. doi: 10.7498/aps.58.4426
计量
  • 文章访问数:  6588
  • PDF下载量:  66
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-10-15
  • 修回日期:  2019-03-14
  • 上网日期:  2019-05-01
  • 刊出日期:  2019-05-20

/

返回文章
返回