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 involved and accurate 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. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1038/srep37954 | SCIENTIFIC REPORTS |
Field | DocType | Volume |
Network science,Heuristic,Computer science,Complex network,Artificial intelligence,SIMPLE algorithm,Recursion | Journal | 6 |
Issue | ISSN | Citations |
6 | 2045-2322 | 11 |
PageRank | References | Authors |
0.59 | 13 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Lenka Zdeborová | 1 | 1190 | 78.62 |
Pan Zhang | 2 | 17 | 3.17 |
Haijun Zhou | 3 | 76 | 12.53 |