Network dismantling

March 29, 2016 · Entered Twilight · 🏛 Proceedings of the National Academy of Sciences of the United States of America

"Last commit was 9.0 years ago (≥5 year threshold)"

Evidence collected by the PWNC Scanner

Repo contents: COPYING, Makefile, README.md, decycler.cpp, gnp.py, mes.hpp, omp_config.h, proba.hpp, real_type.hpp, reverse-greedy.cpp, reverse-greedy.py, treebreaker.py, twitter.txt.gz

Authors Alfredo Braunstein, Luca Dall'Asta, Guilhem Semerjian, Lenka Zdeborová arXiv ID 1603.08883 Category physics.soc-ph Cross-listed cond-mat.stat-mech, cs.DS Citations 260 Venue Proceedings of the National Academy of Sciences of the United States of America Repository https://github.com/abraunst/decycler ⭐ 18 Last Checked 1 month ago

Abstract

We study the network dismantling problem, which consists in determining a minimal set of vertices whose removal leaves the network broken into connected components of sub-extensive 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 further 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.