Knowledge Management System of Institute of Theoretical Physics, CAS
Zdeborova, L; Zhang, P ; Zhou, HJ; Zhang, P (reprint author), Chinese Acad Sci, Inst Theoret Phys, CAS Key Lab Theoret Phys, Beijing 100190, Peoples R China.
| |
| 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