Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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.
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Emmanuelle De Laborderie Connect in order to contact the contributor
Submitted on : Friday, January 27, 2017 - 3:36:29 PM
Last modification on : Friday, January 7, 2022 - 3:51:41 AM
Long-term archiving on: : Saturday, April 29, 2017 - 12:36:16 AM


Files produced by the author(s)



Lenka Zdeborová, Pan Zhang, Hai-Jun Zhou. Fast and simple decycling and dismantling of networks. 2017. ⟨cea-01448152⟩



Record views


Files downloads