On the Robustness of Complex Networks by Using the Algebraic Connectivity
On the Robustness of Complex Networks by Using the Algebraic Connectivity
复制标题
DOI：
10.1007/978-3-540-79549-0_16
复制
发表时间：
2008-05
期刊：
影响因子：
--
通讯作者：
A. Jamakovic;P. Mieghem
中科院分区：
文献类型：
--
作者：
A. Jamakovic;P. Mieghem
拉普拉斯矩阵的第二小特征值，也称为代数连通性，对网络的鲁棒性起着特殊的作用，因为它衡量了网络难以切割成独立组件的程度。在本文中，我们研究了一个著名的复杂网络模型，Erdens-Rényi随机图的代数连通性的行为。我们估计解析的平均值和方差的代数连接近似它的最小节点度。由此产生的估计改进了代数连通性的渐近行为的已知表达式[18]。模拟强调了分析估计的准确性，也适用于小图尺寸。此外，我们研究了代数连接图的鲁棒性节点和链路故障，即节点和链路的数量，必须删除，以断开一个图。这两个度量称为节点和链路连通性。大量的模拟表明，节点和链路的连通性收敛到一个分布相同的最小节点度，已经在小图的大小。这使得最小节点度成为删除导致不连通随机图的节点或链接的数量的有价值的估计。此外，代数连通度随着节点和链路连通度的增加而增加，证明了代数连通度是衡量复杂网络鲁棒性的一个指标的正确性.
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ős-Rényi 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.