基于社团划分的复杂网络级联抗毁攻击策略

计算机应用 ›› 2014, Vol. 34 ›› Issue (6): 1666-1670.

基于社团划分的复杂网络级联抗毁攻击策略

丁超¹,姚宏²,杜军¹,彭兴钊¹,李浩敏¹

1. 空军工程大学航空航天工程学院,西安 710038
2. 空军工程大学理学院，西安 710051

收稿日期:2013-12-09 修回日期:2014-01-29 出版日期:2014-06-01 发布日期:2014-07-02
通讯作者: 丁超
作者简介:丁超(1989-),男,河南商丘人,硕士研究生,主要研究方向:复杂网络数据挖掘;姚宏(1963-),女,陕西西安人,教授,博士生导师,主要研究方向:复杂系统非线性动力学;杜军(1973-),男,山西太原人,副教授,博士,主要研究方向:智能故障诊断;彭兴钊(1987-),男,河南封丘人,博士研究生,主要研究方向:复杂网络;李浩敏(1989-),男,河南新郑人,硕士研究生,主要研究方向:复杂网络抗毁性。〖JP〗
基金资助:
陕西省自然科学基金资助项目;航空科学基金资助项目

Cascading invulnerability attack strategy of complex network via community detection

DING Chao¹,YAO Hong²,DU Jun¹,PENG Xingzhao¹,LI Minhao¹

1. College of Aeronautics and Astronautics Engineering, Air Force Engineering University, Xi'an Shaanxi 710038, China
2. College of Science, Air Force Engineering University, Xi’an Shaanxi 710051, China

Received:2013-12-09 Revised:2014-01-29 Online:2014-06-01 Published:2014-07-02
Contact: DING Chao

摘要/Abstract

摘要：

为研究在社团划分基础上复杂网络的级联抗毁攻击策略,采用节点及其邻居节点介数定义初始负荷,这种定义方式综合考虑了节点的信息,采用局部择优分配策略处理故障节点负荷,研究了网络耦合强度,WS(Watts-Strogatz)小世界网络、BA(Barabási-Albert)无标度网络、ER(Erds-Rényi)随机网络、局域世界(WL)网络在社团划分攻击策略下抗毁性,以及不同攻击策略下具有重叠和非重叠社团结构网络的抗毁性。仿真结果表明，网络的耦合强度与抗毁性成负相关；不同类型网络在快速分裂算法识别社团前提下,攻击介数最大节点时网络抗毁性最弱；具有重叠社团结构的网络在集团渗流算法（CPM）识别后,采用攻击重叠部分介数最大节点的策略时网络抗毁性最弱。结论表明采用社团划分的攻击策略可以最大规模破坏网络。

Abstract:

In order to investigate the cascading invulnerability attack strategy of complex network via community detection, the initial load of the node was defined by the betweenness of the node and its neighbors, this defining method comprehensively considered the information of the nodes, and the load on the broken nodes were redistributed to its neighbors according to the local preferential probability. When the network being intentionally attacked based on community detection, the couple strength, the invulnerability of Watts-Strogatz (WS) network, Barabási-Albert (BA) network, Erds-Rényi (ER) network and World-Local (WL) network, as well as network with overlapping and non-overlapping community under differet attack strategies were studied. The results show that the network's cascading invulnerability is negatively related with couple strength; as to different types of networks, under the premise that fast division algorithm correctly detects community structure, the networks invulnerability is lowest when the node with largest betweenness was attacked; after detecting overlapping community using the Clique Percolation Method (CPM), the network invulnerability is lowest when the overlapping node with largest betweenness was attacked. It comes to conclusion that the network will be largest destoryed when using the attack strategy of complex network via community detection.

丁超姚宏杜军彭兴钊李浩敏. 基于社团划分的复杂网络级联抗毁攻击策略[J]. 计算机应用, 2014, 34(6): 1666-1670.

DING Chao YAO Hong DU Jun PENG Xingzhao LI Minhao. Cascading invulnerability attack strategy of complex network via community detection[J]. Journal of Computer Applications, 2014, 34(6): 1666-1670.

参考文献

[1]WEI D Q, LUO X S, ZHANG B. Analysis of cascading failure in complex power networks under the load local preferential redistribution rule[J]. Physica A: Statistical Mechanics and its Applications, 2012, 391(8): 2771-2777.
[2]WANG J-W. Robustness of heterogenous network with mitigation strategy against cascading failures[J]. Modern Physics Letters B, 2012, 26(14): 1250087.
[3]THAI M T, PARDALOS P M. Handbook of optimization in complex networks[M]. Berlin: Springer-Verlag, 2012.
[4]WANG J-W. Modeling cascading failures in complex networks based on radiate circle[J]. Physica A: Statistical Mechanics and its Applications, 2012, 391(15): 4004-4011.
[5]NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J].Physical Review E,2004,69:026113.
[6]ALBERT R, BARABSI A L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002, 74(1): 47-97.
[7]XIA Y, FAN J, DAVID H. Cascading failure in Watts_Strogatz small-world networks[J]. Physica A: Statistical Mechanics and its Applications, 2010,389(6):1281-1285.
[8]LI F, HU B, DI P. Optimization of dynamic invulnerability of scale-free networks based on limited resource model[J]. Systems Engineering and Electronics, 2012, 34(1): 175-178.(黎放，胡斌，狄鹏.基于资源有限模型的无标度网络动态抗毁性优化[J].系统工程与电子技术,2012, 34(1):175-178.)
[9]LI H, DU J, PENG X, et al. Research on cascading invulnerability of community structure networks under intentional-attack[J]. , 2014,34(4):935-938.（李浩敏，杜军，彭兴钊，等.蓄意攻击下一类多社团网络级联抗毁性研究[J].计算机应用，2014,34(4):935-938.）
[10]WU J, GAO Z, SUN H. Cascade and breakdown in scale-free networks with community structure[J]. Physical Review E,2006,74:06611.
[11]WANG J, RONG L, ZHANG Z. Attack vulnerability of scale-free networks due to cascading failures[J]. Physica A: Statistical Mechanics and its Applications, 2008, 387(26): 6671-6678.
[12]WU J, RUI L, JIAO L, et al. Phase transition model for community detection[J]. Physica A: Statistical Mechanics and its Applications,2013, 392(6):1287-1301.
[13]NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E,2004,70(6):066111.
[14]PALLA G, DERNYI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[15]ADAMCSEK B, PALLA G, FARKAS I J, et al. CFinder: locating cliques and overlapping modules in biological networks[J]. Bioinformatics,2006,22(8):1021-1023.
[16]MOTTER A E, NISHIKAWA T, LAI Y C. Cascade-based attacks on complex networks [J]. Physical Review E, 2002, 66: 065102(R).