Fast and simple decycling and dismantling of networks - CEA - Commissariat à l’énergie atomique et aux énergies alternatives Access content directly
Preprints, Working Papers, ... Year :

Fast and simple decycling and dismantling of networks


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.
Fichier principal
Vignette du fichier
1607.03276v1.pdf (566.07 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

cea-01448152 , version 1 (27-01-2017)



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



Gmail Facebook Twitter LinkedIn More