title: 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 involved and accurate 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.
authors.affiliation: Institut de Physique Thérique, CNRS, CEA and Université Paris-Saclay, Gif-sur-Yvette, France.
authors.forename: Lenka
authors.initials: L
authors.lastname: Zdeborová
authors.affiliation: CAS Key Laboratory of Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China.
authors.forename: Pan
authors.initials: P
authors.lastname: Zhang
authors.affiliation: CAS Key Laboratory of Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China.
authors.forename: Hai-Jun
authors.initials: HJ
authors.lastname: Zhou