摘要In network theory, a complex network represents a system whose evolving structure and dynamic behavior contribute to its robustness. The natural connectivity is recently proposed as a spectral measure to characterize the robustness of complex networks. We decompose the natural connectivity of a network as local natural connectivity of its connected components and quantify their contributions to the network robustness. In addition, we compare the natural connectivity of a network with that of an induced subgraph of it based on interlacing theorems. As an application, we derive an inequality for eigenvalues of Erdös-Rényi random graphs.
Abstract：In network theory, a complex network represents a system whose evolving structure and dynamic behavior contribute to its robustness. The natural connectivity is recently proposed as a spectral measure to characterize the robustness of complex networks. We decompose the natural connectivity of a network as local natural connectivity of its connected components and quantify their contributions to the network robustness. In addition, we compare the natural connectivity of a network with that of an induced subgraph of it based on interlacing theorems. As an application, we derive an inequality for eigenvalues of Erdös-Rényi random graphs.
[1] Albert R and Barabási A L 2002 Rev. Mod. Phys. 74 47
[2] Amaral L A N and Uzzi B 2007 Management Sci. 53 1033
[3] Boccaletti S, Latora V, Moreno Y, Chavez M and Hwang D U 2006 Phys. Rep. 424 175
[4] Newman M E J 2003 SIAM Rev. 45 167
[5] Albert R, Jeong H and Barabási A L 2000 Nature 406 378
[6] Bollobás B and Riordan O 2004 Internet Math. 1 1
[7] Chi L P, Yang C B and Cai X 2006 Chin. Phys. Lett. 23 263
[8] Hu B, Li F and Zhou H S 2009 Chin. Phys. Lett. 26 128901
[9] Wang J W and Rong L L 2008 Chin. Phys. Lett. 25 3826
[10] Battilotti S 2008 Automatica 44 348
[11] Shang Y 2010 Int. J. Math. Anal. 4 1205
[12] Shang Y 2010 Chin. Phys. B 19 070201
[13] Frank H and Frisch I 1970 IEEE Trans. Commun. Tech. 18 567
[14] Esfahanian A H and Hakimi S 1988 Inform. Process. Lett. 27 195
[15] Krishnamoorth M and Krishnamirthy B 1987 Comput. Math. Appl. 13 577
[16] Chvátal V 1973 Discrete Math. 5 215
[17] Jung H 1978 J. Comb. Theor. B 24 125
[18] Mohar B 1989 J. Comb. Theor. B 47 274
[19] Barrat A, Barthélemy M and Vespignani A 2008 Dynamical Process on Complex Networks (Cambridge: Cambridge University Press) p1
[20] Fiedler M 1973 Czech. Math. J. 23 298
[21] Wu J, Barahona M, Tan Y J and Deng H Z 2010 Chin. Phys. Lett. 27 078902
[22] Wu J, Barahona M, Tan Y J and Deng H Z 2010 arXiv:1009.3430
[23] Wu J, Barahona M, Tan Y J and Deng H Z 2009 arXiv:0912.2144
[24] Wu J, Deng H Z and Tan Y J 2010 The Third IEEE International Conference on Computer Science and Information Technology (Chengdu China 9–11 July 2010) p 50
[25] Shang Y 2011 J. Phys. A: Math. Theor. 44 075003
[26] Haemers W H 1995 Lin. Algebra Appl. 227 593
[27] Estrada E 2000 Chem. Phys. Lett. 319 713
[28] Estrada E and Rodríguez-Velázquez J A 2005 Phys. Rev. E 72 046105
[29] Estrada E and Rodríguez-Velázquez J A 2005 Phys. Rev. E 71 056103
[30] Barabási A L and Albert R 1999 Science 286 509
[31] Cohen R, Erez K, ben-Avraham D and Havlin S 2001 Phys. Rev. Lett. 86 3682
[32] Bollobás B 2001 Random Graphs (Cambridge: Cambridge University) p 1
2011, Vol. 28 
