Chin. Phys. Lett.  2010, Vol. 27 Issue (7): 078902    DOI: 10.1088/0256-307X/27/7/078902
CROSS-DISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY |
Natural Connectivity of Complex Networks

WU Jun1,2, Mauricio Barahona2,3, TAN Yue-Jin1, DENG Hong-Zhong1

1College of Information Systems and Management, National University of Defense Technology, Changsha 410073 2Institute for Mathematical Sciences, Imperial College London, London SW7 2PG, United Kingdom 3Department of Bioengineering, Imperial College London, London SW7 2AZ, United Kingdom
Cite this article:   
WU Jun, Mauricio Barahona, TAN Yue-Jin et al  2010 Chin. Phys. Lett. 27 078902
Download: PDF(335KB)  
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

The concept of natural connectivity is reported as a robustness measure of complex networks. The natural connectivity has a clear physical meaning and a simple mathematical formulation. It is shown that the natural connectivity can be derived mathematically from the graph spectrum as an average eigenvalue and that it changes strictly monotonically with the addition or deletion of edges. By comparing the natural connectivity with other typical robustness measures within a scenario of edge elimination, it is demonstrated that the natural connectivity has an acute discrimination which agrees with our intuition.

Keywords: 89.75.Hc      89.75.Fb     
Received: 22 April 2010      Published: 28 June 2010
PACS:  89.75.Hc (Networks and genealogical trees)  
  89.75.Fb (Structures and organization in complex systems)  
TRENDMD:   
URL:  
https://cpl.iphy.ac.cn/10.1088/0256-307X/27/7/078902       OR      https://cpl.iphy.ac.cn/Y2010/V27/I7/078902
Service
E-mail this article
E-mail Alert
RSS
Articles by authors
WU Jun
Mauricio Barahona
TAN Yue-Jin
DENG Hong-Zhong
[1] Albert R, Jeong H and Barabási A-L 2000 Nature 406 378
[2] Holme P, Kim B J, Yoon C N and Han S K 2002 Phys. Rev. E 65 056109
[3] Bollobás B and Riordan O 2003 Internet Math. 1 1
[4] Chi L P, Yang C B and Cai X 2006 Chin. Phys. Lett. 23 263
[5] Sun K and Ouyang Q 2001 Chin. Phys. Lett. 18 452
[6] Wang J W and Rong L L 2008 Chin. Phys. Lett. 25 3826
[7] Hu B, Li F and Zhou H S 2009 Chin. Phys. Lett. 26 128901
[8] Liu J G, Wang Z T and Dang Y Z 2006 Mod. Phys. Lett. B 20 815
[9] Albert R and Barabási A-L 2002 Rev. Mod. Phys. 74 47
[10] Newman M E J 2003 SIAM Rev. 45 167
[11] Wang X F 2002 Int. J. Bifurcation & Chaos 12 885
[12] Frank H and Frisch I T 1970 IEEE Trans. Commun. Tech. 18 567
[13] Chvatal V 1973 Discr. Math. 5 215
[14] Jung H A 1978 J. Combin. Theor. B 24 125
[15] Barefoot C A, Entringer R and Swart H 1987 J. Combin. Math. Combin. Comput. 1 13
[16] Cozzens M, Moazzami D and Stueckle S 1995 Seventh International Conference on the Theory and Applications of Graphs (New York: Wiley) p 1111
[17] Kratsch D 1997 Discr. App. Math. 77 259
[18] Fiedler M 1973 Czech. Math. J. 23 298
[19] Bollobás B 1985 Random Graphs (New York: Academic)
[20] Cohen R, Erez K, ben-Avraham D and Havlin S 2001 Phys. Rev. Lett. 86 3682
[21] Cohen R, Erez K, ben-Avraham D and Havlin S 2000 Phys. Rev. Lett. 85 4626
[22] Callaway D S, Newman M E J, Strogatz S H and Watts D J 2000 Phys. Rev. Lett. 85 5468
[23] Wu J, Deng H Z, Tan Y J, Li Y and Zhu D Z 2007 Mod. Phys. Lett. B 21 1007
[24] Wu J, Deng H Z, Tan Y J and Zhu D Z 2007 J. Phys. A 40 2665
[25] Wu J, Deng H Z, Tan Y J and Li Y 2007 Chin. Phys. Lett. 24 2138
[26] Estrada E 2000 Chem. Phys. Lett. 319 713
[27] Estrada E and Rodríguez-Velázquez J A 2005 Phys. Rev. E 71 056103
[28] Estrada E and Rodríguez-Velázquez J A 2005 Phys. Rev. E 72 046105
[29] Cvetkovic D M, Doob M and Sachs H 1979 Spectra of Graphs (New York: Academic)
[30] Barabási A L and Albert R 1999 Science 286 509
Related articles from Frontiers Journals
[1] QI Kai,TANG Ming**,CUI Ai-Xiang,FU Yan. The Slow Dynamics of the Zero-Range Process in the Framework of the Traps Model[J]. Chin. Phys. Lett., 2012, 29(5): 078902
[2] ZHAO Qing-Bai,ZHANG Xiao-Fei,SUI Dan-Ni,ZHOU Zhi-Jin,CHEN Qi-Cai,TANG Yi-Yuan,**. The Efficiency of a Small-World Functional Brain Network[J]. Chin. Phys. Lett., 2012, 29(4): 078902
[3] CHEN Duan-Bing**,GAO Hui. An Improved Adaptive model for Information Recommending and Spreading[J]. Chin. Phys. Lett., 2012, 29(4): 078902
[4] LIU Xu,XIE Zheng,YI Dong-Yun**. Community Detection by Neighborhood Similarity[J]. Chin. Phys. Lett., 2012, 29(4): 078902
[5] LI Ping, ZHANG Jie, XU Xiao-Ke, SMALL Michael. Dynamical Influence of Nodes Revisited: A Markov Chain Analysis of Epidemic Process on Networks[J]. Chin. Phys. Lett., 2012, 29(4): 078902
[6] XIE Zheng, YI Dong-Yun, OUYANG Zhen-Zheng, LI Dong. Hyperedge Communities and Modularity Reveal Structure for Documents[J]. Chin. Phys. Lett., 2012, 29(3): 078902
[7] TIAN Liang, LIN Min. Relaxation of Evolutionary Dynamics on the Bethe Lattice[J]. Chin. Phys. Lett., 2012, 29(3): 078902
[8] REN Xue-Zao, YANG Zi-Mo, WANG Bing-Hong, ZHOU Tao. Mandelbrot Law of Evolving Networks[J]. Chin. Phys. Lett., 2012, 29(3): 078902
[9] ZHU Zi-Qi, JIN Xiao-Ling, HUANG Zhi-Long. Search for Directed Networks by Different Random Walk Strategies[J]. Chin. Phys. Lett., 2012, 29(3): 078902
[10] SUN Mei, CHEN Ying, CAO Long, WANG Xiao-Fang. Adaptive Third-Order Leader-Following Consensus of Nonlinear Multi-agent Systems with Perturbations[J]. Chin. Phys. Lett., 2012, 29(2): 078902
[11] CHENG Hong-Yan, YANG Jun-Zhong** . Organization of the Strategy Pattern in Evolutionary Prisoner's Dilemma Game on Scale-Free Networks[J]. Chin. Phys. Lett., 2011, 28(6): 078902
[12] SUN Wei-Gang, , CAO Jian-Ting, WANG Ru-Bin** . Approach of Complex Networks for the Determination of Brain Death[J]. Chin. Phys. Lett., 2011, 28(6): 078902
[13] LI Jun, WU Jun**, LI Yong, DENG Hong-Zhong, TAN Yue-Jin** . Optimal Attack Strategy in Random Scale-Free Networks Based on Incomplete Information[J]. Chin. Phys. Lett., 2011, 28(6): 078902
[14] SHANG Yi-Lun . Local Natural Connectivity in Complex Networks[J]. Chin. Phys. Lett., 2011, 28(6): 078902
[15] JIANG Hui-Jun, WU Hao, HOU Zhong-Huai** . Explosive Synchronization and Emergence of Assortativity on Adaptive Networks[J]. Chin. Phys. Lett., 2011, 28(5): 078902
Viewed
Full text


Abstract