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 metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal-cea.archives-ouvertes.fr/cea-01448152
Contributor : Emmanuelle de Laborderie <>
Submitted on : Friday, January 27, 2017 - 3:36:29 PM
Last modification on : Monday, February 10, 2020 - 6:13:40 PM
Long-term archiving on: : Saturday, April 29, 2017 - 12:36:16 AM

File

1607.03276v1.pdf
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

205

Files downloads

277