基于社区划分与连边逆序放回的网络分解算法
Network Dismantling Algorithm Based on Community Detection and Inverse Reinsertion of Edges
- 电子学报 2022年50卷第3期 页码：540-547
- 作者机构：
1.中国矿业大学计算机学院,江苏徐州 221116
2.教育部矿山数字化工程研究中心,江苏徐州 221116
3.中国矿业大学图书馆,江苏徐州, 221116
4.中国矿业大学徐海学院,江苏徐州 221008
- 作者简介：
[ "王志晓 男，1979年生于河南叶县，博士中国矿业大学计算机学院教授、博士生导师.主要研究方向为社交网络分析与数据挖掘.在国内外重要学术期刊与会议上发表学术论文30余篇.E-mail:zhxwang@cumt.edu.cn" ]
[ "张 磊 男，1982年生于江苏泰兴，中国矿业大学计算机学院博士研究生.主要研究方向为社交网络分析和机器学习.E-mail:zhangleixp@126.com" ]
[ "孙成成 男，1993年生于山东邹城，中国矿业大学计算机学院博士研究生，主要研究方向为社会网络分析、图表示学习和数据挖掘.E-mail:scc@cumt.edu.cn" ]
- 基金信息：国家自然科学基金项目(61876186;71774159)
DOI：10.12263/DZXB.20201201
中图分类号： TP393收稿：2020-10-28，
修回：2020-12-30，
纸质出版：2022-03-25
- 稿件说明：
移动端阅览
王志晓,张磊,孙成成等.基于社区划分与连边逆序放回的网络分解算法[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 .
0
浏览量
9
下载量
0
CSCD
- 网络PDF下载
- Meta-XML下载
- BibTeX下载
- Endnote下载
- RefMan 下载
- NoteExpress下载
- NoteFirst下载
关联资源
相关文章
相关作者
相关机构
- 技术支持由北京北大方正电子有限公司提供 京ICP备09064830号-19
京公网安备11010802024621 - 本系统建议在Chrome、 IE9+ 以上版本浏览器阅读本站内容，360浏览器请切换至极速模式
- Cookies帮助我们提供服务并提供个性化体验。使用本网站，即表示您同意我们使用Cookies