We introduce the concept of natural connectivity as a robustness measure of complex networks. The natural connectivity has a clear physical meaning and a simple mathematical formulation. It characterizes the redundancy of alternative paths by quantifying the weighted number of closed walks of all lengths. We show that the natural connectivity can be derived mathematically from the graph spectrum as an average eigenvalue and that it increases strictly monotonically with the addition of edges. We test the natural connectivity and compare it with other robustness measures within a scenario of edge elimination. We demonstrate that the natural connectivity has an acute discrimination which agrees with our intuition. PACS numbers: 89.75. Hc, 89.75.Fb, 02.10.Ox We are surrounded by networks. Networks with complex topology describe a wide range of systems in nature and society. The study of complex networks has become an important area of multidisciplinary research involving physics, mathematics, biology, social sciences, informatics, and other theoretical and applied sciences [1, 2] . Complex networks rely for their function and performance on their robustness, i.e., the ability to endure threats and survive accidental events. For example, modern society is dependent on its critical infrastructure networks: communication, electrical power, rail, and fuel distribution networks. Failure of any of these critical infrastructure networks can bring the ordinary activities of work and recreation to a standstill. Other examples of robustness arise in biological and social systems, including questions such as the stability of social organizations in the face of famine, war, or even changes in social policy. Because of its broad application, robustness has become a central topic in all complex networks and receives growing attention. As a basic concept of graph theory, the connectivity of a graph is an important and probably the earliest measure of robustness of a network [3] . Vertex (edge) connectivity, defined as the size of the smallest vertex (edge) cut, determines in a certain sense the robustness of a graph to the deletion of vertices (edges). However, the vertex or edge connectivity only partly reflects the ability of graphs to retain certain degrees of connectedness after deletion. Other improved measures were introduced and studied, including super connectivity [4] [12] . In contrast to vertex (edge) connectivity, these new measures consider both the cost to damage a network and how badly the network is damaged. However, from an algorithmic point of view, it is unfortunate that the problem of calculating these measures for general graphs is NP-complete. This implies that these measures are of no great use within the context of complex networks. Another remarkable measure to unfold the robustness of a network is the second smallest eigenvalue of the Laplacian matrix, also known as the algebraic connectivity. Fiedler [13] showed that the magnitude of the algebraic connectivity reflects how well connected the overall graph is, i.e., the larger the algebraic connectivity is, the more difficult it is to cut a graph into independent components. Hence, there is a vast literature on the algebraic connectivity (see [14] for a survey). However, the algebraic connectivity is equal to zero for all disconnected networks. Therefore, it is too coarse a measure for complex networks. The prime study regarding network robustness within the context of complex networks came from random graph theory [15] and was stimulated by the work of Albert et al. [16] . Instead of a strict extremal property, they proposed a statistical measure, i.e., the critical removal fraction of vertices (edges) for the disintegration of a network, to characterize the robustness of complex networks. The disintegration of networks can be observed from the decrease of network performance. The most common performance measurements include the diameter, the size of largest component, the average path length, the efficiency [17, 18] and the number of reachable vertex pairs [19, 20] . As the fraction of removed vertices or edges increases, the network will eventually collapse at a critical fraction. It is suggested that scalefree networks display an exceptional robustness against random failure, but show poor performance against intentional attack [16] . As an expansion of the work by
In REF natural connectivity is considered, characterising the redundancy of alternative paths between nodes by measuring the weighted number of closed walks of all lengths on the network.
Spectral Measure of Robustness in Complex Networks
arXiv: Statistical Mechanics
Mathematics Physics