Impact of Random Failures and Attacks on Poisson and Power-Law Random Networks

Abstract

It appeared recently that the underlying degree distribution of networks may play a crucial role concerning their robustness. Empiric and analytic results have been obtained, based on asymptotic and mean-field approximations. Previous work insisted on the fact that power-law degree distributions induce high resilience to random failure but high sensitivity to attack strategies, while Poisson degree distributions are quite sensitive in both cases. Then, much work has been done to extend these results. We aim here at studying in depth these results, their origin, and limitations. We review in detail previous contributions and give full proofs in a unified framework, and identify the approximations on which these results rely. We then present new results aimed at enlightening some important aspects. We also provide extensive rigorous experiments which help evaluate the relevance of the analytic results. We reach the conclusion that, even if the basic results of the field are clearly true and important, they are in practice much less striking than generally thought. The differences between random failures and attacks are not so huge and can be explained with simple facts. Likewise, the differences in the behaviors induced by power-law and Poisson distributions are not as striking as often claimed.

References in corpus (46)

• Emergence of scaling in random networks
• Fast unfolding of communities in large networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Epidemic spreading in scale-free networks
• Fast algorithm for detecting community structure in networks
• Assortative mixing in networks
• The diameter of the world wide web
• Random graphs with arbitrary degree distributions and their applications
• Evolution of networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Cascade-based attacks on complex networks
• Attack vulnerability of complex networks
• Dynamical and correlation properties of the Internet
• Breakdown of the Internet under intentional attack
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Immunization of complex networks
• Efficient Immunization Strategies for Computer Networks and Populations
• A model for cascading failures in complex networks
• Growing Scale-Free Networks with Tunable Clustering
• Scale-free topology of e-mail networks
• Cascade control and defense in complex networks
• Modeling the Internet's Large-Scale Topology
• Halting viruses in scale-free networks
• Properties of highly clustered networks
• Highly clustered scale-free networks
• Stability and topology of scale-free networks under attack and defense strategies
• Resilience to damage of graphs with degree correlations
• Epidemic spreading in complex networks with degree correlations
• Random graphs as models of networks
• Optimization of Robustness of Complex Networks
• Optimization of Network Robustness to Waves of Targeted and Random Attack
• Efficient local strategies for vaccination and network attack
• The topology of the transcription regulatory network in the yeast, S. cerevisiae
• Exploring networks with traceroute-like probes: theory and simulations
• Uncorrelated Random Networks
• Robustness of the avalanche dynamics in data packet transport on scale-free networks
• Resilience of Complex Networks to Random Breakdown
• Comment on "Breakdown of the Internet under Intentional Attack"
• On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs
• Stability of complex networks under the evolution of attack and repair
• Redundancy and Robustness of the AS-level Internet topology and its models
• Measuring Fundamental Properties of Real-World Complex Networks