电子学报 ›› 2022, Vol. 50 ›› Issue (3): 540-547.DOI: 10.12263/DZXB.20201201

• 学术论文 • 上一篇    下一篇

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

王志晓1,2, 张磊1,4, 孙成成1, 芮晓彬1, 黄珍珍1,3, 张孙贤1   

  1. 1.中国矿业大学计算机学院, 江苏 徐州 221116
    2.教育部矿山数字化工程研究中心, 江苏 徐州 221116
    3.中国矿业大学图书馆, 江苏 徐州, 221116
    4.中国矿业大学徐海学院, 江苏 徐州 221008
  • 收稿日期:2020-10-28 修回日期:2020-12-30 出版日期:2022-03-25 发布日期:2022-03-25
  • 作者简介:王志晓 男,1979年生于河南叶县,博士中国矿业大学计算机学院教授、博士生导师.主要研究方向为社交网络分析与数据挖掘.在国内外重要学术期刊与会议上发表学术论文30余篇.E-mail:zhxwang@cumt.edu.cn
    张 磊 男,1982年生于江苏泰兴,中国矿业大学计算机学院博士研究生.主要研究方向为社交网络分析和机器学习.E-mail:zhangleixp@126.com
    孙成成 男,1993年生于山东邹城,中国矿业大学计算机学院博士研究生,主要研究方向为社会网络分析、图表示学习和数据挖掘.E-mail:scc@cumt.edu.cn
  • 基金资助:
    国家自然科学基金项目(61876186)

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

WANG Zhi-xiao1,2, ZHANG Lei1,4, SUN Cheng-cheng1, RUI Xiao-bin1, HUANG Zhen-zhen1,3, ZHANG Sun-xian1   

  1. 1.College of Computer Science and Technology,China University of Mining and Technology,Xuzhou,Jiangsu 221116,China
    2.Mining Digital Engineering Research Center of Ministry of Education,Xuzhou,Jiangsu 221116,China
    3.Library of China University of Mining and Technology,Xuzhou,Jiangsu 221116,China
    4.College of Xuhai,China University of Mining and Technology,Xuzhou,Jiangsu 221008,China
  • Received:2020-10-28 Revised:2020-12-30 Online:2022-03-25 Published:2022-03-25

摘要:

网络分解是通过删除网络中最少规模的节点或者连边,将网络破坏至最大连通分支的规模不超过设定阈值.传统基于节点删除的网络分解算法忽略了删除代价.实际上,节点的删除导致相应连边的删除,代价是不同的.传统基于连边删除的网络分解算法虽然考虑删除代价,但是,无论是迭代计算连边中心性值,还是迭代划分最大连通分量,其性能和效率都亟待改善.本文提出了一种基于社区划分与连边逆序放回的网络分解算法,该算法是一种基于连边删除的方法,包含两个步骤,首先,利用社区划分算法将网络划分为多个社区,删除社区之间的全部连边使社区独立,破坏社区间的连通性;然后,每个社区内部采用连边逆序放回策略破坏其内部连通性,从而完成整个网络的分解.真实网络及人工网络上的实验结果表明:一方面,本文提出的网络分解算法能够以最小的连边删除代价将网络分解至设定阈值;另一方面,随着网络规模、网络结构以及分解阈值的变化,算法展现出良好的稳定性.

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

Abstract:

Network dismantling aims to find the minimal set of nodes or edges that, if removed, will break the network into small components and the scale of the giant connected component shall not exceed the pre-defined threshold. Traditional 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 inverse reinsertion of edges is used to destroy the connectivity within each community. Thus, we can dismantle the whole network 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 network dismantling.

Key words: social network, network dismantling, deletion cost, community detection, inverse reinsertion of edge, network connectivty

中图分类号: