Spectral measure of robustness for Internet topology

The natural connectivity as a novel robustness measure of complex networks is proposed. 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 robustness of global Internet AS-level topology and Chinese Internet AS-level topology is studied using natural connectivity.