-
复杂网络的同步作为一种重要的网络动态特性, 在通信、控制、生物等领域起着重要的作用. 谱粗粒化方法是一种在保持原始网络的同步能力尽量不变情况下将大规模网络约简为小规模网络的算法. 此方法在对约简节点分类时是以每个节点对应特征向量分量间的绝对距离作为判断标准, 在实际运算中计算量大, 可执行性较差. 本文提出了一种以特征向量分量间相对距离作为分类标准的谱粗粒化改进算法, 能够使节点的合并更加合理, 从而更好地保持原始网络的同步能力. 通过经典的三种网络模型(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.
-
Keywords:
- complex network /
- synchronizability /
- spectral coarse graining /
- relative distance
[1] Watts D J 2004 Annu. Rev. Sociol. 30 243
Google Scholar
[2] Pecora L M, Carroll Y L 1998 Phys. Rev. Lett. 80 2109
Google Scholar
[3] Fink K S, Johnson G, Carroll T, Mar D, Pecora L 2000 Phys. Rev. E 61 5080
Google Scholar
[4] Wang X F, Chen G R 2002 Int. J. Bifurcat. Chaos 12 187
Google Scholar
[5] Belykh I V, Belykh V N 2004 Physica D 195 159
Google Scholar
[6] Motter A E, Zhou C S, Kurths J 2005 Phys. Rev. E 71 016116
Google Scholar
[7] Nishikawa T, Motter A E 2006 Physica D 224 77
Google Scholar
[8] Arenas A, Díaz-Guilera A, Kurths J, Moreno Y, Zhou C S 2008 Phys. Rep. 469 93
Google Scholar
[9] 朱廷祥, 吴晔, 肖井华 2012 物理学报 61 040502
Google Scholar
Zhu T X, Wu Y, Xiao J H 2012 Acta Phys. Sin. 61 040502
Google Scholar
[10] 孙娟, 李晓霞, 张金浩, 申玉卓, 李艳雨 2017 物理学报 66 188901
Google Scholar
Sun J, Li X X, Zhang J H, Shen Y Z, Li Y Y 2017 Acta Phys. Sin. 66 188901
Google Scholar
[11] Wei J, Wu X Q, Lu J A, Wei X 2017 Europhys. Lett. 120 20005
Google Scholar
[12] Chen C, Liu S, Shi X Q, Chaté H, Wu Y L 2017 Nature 542 210
Google Scholar
[13] 王宇娟, 涂俐兰, 宋帅, 李宽洋 2018 物理学报 67 050504
Google Scholar
Wang Y J, Xu L L, Song S, Li K Y 2018 Acta Phys. Sin. 67 050504
Google Scholar
[14] 郑广超, 刘崇新, 王琰 2018 物理学报 67 050502
Google Scholar
Zheng G C, Liu C X, Wang Y 2018 Acta Phys. Sin. 67 050502
Google Scholar
[15] Shen J, Tang L K 2018 Chin. Phys. B 27 100503
Google Scholar
[16] Ma X J, Huang L, Lai Y C, Wang Y, Zheng Z 2008 Chaos 18 043109
Google Scholar
[17] Gfeller D, Rios P D L 2007 Phys. Rev. Lett. 99 038701
Google Scholar
[18] Gfeller D, Rios P D L 2008 Phys. Rev. Lett. 100 174104
Google Scholar
[19] 周建, 贾贞, 李科赞 2017 物理学报 66 060502
Google Scholar
Zhou J, Jia Z, Li K Z 2017 Acta Phys. Sin. 66 060502
Google Scholar
[20] Chen J, Lu J A, Lu X F, Wu X Q, Chen G R 2013 Commun. Nonlinear Sci. 18 3036
Google Scholar
[21] Wang P, Xu S 2017 Physica A 478 168
Google 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 509
Google 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 440
Google Scholar
[26] Newman M E J, Watts D J 1999 Phys. Lett. A 263 341
Google 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 078902
Google Scholar
[31] Ravasz E, Somera A L, Mongru D A, Oltvai Z N, Barabási A L 2002 Science 297 1551
Google Scholar
[32] Xiong F, Wang X M, Cheng J J 2016 Chin. Phys. B 25 108904
Google Scholar
-
图 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) ISCG ISCGR ISCG ISCGR ISCG ISCGR ISCG ISCGR 化学 DD_g1 327 899 [27] 2.06% 1.77% 7.66% 7.17% 34.90% 23.46% 187% 173% DD_g1046 707 1646 [27] 1.40% 1.31% 7.27% 6.62% 42.92% 17.81% 191% 94% 合作 netscience 379 914 [27] 0.13% 0.13% 1.05% 1.05% 5.79% 5.46% 49.74% 39.41% ca-GrQc 4158 13422 [27] 0 0 0 0 0.03% 0.03% 0.34% 0.20% 社交 ia-infect-dublin 410 2765 [27] 0.91% 0.95% 3.59% 2.46% 13.47% 14.37% 104% 51% moreno_crime 829 1473 [28] 0.01% 0.01% 0.39% 0.24% 3.02% 2.32% 13.34% 13.05% socfb-Sim81 1518 32988 [28] 0 0 0 0 0 0 23.65% 11.82% ia-email-univ 1133 5451 [27] 0 0 0 0 0.07% 0.06% 0.26% 0.16% 电力 东北电网 58 70 [29] 8.14% 5.78% 24.36% 18.63% 54.65% 54.65% — — IEEE162 162 280 [29] 2.35% 2.10% 16.94% 8.68% 27.70% 25.65% 113% 113% IEEE145 145 422 [29] 0.85% 0.80% 4.14% 3.16% 17.85% 14.22% 240% 230% 生物 diseasome 516 1188 [27] 0.22% 0.11% 0.79% 0.67% 2.58% 2.02% 33.45% 15.82% 互联网 Route views 6474 12572 [28] 0 0 0 0 0.07% 0.07% 1.07% 0.57% Wiki-vote 889 2914 [27] 0.02% 0.01% 0.07% 0.05% 0.17% 0.17% 0.61% 0.49% 技术 bibd_12_4 495 2951 [27] 0.02% 0.01% 0.20% 0.06% 0.80% 0.41% 29.02% 19.73% G1 800 19176 [27] 0 0 0 0 0.27% 0.19% 0.56% 0.55% GD00_c 638 1020 [27] 0.02% 0.02% 0.27% 0.27% 1.50% 1.15% 4.29% 2.75% dwt_1005 1005 3808 [27] 2.17% 0.49% 4.25% 1.61% 23.93% 10.83% 129% 92% dwt_503 503 2762 [27] 4.94% 3.68% 9.33% 6.18% 44.00% 21.32% 138% 117% 数学 130bit 584 6058 [27] 0.01% 0 0.02% 0.01% 0.68% 0.36% 1.51% 1.15% ash608 608 1212 [27] 0.74% 0.40% 6.95% 1.10% 18.29% 13.73% 51.99% 30.57% bibd_12_5 792 7860 [27] 0.02% 0 0.07% 0.03% 0.35% 0.11% 25.14% 5.84% jagmesh3 1089 3136 [27] 0.31% 0.10% 1.44% 1.13% 16.86% 9.25% 192% 127% frb45-21-1 945 386854 [27] 0.03‱ 0 0.23‱ 0.04‱ 0.51‱ 0.28‱ 1.39‱ 1.34‱ kneser_6_2_1 676 2017 [27] 0.03% 0.01% 0.16% 0.13% 1.83% 0.44% 81% 30% EX1 560 4368 [27] 0 0 0.03% 0.03% 3.08% 0.41% 123% 26% 随机 G43 1000 9990 [27] 0 0 0.01% 0 0.13% 0.11% 0.95% 0.50% 
下载: 导出CSV
-
[1] Watts D J 2004 Annu. Rev. Sociol. 30 243
Google Scholar
[2] Pecora L M, Carroll Y L 1998 Phys. Rev. Lett. 80 2109
Google Scholar
[3] Fink K S, Johnson G, Carroll T, Mar D, Pecora L 2000 Phys. Rev. E 61 5080
Google Scholar
[4] Wang X F, Chen G R 2002 Int. J. Bifurcat. Chaos 12 187
Google Scholar
[5] Belykh I V, Belykh V N 2004 Physica D 195 159
Google Scholar
[6] Motter A E, Zhou C S, Kurths J 2005 Phys. Rev. E 71 016116
Google Scholar
[7] Nishikawa T, Motter A E 2006 Physica D 224 77
Google Scholar
[8] Arenas A, Díaz-Guilera A, Kurths J, Moreno Y, Zhou C S 2008 Phys. Rep. 469 93
Google Scholar
[9] 朱廷祥, 吴晔, 肖井华 2012 物理学报 61 040502
Google Scholar
Zhu T X, Wu Y, Xiao J H 2012 Acta Phys. Sin. 61 040502
Google Scholar
[10] 孙娟, 李晓霞, 张金浩, 申玉卓, 李艳雨 2017 物理学报 66 188901
Google Scholar
Sun J, Li X X, Zhang J H, Shen Y Z, Li Y Y 2017 Acta Phys. Sin. 66 188901
Google Scholar
[11] Wei J, Wu X Q, Lu J A, Wei X 2017 Europhys. Lett. 120 20005
Google Scholar
[12] Chen C, Liu S, Shi X Q, Chaté H, Wu Y L 2017 Nature 542 210
Google Scholar
[13] 王宇娟, 涂俐兰, 宋帅, 李宽洋 2018 物理学报 67 050504
Google Scholar
Wang Y J, Xu L L, Song S, Li K Y 2018 Acta Phys. Sin. 67 050504
Google Scholar
[14] 郑广超, 刘崇新, 王琰 2018 物理学报 67 050502
Google Scholar
Zheng G C, Liu C X, Wang Y 2018 Acta Phys. Sin. 67 050502
Google Scholar
[15] Shen J, Tang L K 2018 Chin. Phys. B 27 100503
Google Scholar
[16] Ma X J, Huang L, Lai Y C, Wang Y, Zheng Z 2008 Chaos 18 043109
Google Scholar
[17] Gfeller D, Rios P D L 2007 Phys. Rev. Lett. 99 038701
Google Scholar
[18] Gfeller D, Rios P D L 2008 Phys. Rev. Lett. 100 174104
Google Scholar
[19] 周建, 贾贞, 李科赞 2017 物理学报 66 060502
Google Scholar
Zhou J, Jia Z, Li K Z 2017 Acta Phys. Sin. 66 060502
Google Scholar
[20] Chen J, Lu J A, Lu X F, Wu X Q, Chen G R 2013 Commun. Nonlinear Sci. 18 3036
Google Scholar
[21] Wang P, Xu S 2017 Physica A 478 168
Google 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 509
Google 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 440
Google Scholar
[26] Newman M E J, Watts D J 1999 Phys. Lett. A 263 341
Google 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 078902
Google Scholar
[31] Ravasz E, Somera A L, Mongru D A, Oltvai Z N, Barabási A L 2002 Science 297 1551
Google Scholar
[32] Xiong F, Wang X M, Cheng J J 2016 Chin. Phys. B 25 108904
Google Scholar
下载:
计量
- 文章访问数: 8142
- PDF下载量: 74
- 被引次数: 0
