On the Robustness of Complex Networks by Using the Algebraic Connectivity
The second smallest eigenvalue of the Laplacian matrix, also known as the algebraic connectivity, plays a special role for the robustness of networks since it measures the extent to which it is difficult to cut the network into independent components. In
- PDF / 484,366 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 31 Downloads / 144 Views
Abstract. The second smallest eigenvalue of the Laplacian matrix, also known as the algebraic connectivity, plays a special role for the robustness of networks since it measures the extent to which it is difficult to cut the network into independent components. In this paper we study the behavior of the algebraic connectivity in a well-known complex network model, the Erd˝os-R´enyi random graph. We estimate analytically the mean and the variance of the algebraic connectivity by approximating it with the minimum nodal degree. The resulting estimate improves a known expression for the asymptotic behavior of the algebraic connectivity [18]. Simulations emphasize the accuracy of the analytical estimation, also for small graph sizes. Furthermore, we study the algebraic connectivity in relation to the graph’s robustness to node and link failures, i.e. the number of nodes and links that have to be removed in order to disconnect a graph. These two measures are called the node and the link connectivity. Extensive simulations show that the node and the link connectivity converge to a distribution identical to that of the minimal nodal degree, already at small graph sizes. This makes the minimal nodal degree a valuable estimate of the number of nodes or links whose deletion results into disconnected random graph. Moreover, the algebraic connectivity increases with the increasing node and link connectivity, justifies the correctness of our definition that the algebraic connectivity is a measure of the robustness in complex networks.
1 Introduction Complex networks describe a wide range of natural and man-made systems, e.g. the Internet, the WWW, networks of food webs, social acquaintances, paper citations, as well as many others [5,11,28]. Although complex systems are extremely different in their function, a proper knowledge of their topology is required to thoroughly understand and predict the overall system performance. For example, in computer networks, performance and scalability of protocols and applications, robustness to different types of perturbations (such as failures and attacks), all depend on the network topology. Consequently, network topology analysis, primarily aiming at non-trivial topological properties, has resulted in the definition of a variety of practically important metrics, capable of quantitatively characterizing certain topological aspects of the studied systems [2,24]. A. Das et al. (Eds.): NETWORKING 2008, LNCS 4982, pp. 183–194, 2008. c IFIP International Federation for Information Processing 2008
184
A. Jamakovic and P. Van Mieghem
In this paper, we rely on a spectral metric, i.e. the second smallest Laplacian eigenvalue, often also referred to as the algebraic connectivity [13]. Fiedler [13] showed that the algebraic connectivity plays a special role: 1) a graph is disconnected if and only if the algebraic connectivity is zero, 2) the multiplicity of zero as an eigenvalue of a graph is equal to the number of disconnected components. There is a vast literature on the algebraic connectivity
Data Loading...
