Optimal shattering of complex networks

Abstract

We consider optimal attacks or immunization schemes on different models of random graphs. We derive bounds for the minimum number of nodes needed to be removed from a network such that all remaining components are fragments of negligible size. We obtain bounds for different regimes of random regular graphs, Erdős-Rényi random graphs, and scale free networks, some of which are tight. We show that the performance of attacks by degree is bounded away from optimality. Finally we present a polynomial time attack algorithm and prove its optimal performance in certain cases.

References in corpus (12)

• Error and attack tolerance of complex networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Breakdown of the Internet under intentional attack
• Influence maximization in complex networks through optimal percolation
• Network dismantling
• Generalized Network Dismantling
• Identifying optimal targets of network attack by belief propagation
• Optimal percolation on multiplex networks
• Measuring network resilience through connection patterns
• Sequential Defense Against Random and Intentional Attacks in Complex Networks
• Graph Partitioning Induced Phase Transitions