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

WANG Zhi-xiao; ZHANG Lei; SUN Cheng-cheng; RUI Xiao-bin; HUANG Zhen-zhen; ZHANG Sun-xian

doi:10.12263/DZXB.20201201

您当前的位置：

首页 >

文章列表页 >

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

PAPERS | 更新时间：2025-12-11

- Network Dismantling Algorithm Based on Community Detection and Inverse Reinsertion of Edges
- ACTA ELECTRONICA SINICA Vol. 50, Issue 3, Pages: 540-547(2022)
- 作者机构：
  
  1.中国矿业大学计算机学院,江苏徐州 221116
  2.教育部矿山数字化工程研究中心,江苏徐州 221116
  3.中国矿业大学图书馆,江苏徐州, 221116
  4.中国矿业大学徐海学院,江苏徐州 221008
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20201201
  CLC： TP393
- Received：28 October 2020，
  
  Revised：2020-12-30，
  
  Published：25 March 2022
- 稿件说明：
移动端阅览
王志晓,张磊,孙成成等.基于社区划分与连边逆序放回的网络分解算法[J].电子学报,2022,50(03):540-547.

WANG Zhi-xiao,ZHANG Lei,SUN Cheng-cheng,et al.Network Dismantling Algorithm Based on Community Detection and Inverse Reinsertion of Edges[J].ACTA ELECTRONICA SINICA,2022,50(03):540-547.
王志晓,张磊,孙成成等.基于社区划分与连边逆序放回的网络分解算法[J].电子学报,2022,50(03):540-547. DOI： 10.12263/DZXB.20201201.

WANG Zhi-xiao,ZHANG Lei,SUN Cheng-cheng,et al.Network Dismantling Algorithm Based on Community Detection and Inverse Reinsertion of Edges[J].ACTA ELECTRONICA SINICA,2022,50(03):540-547. DOI： 10.12263/DZXB.20201201.

摘要

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

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.

关键词

Keywords

references

朱恩强 , 吴艳蕾 , 许宇光 , 等 . 基于树核度的社交网络影响最大化问题 [J]. 电子学报 , 2019 , 47 ( 01 ): 161 - 168 .

ZHU E Q , WU Y L , XU Y G , et al . Tree-coritivity-based influence maximization in social networks [J]. Acta Electronica Sinca , 2019 , 47 ( 01 ): 161 - 168 . (in Chinese)

WANG N , SUN Q , ZHOU Y , et al . A study on influential user identification in online social networks [J]. Chinese Journal of Electronics , 2016 , 25 ( 3 ): 467 - 473 .

BRAUNSTEIN A , DALL' ASTA L , SEMERJIAN G , et al . Network dismantling [J]. Proceedings of the National Academy of Sciences , 2016 , 113 ( 44 ): 12368 - 12373 .

REN X L , GLEINIG N , HELBING D , et al . Generalized network dismantling [J]. Proceedings of the National Academy of Sciences of the United States of America , 2019 , 116 ( 14 ): 6554 - 6559 .

CAO Y , SUN Y K , MA L C . A fault diagnosis method for train plug doors via sound signals [J]. IEEE Intelligent Transportation Systems Magazine , 2020 , 13 ( 3 ): 107 - 117 .

CAO Y , WANG Z C , LIU F , et al . Bio-inspired speed curve optimization and sliding mode tracking control for subway trains [J]. IEEE Transactions on Vehicular Technology , 2019 , 68 ( 7 ): 6331 - 6342 .

MUGISHA S , ZHOU H J . Identifying optimal targets of network attack by belief propagation [J]. Physical Review E , 2016 , 94 ( 1 ): 012305 .

MORONE F , MAKSE H A . Influence maximization in complex networks through optimal percolation [J]. Nature , 2015 , 524 ( 7563 ): 65 - 68 .

CHENG X , REN F , SHEN H , et al . Bridgeness: a local index on edge significance in maintaining global connectivity [J]. Physics , 2010 , 10 ( 5 ): 10011 .

LÜ L , CHEN D , REN X L , et al . Vital nodes identification in complex networks [J]. Physics Reports , 2016 , 650 : 1 - 63 .

REN X L , GLEINIG N , TOLIC' D , et al . Underestimated cost of targeted attacks on complex networks [J]. Complexity , 2018 , 2018 : 2826243 .

汪林玉 , 谷科 , 余飞 , 等 . 基于个人意愿的社会网络团体结构与信息检测方案 [J]. 电子学报 , 2019 , 47 ( 04 ): 886 - 895 .

WANG L Y , GU K , YU F , et al . Social community structure and information detection scheme based on personal willingness [J]. Acta Electronica Sinca , 2019 , 47 ( 04 ): 886 - 895 . (in Chinese)

WANG F F , ZHANG B H , CHAI S C . Deep auto-encoded clustering algorithm for community detection in complex networks [J]. Chinese Journal of Electronics , 2019 , 28 ( 3 ): 489 - 496 .

雷秀娟 , 高银 , 郭玲 . 基于拓扑势加权的动态PPI网络复合物挖掘方法 [J]. 电子学报 , 2018 , 46 ( 01 ): 145 - 151 .

LEI X J , GAO Y , GUO L . Mining protein complexes based on topology potential weight in dynamic protein-protein interaction networks [J]. Acta electronica Sinca , 2018 , 46 ( 01 ): 145 - 151 . (in Chinese)

WANG X S , CHEN Y H , SUN W F . Identification of overlapping protein complexes using structural and functional information of ppi network [J]. Chinese Journal of Electronics , 2015 , 24 ( 3 ): 564 - 568 .

BLONDEL V D , GUILLAUME J L , LAMBIOTTE R , et al . Fast unfolding of communities in large networks [J]. Journal of Statistical Mechanics: Theory and Experiment , 2008 , 2008 ( 10 ): P10008 .

CHEN Y , PAUL G , HAVLIN S , et al . Finding a better immunization strategy [J]. Physical Review Letters , 2008 , 101 ( 5 ): 058701 .

CALLAWAY D S , NEWMAN M E J , STROGATZ S H , et al . Network robustness and fragility: percolation on random graphs [J]. Physical Review Letters , 2000 , 85 ( 25 ): 5468 - 5471 .

ZDEBOROVÁ L , ZHANG P , ZHOU H J . Fast and simple decycling and dismantling of networks [J]. Scientific Reports , 2016 , 6 ( 1 ): 37954 .

RICHARD J L , DONALD J R , ROBERT E T . Generalized nested dissection [J]. SIAM Journal on Numerical Analysis , 1979 , 16 ( 2 ): 346 - 358 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Behavior Steganography in Social Networks Based on 0-1 Knapsack Algorithm

An Efficient Algorithm of Information Recommendation Between Groups in Social Networks

A Social Network Recommendation Scheme Based on Bipartite Graph and Node Role Division

Co-Extracting Opinion Targets and Opinion-Bearing Words in Chinese Micro-Blog Texts

SEIR-Based Model for the Information Spreading over SNS

Related Author

GAO Peng

CHAI Peng-xiang

LANG Jun

XIANG Yang

FANG Qiang

ZHANG Bo

HUANG Zhen-hua

LIU Yan-bing

Related Institution

College of Computer Science and Engineering, Northeastern University

College of Information Mechanical and Electrical Engineering Shanghai Normal University Shanghai China

The Key Laboratory of Embedded System and Service Computing Ministry of Education Tongji University Shanghai China

Department of Computer and Technology Tongji University Shanghai China

College of Information, Mechanical and Electrical Engineering, Shanghai Normal University

⁰