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 | |
发表期刊 | SCIENTIFIC REPORTS |
语种 | 英语 |
摘要 | 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 | |
卷号 | 6页码:37954 |
学科领域 | Science & Technology - Other Topics |
DOI | http://dx.doi.org/10.1038/srep37954 |
收录类别 | SCI |
项目资助者 | 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] |
引用统计 | |
文献类型 | 期刊论文 |
条目标识符 | http://ir.itp.ac.cn/handle/311006/21476 |
专题 | SCI期刊论文 计算平台成果 |
通讯作者 | Zhang, P (reprint author), Chinese Acad Sci, Inst Theoret Phys, CAS Key Lab Theoret Phys, Beijing 100190, Peoples R China. |
推荐引用方式 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. |
条目包含的文件 | ||||||
文件名称/大小 | 文献类型 | 版本类型 | 开放类型 | 使用许可 | ||
Fast and simple decy(612KB) | 开放获取 | -- | 请求全文 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论