On the relationship between the algebraic connectivity and graph's robustness to node and link failures
- 1 May 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 96-102
Abstract
We study the algebraic connectivity in relation to the graph's robustness to node and link failures. Graph's robustness is quantified with the node and the link connectivity, two topological metrics that give the number of nodes and links that have to be removed in order to disconnect a graph. The algebraic connectivity, i.e. the second smallest eigenvalue of the Laplacian matrix, is a spectral property of a graph, which is an important parameter in the analysis of various robustness-related problems. In this paper we study the relationship between the proposed metrics in three well-known complex network models: the random graph of Erdos-Renyi, the small-world graph of Watts-Strogatz and the scale-free graph of Barabasi-Albert. From (Fielder, 1973) it is known that the algebraic connectivity is a lower bound on both the node and the link connectivity. Through extensive simulations with the three complex network models, we show that the algebraic connectivity is not trivially connected to graph's robustness to node and link failures. Furthermore, we show that the tightness of this lower bound is very dependent on the considered complex network model.Keywords
This publication has 9 references indexed in Scilit:
- The Structure and Function of Complex NetworksSIAM Review, 2003
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- Random Graphs2001
- Emergence of Scaling in Random NetworksScience, 1999
- On power-law relationships of the Internet topologyACM SIGCOMM Computer Communication Review, 1999
- Collective dynamics of ‘small-world’ networksNature, 1998
- The Laplacian Spectrum of a GraphSIAM Journal on Matrix Analysis and Applications, 1990
- Algebraic connectivity of graphsCzechoslovak Mathematical Journal, 1973
- Theoretical Improvements in Algorithmic Efficiency for Network Flow ProblemsJournal of the ACM, 1972