# Network dismantling

arXiv: https://arxiv.org/abs/1603.08883 · HTML: https://mlsanity.com/paper/1603.08883/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2016.

## Built on by (most cited first, 12 of 12)

- [Machine learning dismantling and early-warning signals of disintegration in complex systems](https://mlsanity.com/paper/2101.02453/) (2021)
- [Identify Critical Nodes in Complex Network with Large Language Models](https://mlsanity.com/paper/2403.03962/) (2024)
- [Robustness and stability of enterprise intranet social networks: The impact of moderators](https://mlsanity.com/paper/2105.09127/) (2021)
- [Recovering the Graph Underlying Networked Dynamical Systems under Partial Observability: A Deep Learning Approach](https://mlsanity.com/paper/2208.04405/) (2022)
- [Influential Simplices Mining via Simplicial Convolutional Network](https://mlsanity.com/paper/2307.05841/) (2023)
- [Hypernetwork Dismantling via Deep Reinforcement Learning](https://mlsanity.com/paper/2104.14332/) (2021)
- [Inferring the Graph of Networked Dynamical Systems under Partial Observability and Spatially Colored Noise](https://mlsanity.com/paper/2312.11324/) (2023)
- [Mastering Percolation-like Games with Deep Learning](https://mlsanity.com/paper/2305.07687/) (2023)
- [Learning Network Dismantling Without Handcrafted Inputs](https://mlsanity.com/paper/2508.00706/) (2025)
- [Structure-Aware Cooperative Ensemble Evolutionary Optimization on Combinatorial Problems with Multimodal Large Language Models](https://mlsanity.com/paper/2510.21906/) (2025)
- [PACIFIER: Pacing Opinion Depolarization via a Unified Graph Learning Framework](https://mlsanity.com/paper/2602.23390/) (2026)
- [Placing Degree Scales After LayerNorm](https://mlsanity.com/paper/2606.14022/) (2026)

## Abstract (arXiv)

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.