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.
Type de document :
Pré-publication, Document de travail
t16/123 2017
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal-cea.archives-ouvertes.fr/cea-01448152
Contributeur : Emmanuelle De Laborderie <>
Soumis le : vendredi 27 janvier 2017 - 15:36:29
Dernière modification le : jeudi 15 mars 2018 - 15:05:52
Document(s) archivé(s) le : samedi 29 avril 2017 - 00:36:16

Fichier

1607.03276v1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Lenka Zdeborová, Pan Zhang, Hai-Jun Zhou. Fast and simple decycling and dismantling of networks. t16/123 2017. 〈cea-01448152〉

Partager

Métriques

Consultations de la notice

120

Téléchargements de fichiers

65