Name
Abstract | ||
|---|---|---|
We study the problem of network dismantling, that is of finding a minimal set of vertices whose removal leaves the network broken in 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 insight into the dismantling problem concluding that it is an intrinsically collective problem and optimal dismantling sets cannot be viewed as a collection of individually well performing nodes. |
Year | Venue | DocType |
|---|---|---|
2016 | CoRR | Journal |
Volume | Citations | PageRank |
abs/1603.08883 | 13 | 0.63 |
References | Authors | |
9 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alfredo Braunstein | 1 | 479 | 38.97 |
| Luca Dall'Asta | 2 | 13 | 0.63 |
| Guilhem Semerjian | 3 | 251 | 15.96 |
| Lenka Zdeborová | 4 | 1190 | 78.62 |