基于社区划分与连边逆序放回的网络分解算法  

Network Dismantling Algorithm Based on Community Detection and Inverse Reinsertion of Edges

作　　者：王志晓[1,2] 张磊 孙成成[1] 芮晓彬[1] 黄珍珍 张孙贤 WANG Zhi-xiao;ZHANG Lei;SUN Cheng-cheng;RUI Xiao-bin;HUANG Zhen-zhen;ZHANG Sun-xian(College of Computer Science and Technology,China University of Mining and Technology,Xuzhou,Jiangsu 221116,China;Mining Digital Engineering Research Center of Ministry of Education,Xuzhou,Jiangsu 221116,China;Library of China University of Mining and Technology,Xuzhou,Jiangsu 221116,China;College of Xuhai,China University of Mining and Technology,Xuzhou,Jiangsu 221008,China)

机构地区：[1]中国矿业大学计算机学院,江苏徐州221116 [2]教育部矿山数字化工程研究中心,江苏徐州221116 [3]中国矿业大学图书馆,江苏徐州221116 [4]中国矿业大学徐海学院,江苏徐州221008

出　　处：《电子学报》2022年第3期540-547,共8页Acta Electronica Sinica

基　　金：国家自然科学基金项目(No.61876186,No.71774159)。

摘　　要：网络分解是通过删除网络中最少规模的节点或者连边,将网络破坏至最大连通分支的规模不超过设定阈值.传统基于节点删除的网络分解算法忽略了删除代价.实际上,节点的删除导致相应连边的删除,代价是不同的.传统基于连边删除的网络分解算法虽然考虑删除代价,但是,无论是迭代计算连边中心性值,还是迭代划分最大连通分量,其性能和效率都亟待改善.本文提出了一种基于社区划分与连边逆序放回的网络分解算法,该算法是一种基于连边删除的方法,包含两个步骤,首先,利用社区划分算法将网络划分为多个社区,删除社区之间的全部连边使社区独立,破坏社区间的连通性;然后,每个社区内部采用连边逆序放回策略破坏其内部连通性,从而完成整个网络的分解.真实网络及人工网络上的实验结果表明:一方面,本文提出的网络分解算法能够以最小的连边删除代价将网络分解至设定阈值;另一方面,随着网络规模、网络结构以及分解阈值的变化,算法展现出良好的稳定性.Network dismantling aims to find the minimal set of nodes or edges that,if removed,will break the net⁃work into small components and the scale of the giant connected component shall not exceed the pre-defined threshold.Tra⁃ditional node-deleting based methods ignore the cost of deletion.In fact,when we delete a node,the corresponding edges linked to this node should also be deleted.The cost is different.Although traditional edge-deleting based methods take the cost into consideration,performance and efficiency need to be further improved.This paper proposes an edge-deleting based network dismantling algorithm,which contains two stages:community detection and inverse reinsertion of edges.In the first stage,the whole network is divided into different communities by using community detection algorithm and then edges between communities are removed to destroy the connectivity of communities.In the second stage,the strategy of in⁃verse reinsertion of edges is used to destroy the connectivity within each community.Thus,we can dismantle the whole net⁃work into pieces.Experiment results on real-world and artificial networks show that,on one hand,our proposed method can dismantle networks by removing a smaller set of edges than that of other state-of-the-art methods.On the other hand,our proposed method exhibits stable performance with the variation of network scale,network structure and the threshold of net⁃work dismantling.

关 键 词：社交网络 网络分解 删除代价 社区划分 连边逆序放回 网络连通性 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]