Fast and simple decycling and dismantling of networks

Abstract

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.

References in corpus (4)

• Robust network community detection using balanced propagation
• Immunization and targeted destruction of networks using explosive percolation
• Minimal contagious sets in random regular graphs
• Spin glass phase transitions in the random feedback vertex set problem

Cited by in corpus (34)

• Robustness and resilience of complex networks
• Generalized Network Dismantling
• Explosive Phenomena in Complex Networks
• Machine learning dismantling and early-warning signals of disintegration in complex systems
• Optimal percolation on multiplex networks
• 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
• Unraveling the effects of multiscale network entanglement on disintegration of empirical systems
• Targeted Damage to Interdependent Networks
• Underestimated cost of targeted attacks on complex networks
• Identifying vital nodes by Achlioptas process
• Smeared phase transitions in percolation on real complex networks
• Influence maximization on temporal networks
• On Minimal Sets to Destroy the $k$-Core in Random Networks
• Optimal percolation in correlated multilayer networks with overlap
• 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
• Solving Statistical Mechanics on Sparse Graphs with Feedback Set Variational Autoregressive Networks
• Rapid decay in the relative efficiency of quarantine to halt epidemics in networks
• Dismantling Complex Networks by a Neural Model Trained from Tiny Networks
• The structure of networks that evolve under a combination of growth, via node addition and random attachment, and contraction, via random node deletion
• Spectral estimation of the percolation transition in clustered networks
• 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
• The Fate of Articulation Points and Bredges in Percolation
• Hierarchical cycle-tree packing model for $K$-core attack problem
• Centralities in complex networks
• Bounding robustness in complex networks under topological changes through majorization techniques
• Spin-glass model for the C-dismantling problem
• Phase transition in evolving networks that combine preferential attachment and random node deletion
• K-core attack, equilibrium K-core, and kinetically constrained spin system