Source-linked AI summary
Fast and simple decycling and dismantling of networks
Lenka Zdeborová, Pan Zhang, Hai-Jun Zhou
TL;DR
Decycling and dismantling are important but NP-hard network problems for which simple heuristics can be suboptimal and message-passing methods can be costly. CoreHD recursively removes highest-degree nodes from the 2-core, achieving solutions close to message-passing results on real-world networks at much lower computational cost. The paper therefore presents it as a practical first-choice strategy for many applications.
Problem
Decycling and dismantling support many network applications, but existing approaches either use simple heuristics with poor performance or computationally demanding message-passing methods.
Method
CoreHD adaptively removes the highest-degree nodes from the network’s 2-core, followed by tree-breaking and optional reinsertion for dismantling.
Results
On real-world networks, CoreHD produces decycling and dismantling sets within a few nodes of the best message-passing results, while being much faster.
Takeaways & Limitations
CoreHD offers a simple, extremely fast strategy whose performance is close to optimal and comparable to message-passing methods across the reported network instances.
Abstract
from arXiv · showhide
Decycling and dismantling of complex networks are underlying many important applications in network science. Recently these two closely related problems were tackled by several heuristic algorithms, simple and considerably sub-optimal, on the one hand, and time-consuming message-passing ones that evaluate single-node marginal probabilities, on the other hand. In this paper we propose a simple and extremely fast algorithm, CoreHD, which recursively removes nodes of the highest degree from the $2$-core of the network. CoreHD performs much better than all existing simple algorithms. When applied on real-world networks, it achieves equally good solutions as those obtained by the state-of-art iterative message-passing algorithms at greatly reduced computational cost, suggesting that CoreHD should be the algorithm of choice for many practical purposes.
I. INTRODUCTION
Decycling and dismantling are NP-hard network-optimization problems with broad applications, and existing methods trade simplicity for performance or computational complexity. The paper introduces CoreHD as a simple, fast alternative designed to approach message-passing quality while remaining tractable for very large and real-world networks.
- Problem setting: Decycling removes as few nodes as possible to eliminate loops, whereas dismantling removes the smallest set needed to break a network into sub-extensive connected components.Both problems support applications including vaccination, surveillance, information spreading, viral marketing, and identifying influential nodes.
- Problem setting: Because both problems are NP-hard, research seeks high-quality approximate solutions rather than exact polynomial-time algorithms.On sparse random networks, spin-glass methods provide accurate algorithms, and decycling closely tracks dismantling.
- Prior methods: Existing message-passing algorithms achieve near-theoretical performance but require whole-network equation iterations and have guarantees justified only for random networks.Their empirical success on loopy real-world networks leaves open the possibility of simpler, analyzable strategies.
- Motivation: Simple strategies are important for assessing practical usefulness, yet adaptive high-degree removal and collective influence remain far from optimal and, for CI, computationally costly.CI requires evaluating a large neighborhood around each node.
- Contribution: CoreHD combines the simplicity and speed of adaptive high-degree removal with performance much closer to optimal than CI and comparable to message-passing methods, while being several orders of magnitude faster.The method is intended to scale to networks with many billions of nodes.
- Contribution: The authors argue that CoreHD should be the first choice for many decycling and dismantling applications and that its structure may permit rigorous guarantees for loopy networks.The same idea generalizes to destroying a network’s k-core by repeatedly removing highest-degree nodes from the current k-core.
II. THE COREHD ALGORITHM
CoreHD focuses adaptive highest-degree removal on the network’s 2-core rather than on dangling trees, then applies tree-breaking and optional reinsertion for dismantling. This targets the structures relevant to loops and yields a simple algorithmic procedure for decycling and dismantling.
- Core-focused design: The 2-core is obtained by adaptively removing all leaves, so focusing on it excludes tree-like regions that need not be removed for decycling.High-degree nodes outside loops can be unnecessary because trees can be dismantled by removing a vanishing fraction of nodes.
- CoreHD procedure: CoreHD repeatedly removes the highest-degree node from the current 2-core, updating the 2-core and node degrees after each removal.The algorithm stops when the 2-core is empty and then performs tree-breaking.
- CoreHD procedure: The algorithm outputs a forest of small trees by combining adaptive 2-core removal with a final tree-breaking step.Its implementation repeatedly identifies a maximum-degree 2-core node, removes it, and updates the remaining core.
- Dismantling refinement: After decycling, CoreHD breaks the remaining trees into small components for dismantling and can reinsert deleted nodes that do not substantially increase the largest component.The reinsertion refinement is intended for networks containing many small loops.
III. RESULTS
CoreHD is evaluated against CI, BPD, and HD on random and real-world networks, measuring removal fractions, dismantling quality, and computational time. It achieves near-BPD solutions while substantially reducing computation, and outperforms CI across the reported settings.
- Random networks: CoreHD reaches the exact optimal decycling fraction ρ = 0.25 on regular random graphs of degree 3.This matches a greedy method previously shown to be optimal for that case.
- Random networks: CoreHD removes 0.1846 of nodes to create components smaller than 0.01N, compared with 0.2014 for CI, 0.2225 for HD, and 0.1780 for BPD.The theoretical asymptotic optimum reported for this ER network is 0.1753.
- Computational efficiency: CoreHD updates the 2-core in average O(1) operations after each deletion and can be faster than HD when the 2-core is much smaller than the network.Computing the initial 2-core requires O(N) operations in the reported leaf-removal implementation.
- Random networks: For N = 2 × 10^8 and c = 3, CoreHD achieves ρ ≈0.1407 in 64 minutes versus BPD's ρ ≈0.1357 in 23.5 hours.CoreHD removes one node per step, yet remains faster than the time required to read the network file.
- Random networks: Across ER, regular random, and scale-free networks, CoreHD performs better than CI and worse than BPD, with its best performance on scale-free networks.The scale-free result is highlighted because real-world networks commonly have heavy-tailed degree distributions.
- Real-world networks: On real-world networks, CoreHD produces decycling and dismantling sets close to BPD, smaller than CI, and slightly better than BPD on some instances.The reported instances include RoadEU, IntNet1, and RoadTX; Table I compares deletion counts and dismantling times.
IV. CONCLUSION AND DISCUSSIONS
CoreHD combines ultra-fast execution with strong decycling and dismantling performance, but the mechanism behind its advantage remains incompletely understood and decycling differs from dismantling on real-world networks.
- IV. CONCLUSION AND DISCUSSIONS: CoreHD iteratively removes highest-degree nodes from the network 2-core, producing an ultra-fast and highly efficient decycling and dismantling algorithm.Its running time is reported to be shorter than the time required to read the network file.
- IV. CONCLUSION AND DISCUSSIONS: CoreHD can outperform slower, more sophisticated alternatives, although a detailed explanation of why it performs best is left for future work.The authors report that CI, adjacency-matrix centrality on the 2-core, and HD on the 3-core are slower and perform no better.
- IV. CONCLUSION AND DISCUSSIONS: On real-world networks with many short loops and motifs, decycling differs substantially from dismantling.
Appendix A: Greedy Tree Breaking and Refinement by Insertion
The appendix describes a greedy procedure for breaking tree components and a refinement that reinserts removed nodes while preserving the target component-size threshold.
- Appendix A: Greedy Tree Breaking and Refinement by Insertion: Greedy tree breaking repeatedly removes the node whose deletion produces the largest reduction in the largest connected component.For forests, optimal breaking into small components is polynomial-time solvable, and the greedy procedure works well empirically.
- Appendix A: Greedy Tree Breaking and Refinement by Insertion: Messages propagated through a tree allow the algorithm to identify which node maximally decreases component size when removed.Each node reports the largest component created by removing the edge to a neighbor, enabling selection after messages reach the root.
- Appendix A: Greedy Tree Breaking and Refinement by Insertion: The refinement reinserts removed nodes one at a time, choosing the node that causes the smallest increase in component size.
Appendix B: Dangling-tree problem of the CI index
The CI index estimates node importance using degrees on a distance-ℓ boundary, but dangling-tree nodes can receive misleadingly high scores because the non-backtracking operator is governed by the 2-core.
- Appendix B: Dangling-tree problem of the CI index: At level ℓ, CIℓ(i) measures node importance using the degree of i and the degrees of nodes at distance ℓ from it.The distance-ℓ set is denoted ∂ℓi, and degrees are taken in the remaining network.
- Appendix B: Dangling-tree problem of the CI index: The CI algorithm repeatedly removes a small fraction of nodes with the highest CI values and updates the remaining indices.An example fraction is f = 0.001.
- Appendix B: Dangling-tree problem of the CI index: A high CI score can incorrectly prioritize a dangling-tree node that does not affect the non-backtracking eigenvalue because it lies outside the 2-core.
Appendix C: Comparing CoreHD and CoreCI
CoreCI adds 2-core reduction to CI and improves over original CI, but CoreHD performs slightly better while avoiding CoreCI’s repeated, time-consuming CI computations.
- Appendix C: Comparing CoreHD and CoreCI: CoreCI first reduces the remaining network to its 2-core, computes CI within that core, and deletes the highest-CI node.Afterward it may apply greedy tree breaking and reinsert nodes while the largest component remains below 0.01N.
- Appendix C: Comparing CoreHD and CoreCI: CoreCI considerably improves on original CI, yet CoreHD performs slightly better on ER, RR, and SF random networks.Table II compares the fraction ρ of deleted nodes across 96 instances of each network setting, with N = 10^5 and CoreCI radius ℓ = 4.
- Appendix C: Comparing CoreHD and CoreCI: Repeatedly computing CI within the 2-core remains time-consuming, so the authors recommend CoreHD as the more efficient practical heuristic.