Abstract：The effects of three typical structural properties on invulnerability of complex network topologies are investigated based on the natural connectivity. The effect of degree distribution on invulnerability of complex network topologies is studied by generating complex networks with various degree distributions using mixing preferential attachment model. It is shown that, with the same condition, the more heterogeneous the degree distribution is, the better the invulnerability is. The effect of small-world property on invulnerability of complex network topologies is studied by degree-preserve rewirings and freedom rewirings from regular ring lattices, respectively. It is shown that there is no certain correlation between small-world property and invulnerability. The effect of degree correlation on invulnerability of complex network topologies is studied by degree-preserve-assortativerewirings and degree-preserve-disassortativerewirings, respectively. It is shown that assortative networks are more invulnerable than disassortative networks.
吴俊, 谭索怡, 谭跃进, 邓宏钟. 基于自然连通度的复杂网络抗毁性分析[J]. 复杂系统与复杂性科学, 2014, 11(1): 77-86.
WU Jun, TAN Suo-yi, TAN Yue-Jin, DENG Hong-Zhong. Analysis of Invulnerability in Complex Networks Based on Natural Connectivity[J]. Complex Systems and Complexity Science, 2014, 11(1): 77-86.
[1] 方锦清, 汪小帆, 刘曾荣. 略论复杂性问题和非线性复杂网络系统的研究[J]. 科技导报, 2004, 22（2):9-12,64. Fang Jinqing, Wang Xiaofan, Liu Zengrong. On the study of complexity and nonlinear complex networks[J]. Science & Technology Review, 2004, 22（2):9-12, 64. [2] 吴金闪, 狄增如. 从统计物理学看复杂网络研究[J]. 物理学进展, 2004, 24（1):18-46. Wu Jinshan, Di Zengru. Complex networks in statistical physics[J]. Progress in Physics, 2004, 24（1):18-46. [3] 郑金连, 狄增如. 复杂网络研究与复杂现象[J]. 系统辩证学报, 2005, 13（4):8-13. Zheng Jinlian, Di Zengru. A brief discussion on complex networks and complexity[J]. Journal of Systemic Dialectics, 2005, 13（4):8-13. [4] 陈禹. 人类对于网络的认识的新发展[J]. 系统辩证学报, 2005, 13（4):18-22. Chen Yu. New progress on the network for the human being[J]. Journal of Systemic Dialectics, 13（4):18-22. [5] 史定华. 网络——探索复杂性的新途径[J]. 系统工程学报, 2005, 20（2):115-119. Shi Dinghua. Networks—a new approach for exploring complexity[J]. Journal of System Engineering, 2005, 20（2):115-119. [6] 汪秉宏, 周涛, 何大韧. 统计物理学与复杂系统研究最新发展趋势分析[J]. 中国基础科学, 2005, 7（3):37-43. Wang Binghong, Zhou Tao, He Daren. The trend of recent research on statistical physics and complex systems[J]. China Basic Science, 2005, 7（3):37-43. [7] 汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用[M]. 北京:清华大学出版社, 2006. [8] 谭跃进, 吴俊, 邓宏钟. 复杂网络抗毁性研究综述[J]. 系统工程, 2006, 24（11):1-5. Tan Yuejin, Wu Jun, Deng Hongzhong. Invulnerability of complex networks:asurvey[J]. System Engineering, 2006, 24（11):1-5. [9] 吴俊, 谭跃进. 复杂网络抗毁性测度研究[J]. 系统工程学报, 2005, 20（2):128-131. Wu Jun, Tan Yuejin. Study on measure of complex network invulnerability[J]. Journal of System Engineering, 2005, 20（2):128-131. [10] 谭跃进, 吕欣, 吴俊, 等. 复杂网络抗毁性研究若干问题的思考[J]. 系统工程理论与实践, 2008, 28（Suppl):116-120. Tan Yuejin, Lü Xin, Wu Jun, et al. On the invulnerability research of complex networks[J]. Systems Engineering-Theory & Practice, 2008, 28（Suppl):116-120. [11] Frank H, Frisch I T. Analysis and design of survivable network[J]. IEEE Transaction on Communication Technology, 1970, 18 （5):567-662 [12] Chvatal V. Tough graphs and hamiltonian circuits[J]. Discrete Mathematics, 1973, 5（3):215-228. [13] Barefoot C A, Entringer R, Swart H. Vulnerability in graphs-a comparative survey[J]. J Combin Math Combin Comput, 1987, 1（2):13-22. [14] Cozzens M, Moazzami D, Stueckle S. The tenacity of a graph[C]//Seventh International Conference on the Theory and Applications of Graphs. New York:Wiley, 1995:1111-1122. [15] Jung H A.On a class of posets and the corresponding comparability graphs[J]. J Combin Theory B, 1978, 24（2):125-133. [16] Bassalygo L A, Pinsker M S. The complexity of an optimal non-blocking commutation scheme without reorganization[J]. Problemy Peredaci Informacii, 1973, 9（1):84-87. [17] 许进. 系统的核与核度理论Ⅱ——优化设计与可靠通讯网络[J]. 系统工程学报, 1994, 9（1):1-11. Xu Jin. The core and coritivity of a system Ⅱ—— optimization design and reliable communication network[J]. Journal of System Engineering, 1994, 9（1):1-11. [18] 许进, 席酉民. 系统的核与核度[J]. 系统科学与数学, 1993, 13（2):102-110. Xu Jin, Xi Youmin. The core and coritivity of a system[J]. System and Mathematics, 1993, 13（2):102-110 [19] Kratsch D. Measuring the vulnerability for classes of intersection graphs[J]. Discr App Math, 1997, 77（3):259-270. [20] 周涛, 柏文洁, 汪秉宏, 等. 复杂网络研究概述[J]. 物理, 2005, 34（1):31-36. Zhou Tao, Bai Wenjie, Wang Binghong,et al. A brief review of complex networks[J]. Physics, 2005, 34（1):31-36. [21] Albert R, Jeong H, Barabasi A L. Error and attack tolerance of complex networks[J]. Nature, 2000, 406（6794):378-382. [22] Callaway D S, Newman M E J, Strogatz S H, et al. Network robustness and fragility:percolation on random graphs[J]. Phys Rev Lett, 2000, 85（25):5468-5471. [23] Cohen R, Erez K, ben-Avraham D,et al. Resilience of the internet to random breakdowns[J]. Phys Rev Lett, 2000, 85（21):4626-4628. [24] Cohen R, Erez K, ben-Avraham D, et al. Breakdown of the internet under intentional attack[J]. Phys Rev Lett, 2001, 86（16):3682-3685 [25] Holme P, Kim B J, Yoon C N,et al. Attack vulnerability of complex networks[J]. Phys Rev E, 2002, 65（5):056109 [26] Zhou T, WANG B H. Catastrophes in scale-free networks[J]. Chin Phys Lett, 2005, 22（5):1072-1075. [27] Gallos L K, Cohen R, Argyrakis P, et al. Stability and topology of scale-free networks under attack and defense srategies[J]. Phys Rev Lett, 2005, 94（18):188701. [28] Wang B, Tang H W, Guo C H, et al. Entropy optimization of scale-free networks' robustness to random failures[J]. Physica A, 2006, 363（2):591-596. [29] Liu J G, Wang Z T, Dang Y Z. Optimization of scale-free network for random failures[J]. Mod Phys Lett B, 2006, 20（14):815-820. [30] Wu J, Tan Y L, Deng H Z, et al. Relationship between degree-rank distributions and degree distributions of complex networks[J]. Physica A, 2007, 383（2):745-752. [31] Wang J W, Rong L L, Zhang L, et al. Attack vulnerability of scale-free networks due to cascading failures[J]. Physica A, 2008, 387（26):6671-6678. [32] Yin Y P, Zhang D M, Tan J, et al. Multiple partial attacks on complex networks[J]. Chin Phys Lett, 2008, 25（2):769-772. [33] Wu J, Barahona M, Tan Y J, et al. Natural connectivity of complex networks[J]. Chin Phys Lett, 2010, 27（7):078902. [34] Wu J, Barahona M, Tan Y J, et al. Spectral measure of structural robustness in complex networks[J]. IEEE Transactions on Systems Man and Cybernetics Part A, 2011, 41（6):1244-1252. [35] Estrada E, Hatano N, Benzi M. The physics of communicability in complex networks[J]. Phys Rep, 2012, 514（3):89-119. [36] Shang Y L. Perturbation results for the Estrada index in weighted networks[J]. J Phys A, 2011, 44（7):075003. [37] Shang Y L. Local natural connectivity in complex networks[J]. Chin Phys Lett, 2011, 28（6):068903. [38] Estrada E, Rodriguez-Velazquez J A. Subgraph centrality in complex networks[J]. Phys Rev E, 2005, 71（5):056103. [39] Estrada E, Rodriguez-Velazquez J A. Spectral measures of bipartivity in complex networks[J]. Phys Rev E, 2005, 72（4):046105. [40] Cvetković D M, Doob M, Sachs H. Spectra of Graphs[M]. New York:Academic Press, 1979. [41] Wu J, Barahona M, Tan Y J, et al. Robustness of regularring lattices based on natural connectivity[J]. International Journal of Systems Science, 2011, 42（7):1085-1092. [42] Wu J, Barahona M, Tan Y J, et al. Robustness of random graphs based on graph spectra[J]. Chaos, 2012, 22（4):043101. [43] Liu Z H, Lai Y C, Ye N, et al. Connectivity distribution and attack tolerance of general networks with both preferential and random attachments[J]. Phys Lett A, 2002, 303（5/6):337-344. [44] Wu J, Tan Y J, Deng H Z, et al. Normalized entropy of rank distribution:a novel measure of heterogeneity of complex networks[J]. Chin Phys, 2007, 16（6):1576-1580. [45] Latora V, Marchiori M. Efficient behavior of small-world networks[J]. Phys Rev Lett, 2001, 87（19) 198701. [46] Barabási A-L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286（5439):509-512.
