Long-loop feedback vertex set and dismantling on bipartite factor graphs

doi:10.1103/PhysRevE.103.L061302

CORC > 理论物理研究所 > 中国科学院理论物理研究所 > 理论物理所科研产出 > 理论物理所1978-2010年知识产出

	Long-loop feedback vertex set and dismantling on bipartite factor graphs
	Li, Tianyi 1,6; Zhang, Pan 2,3; Zhou, Hai-Jun
刊名	PHYSICAL REVIEW E
	2021
卷号	103 期号:6 页码:L061302
关键词	COMMUNITY STRUCTURE COMPLEX NETWORKS
ISSN号	2470-0045
DOI	10.1103/PhysRevE.103.L061302
英文摘要	Network 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.
学科主题	Physics
语种	英语
内容类型	期刊论文
源URL	[http://ir.itp.ac.cn/handle/311006/27382]
专题	理论物理研究所_理论物理所1978-2010年知识产出
作者单位	1.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
推荐引用方式 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.