Robustness and Vulnerability of Scale-Free Random Graphs
Robustness and Vulnerability of Scale-Free Random Graphs
复制标题
DOI：
10.1080/15427951.2004.10129080
复制
发表时间：
2004-01
影响因子：
--
通讯作者：
B. Bollobás;O. Riordan
中科院分区：
文献类型：
--
作者：
B. Bollobás;O. Riordan
最近，许多新的“无标度”随机图模型被引入，其动机是在许多大规模真实世界网络中观察到的幂律度序列。也许最著名的是巴拉巴西-阿尔伯特模型，已经从启发式和实验的角度进行了广泛的研究。在这里，我们考虑数学上的两个基本特征的一个精确的版本，这个模型，LCD模型，即鲁棒性随机损坏，和恶意攻击的脆弱性。我们表明，LCD图是更强大的比经典的随机图具有相同数量的边缘，但也更容易受到攻击。特别地，如果n-顶点LCD图的顶点被随机删除，则只要任何正比例保持，在剩余顶点上诱导的图具有n阶分量。相反，如果删除的顶点是恶意选择的，则可以删除小于1的常数分数以破坏所有大组件。对于巴拉巴西-阿尔伯特模型，这些问题已经由几个小组进行了实验和实证研究。
Recently many new "scale-free" random graph models have been introduced, motivated by the power-law degree sequences observed in many large-scale, real-world networks. Perhaps the best known, the Barabási-Albert model, has been extensively studied from heuristic and experimental points of view. Here we consider mathematically two basic characteristics of a precise version of this model, the LCD model, namely robustness to random damage, and vulnerability to malicious attack. We show that the LCD graph is much more robust than classical random graphs with the same number of edges, but also more vulnerable to attack. In particular, if vertices of the n-vertex LCD graph are deleted at random, then as long as any positive proportion remains, the graph induced on the remaining vertices has a component of order n. In contrast, if the deleted vertices are chosen maliciously, a constant fraction less then 1 can be deleted to destroy all large components. For the Barabási-Albert model, these questions have been studied experimentally and heuristically by several groups.