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
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
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.
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.
[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
2010, Vol. 27 
