title: Network dismantling.
abstract: We study the network dismantling problem, which consists of determining a minimal set of vertices in which removal leaves the network broken into connected components of subextensive size. For a large class of random graphs, this problem is tightly connected to the decycling problem (the removal of vertices, leaving the graph acyclic). Exploiting this connection and recent works on epidemic spreading, we present precise predictions for the minimal size of a dismantling set in a large random graph with a prescribed (light-tailed) degree distribution. Building on the statistical mechanics perspective, we propose a three-stage Min-Sum algorithm for efficiently dismantling networks, including heavy-tailed ones for which the dismantling and decycling problems are not equivalent. We also provide additional insights into the dismantling problem, concluding that it is an intrinsically collective problem and that optimal dismantling sets cannot be viewed as a collection of individually well-performing nodes.
authors: Department of Applied Science and Technology, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Turin, Italy.|Human Genetics Foundation, Via Nizza 52, 10126 Turin, Italy.|Collegio Carlo Alberto, Via Real Collegio 30, 10024 Moncalieri, Italy.
authors: Alfredo
authors: A
authors: Braunstein
authors: Department of Applied Science and Technology, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Turin, Italy.|Collegio Carlo Alberto, Via Real Collegio 30, 10024 Moncalieri, Italy.
authors: Luca
authors: L
authors: Dall'Asta
authors: Laboratoire de Physique Théorique, Ecole Normale Supérieure, Paris Sciences et Lettres (PSL) Research University, Sorbonne Universités, Université Pierre et Marie Curie (UPMC), CNRS, 75005 Paris, France.
authors: Guilhem
authors: G
authors: Semerjian
authors: Institut de Physique Théorique, CNRS, Commissariat à l'Energie Atomique (CEA) and Université Paris Saclay, 91191 Gif-sur-Yvette, France lenka.zdeborova@cea.fr.
authors: Lenka
authors: L
authors: Zdeborová
keywords: graph fragmentation; influence maximization; message passing; percolation; random graphs