ITP OpenIR  > SCI期刊论文
Li, Tianyi1,6; Zhang, Pan2,3; Zhou, Hai-Jun
Long-loop feedback vertex set and dismantling on bipartite factor graphs
Source PublicationPHYSICAL REVIEW E
AbstractNetwork dismantling aims at breaking a network into disconnected components and attacking vertices that intersect with many loops has proven to be a most efficient strategy. Yet existing loop-focusing methods do not distinguish the short loops within densely connected local clusters (e.g., cliques) from the long loops connecting different clusters, leading to lowered performance of these algorithms. Here we propose a new solution framework for network dismantling based on a two-scale bipartite factor-graph representation, in which long loops are maintained while local dense clusters are simplistically represented as individual factor nodes. A mean-field spin-glass theory is developed for the corresponding long-loop feedback vertex set problem. The framework allows for the advancement of various existing dismantling algorithms; we developed the new version of two benchmark algorithms BPD (which uses the message-passing equations of the spin-glass theory as the solver) and CoreHD (which is fastest among well-performing algorithms). New solvers outperform current state-of-the-art algorithms by a considerable margin on networks of various sorts. Further improvement in dismantling performance is achievable by opting flexibly the choice of local clusters.
Cooperation Status国际
Subject AreaPhysics
MOST Discipline CataloguePhysics, Fluids & Plasmas ; Physics, Mathematical
Indexed BySCIE
Citation statistics
Document Type期刊论文
Affiliation1.Chinese Acad Sci, Inst Theoret Phys, CAS Key Lab Theoret Phys, Beijing 100190, Peoples R China
2.MIT, Sloan Sch Management, Syst Dynam Grp, Cambridge, MA 02142 USA
3.UCAS, Hangzhou Inst Adv Study, Sch Fundamental Phys & Math Sci, Hangzhou 310024, Peoples R China
4.Int Ctr Theoret Phys Asia Pacific, Beijing, Peoples R China
5.Univ Chinese Acad Sci, Sch Phys Sci, Beijing 100049, Peoples R China
6.MinJiang Univ, MinJiang Collaborat Ctr Theoret Phys, Fuzhou 350108, Peoples R China
7.CUHK Business Sch, Dept Decis Sci & Managerial Econ, Hong Kong, Peoples R China
Recommended Citation
GB/T 7714
Li, Tianyi,Zhang, Pan,Zhou, Hai-Jun. Long-loop feedback vertex set and dismantling on bipartite factor graphs[J]. PHYSICAL REVIEW E,2021,103(6):L061302.
APA Li, Tianyi,Zhang, Pan,&Zhou, Hai-Jun.(2021).Long-loop feedback vertex set and dismantling on bipartite factor graphs.PHYSICAL REVIEW E,103(6),L061302.
MLA Li, Tianyi,et al."Long-loop feedback vertex set and dismantling on bipartite factor graphs".PHYSICAL REVIEW E 103.6(2021):L061302.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Li, Tianyi]'s Articles
[Zhang, Pan]'s Articles
[Zhou, Hai-Jun]'s Articles
Baidu academic
Similar articles in Baidu academic
[Li, Tianyi]'s Articles
[Zhang, Pan]'s Articles
[Zhou, Hai-Jun]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Li, Tianyi]'s Articles
[Zhang, Pan]'s Articles
[Zhou, Hai-Jun]'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.