Network dismantling

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.

Source code and data can be found at https://github.com/abraunst/decycler

References in corpus (4)

• Influence maximization in complex networks through optimal percolation
• Efficient Immunization Strategies for Computer Networks and Populations
• Identifying optimal targets of network attack by belief propagation
• Minimal contagious sets in random regular graphs

Cited by in corpus (67)

• Robustness and resilience of complex networks
• Generalized Network Dismantling
• Explosive Phenomena in Complex Networks
• Fast and simple decycling and dismantling of networks
• Machine learning dismantling and early-warning signals of disintegration in complex systems
• Optimal percolation on multiplex networks
• Structural Robustness of Complex Networks: A Survey of A Posteriori Measures
• Optimal Deployment of Resources for Maximizing Impact in Spreading Processes
• Rare events and discontinuous percolation transitions
• Efficient collective influence maximization in cascading processes with first-order transitions
• Identifying an influential spreader from a single seed in complex networks via a message-passing approach
• Fluctuations in percolation of sparse complex networks
• Controlling the uncertain response of real multiplex networks to random damage
• Fundamental difference between superblockers and superspreaders in networks
• Systematic comparison between methods for the detection of influential spreaders in complex networks
• Nonbacktracking expansion of finite graphs
• Large deviation theory of percolation on multiplex networks
• Unraveling the effects of multiscale network entanglement on disintegration of empirical systems
• A loop enhancement strategy for network robustness
• Targeted Damage to Interdependent Networks
• Underestimated cost of targeted attacks on complex networks
• Robustness and stability of enterprise intranet social networks: The impact of moderators
• Scaling of percolation transitions on Erdös-Rényi networks under centrality-based attacks
• Neighborhood Information-based Probabilistic Algorithm for Network Disintegration
• Challenges in the Decentralised Web: The Mastodon Case
• Targeted influence maximization in complex networks
• Learning to Identify High Betweenness Centrality Nodes from Scratch: A Novel Graph Neural Network Approach
• On Minimal Sets to Destroy the $k$-Core in Random Networks
• Statistical analysis of articulation points in configuration model networks
• Analysis of the convergence of the degree distribution of contracting random networks towards a Poisson distribution using the relative entropy
• Convergence towards an Erd{\H o}s-Rényi graph structure in network contraction processes
• A growth model for water distribution networks with loops
• Rapid decay in the relative efficiency of quarantine to halt epidemics in networks
• Influence Maximization for Fixed Heterogeneous Thresholds
• Extended-range percolation in complex networks
• Competition, Collaboration, and Optimization in Multiple Interacting Spreading Processes
• Dismantling Complex Networks by a Neural Model Trained from Tiny Networks
• Optimal cost for strengthening or destroying a given network
• Deep-learning-aided dismantling of interdependent networks
• The structure of networks that evolve under a combination of growth, via node addition and random attachment, and contraction, via random node deletion
• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• Critical behaviors of high-degree adaptive and collective-influence percolation
• Statistical analysis of edges and bredges in configuration model networks
• Dismantling Efficiency and Network Fractality
• Performance of attack strategies on modular networks
• Generalized $k$-core pruning process on directed networks
• Bounding robustness in complex networks under topological changes through majorization techniques
• Hierarchical cycle-tree packing model for $K$-core attack problem
• Centralities in complex networks
• The Fate of Articulation Points and Bredges in Percolation
• Spin-glass model for the C-dismantling problem
• Universal vulnerability in strong modular networks with various degree distributions between inequality and equality
• Phase transition in evolving networks that combine preferential attachment and random node deletion
• Detecting and modelling real percolation and phase transitions of information on social media
• Feedback arcs and node hierarchy in directed networks
• Realizing interdependent couplings as thermal or higher-order interactions
• Heterogeneity in Outcomes of Repeated Instances of Percolation Experiments
• Optimal shattering of complex networks
• Modeling resource consumption in the US air transportation system via minimum-cost percolation
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Effective Self-Healing Networks against Attacks or Disasters in Resource Allocation Control
• More Tolerant Reconstructed Networks by Self-Healing against Attacks in Saving Resource
• Larger holes as narrower degree distributions in complex networks
• Local Articulation Points in Complex Networks
• Dismantle a network efficiently during the entire process by a compound algorithm
• Ensemble approach for generalized network dismantling