Dismantling Networks by Skeleton Extraction and Greedy Tree Breaking

作     者：Rui, Xiaobin Meng, Fanrong Chai, Yahui Wang, Zhixiao Yu, Philip S. 

作者机构：China Univ Min & Technol Sch Comp Sci & Technol Xuzhou 221116 Jiangsu Peoples R China Minist Educ Peoples Republ China Mine Digitizat Engn Res Ctr Xuzhou 221116 Jiangsu Peoples R China Univ Illinois Dept Comp Sci Chicago IL 60607 USA 

出 版 物：《IEEE ACCESS》 (IEEE Access)

年 卷 期：2021年第9卷

页      面：84922-84931页

核心收录：

基　　金：Program of ``Double First Rate'' Construction Disciplines of CUMT 

主　　题：Skeleton Clustering algorithms Heuristic algorithms Topology Explosives Social networking (online) Licenses Network dismantling network skeleton acyclic graph greedy tree breaking approximation algorithm 

摘      要：Network dismantling is one of the important NP-hard problems in the field of social network analysis. It aims to break down networks into many small components of limited size by only removing a small group of nodes. One feasible way is to decycle (eliminating all the cycles) the network first and then break the acyclic graph. However, existing decycling-based algorithms mainly concentrate on the decycling step, ignoring the importance of the tree breaking process. Besides, none of the algorithms try to pre-process the network, which may bring improvement in both effectiveness and efficiency. In this paper, we fill these two gaps by proposing a novel network dismantling algorithm that combines skeleton extraction and greedy tree breaking (SEGTB). Network skeleton supports the whole network structure, whose removal would leave a much looser structure and serves as an effective pre-processing for the dismantling problem. The presented tree breaking method is provided with theoretical proofs on its lower bound. Experiments on ten real-world datasets show that our proposed SEGTB algorithm is both effective and efficient, outperforming the state-of-the-art.