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 |
|
|
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)
|
|
|
|
|
[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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|