Local Natural Connectivity in Complex Networks

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.