Robustness and Vulnerability of Scale-Free Random Graphs

Abstract

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.