Knowledge Management System of Institute of Theoretical Physics, CAS
Zdeborova, L; Zhang, P![]() ![]() | |
Fast and simple decycling and dismantling of networks | |
Source Publication | SCIENTIFIC REPORTS
![]() |
Language | 英语 |
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. |
2016 | |
Volume | 6Pages:37954 |
Subject Area | Science & Technology - Other Topics |
DOI | http://dx.doi.org/10.1038/srep37954 |
Indexed By | SCI |
Funding Organization | National Basic Research Program of China [2013CB932804] ; National Basic Research Program of China [2013CB932804] ; National Basic Research Program of China [2013CB932804] ; National Basic Research Program of China [2013CB932804] ; National Natural Science Foundation of China [11121403, 11225526] ; National Natural Science Foundation of China [11121403, 11225526] ; National Natural Science Foundation of China [11121403, 11225526] ; National Natural Science Foundation of China [11121403, 11225526] ; Knowledge Innovation Program of Chinese Academy of Sciences [KJCX2-EW-J02] ; Knowledge Innovation Program of Chinese Academy of Sciences [KJCX2-EW-J02] ; Knowledge Innovation Program of Chinese Academy of Sciences [KJCX2-EW-J02] ; Knowledge Innovation Program of Chinese Academy of Sciences [KJCX2-EW-J02] |
Citation statistics | |
Document Type | 期刊论文 |
Identifier | http://ir.itp.ac.cn/handle/311006/21476 |
Collection | SCI期刊论文 计算平台成果 |
Corresponding Author | Zhang, P (reprint author), Chinese Acad Sci, Inst Theoret Phys, CAS Key Lab Theoret Phys, Beijing 100190, Peoples R China. |
Recommended Citation GB/T 7714 | Zdeborova, L,Zhang, P,Zhou, HJ,et al. Fast and simple decycling and dismantling of networks[J]. SCIENTIFIC REPORTS,2016,6:37954. |
APA | Zdeborova, L,Zhang, P,Zhou, HJ,&Zhang, P .(2016).Fast and simple decycling and dismantling of networks.SCIENTIFIC REPORTS,6,37954. |
MLA | Zdeborova, L,et al."Fast and simple decycling and dismantling of networks".SCIENTIFIC REPORTS 6(2016):37954. |
Files in This Item: | ||||||
File Name/Size | DocType | Version | Access | License | ||
Fast and simple decy(612KB) | 开放获取 | -- | Application Full Text |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment