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.

Abstract licence: CC BY-NC-ND

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.