ITP OpenIR  > 计算平台成果
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 PublicationSCIENTIFIC 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
Volume6Issue:6Pages:37954
Cooperation Status国际
Subject AreaScience & Technology - Other Topics
DOIhttp://dx.doi.org/10.1038/srep37954
Indexed BySCI
Funding OrganizationNational 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] ; 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] ; 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] ; 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期刊论文
Identifierhttp://ir.itp.ac.cn/handle/311006/21260
Collection计算平台成果
Corresponding AuthorZhang, 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(6):37954.
APA Zdeborova, L,Zhang, P,Zhou, HJ,&Zhang, P .(2016).Fast and simple decycling and dismantling of networks.SCIENTIFIC REPORTS,6(6),37954.
MLA Zdeborova, L,et al."Fast and simple decycling and dismantling of networks".SCIENTIFIC REPORTS 6.6(2016):37954.
Files in This Item:
File Name/Size DocType Version Access License
Fast and simple decy(612KB)期刊论文出版稿开放获取CC BY-NC-SAApplication Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zdeborova, L]'s Articles
[Zhang, P]'s Articles
[Zhou, HJ]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zdeborova, L]'s Articles
[Zhang, P]'s Articles
[Zhou, HJ]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zdeborova, L]'s Articles
[Zhang, P]'s Articles
[Zhou, HJ]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.