Fast and simple decycling and dismantling of networks - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

Fast and simple decycling and dismantling of networks

(1) , (2) , (2)
1
2

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

Dates and versions

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

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More