Fast and simple decycling and dismantling of networks

Lenka Zdeborová (1) , Pan Zhang (2) , Hai-Jun Zhou (2)

1 IPHT - Institut de Physique Théorique - UMR CNRS 3681
2 CAS - Chinese Academy of Sciences [Beijing]

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.

Mots clés: Physics and Society (physics.soc-ph); Disordered Systems and Neural Networks (cond-mat.dis-nn); Social and Information Networks (cs.SI)

Domaines: Physique et Société [physics.soc-ph]; Réseaux sociaux et d'information [cs.SI]

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