基于优化理论的复杂网络节点攻击策略

孙昱; 姚佩阳; 张杰勇; 付凯

doi:10.11999/JEIT160396

基于优化理论的复杂网络节点攻击策略

doi: 10.11999/JEIT160396

基金项目:

国家自然科学基金(61573017)

计量
- 文章访问数: 1773
- HTML全文浏览量: 226
- PDF下载量: 566
- 被引次数: 0
出版历程
- 收稿日期: 2016-04-22
- 修回日期: 2016-10-31
- 刊出日期: 2017-03-19

Node Attack Strategy of Complex Networks Based on Optimization Theory

Funds:

The National Natural Science Foundation of China (61573017)

摘要

摘要: 该文在分析传统复杂网络节点攻击策略不足的基础上提出一种新的攻击策略，该策略的思路是将节点攻击序列的构造问题视为一个优化问题而非传统的评估问题。为了实现该策略，设计了复杂网络抗毁性测度用以衡量节点攻击序列的攻击效果，建立了以最大化攻击效果为目标的节点攻击序列构造模型，提出了基于禁忌搜索的模型求解算法。在真实网络和模拟网络上的实验结果表明，新策略比其它复杂网络节点攻击策略更为有效和优越。
- 复杂网络 /
- 攻击策略 /
- 抗毁性测度 /
- 优化模型 /
- 禁忌搜索
Abstract: This study proposes a new node attack strategy of complex networks by analyzing the disadvantages of traditional strategies. The idea of the new strategy is to treat the construction problem of node attack sequence as an optimal problem rather than an evaluation problem. To achieve this strategy, the study designs a survivability index of complex networks to measure the attack effect created by a node attack sequence, then establishes a construction model of node attack sequence with the goal to maximize attack effect, and further brings forward an algorithm based on tabu search to solve the model. Experiment results from real networks and simulated networks show that the new strategy is more effective than others.
- Complex networks /
- Attack strategy /
- Survivability measurement /
- Optimization model /
- Tabu search

HTML全文

参考文献(25)

JIANG Y and WANG Y B. Analysis of attack and defense strategies on complex networks[C]. Proceedings of International Conference on Sensor Network Security Technology and Privacy Communication System, Harbin, China, 2013: 58-62.

ALBERT R, JEONG H, and BARABASI A L. Error and attack tolerance of complex networks[J]. Nature, 2000, 406: 378-382. doi: 10.1038/35019019.

HOLME P, KIM B J, YOON C N, et al. Attack vulnerability of complex networks[J]. Physical Review E, 2002, 65(5): 056109. doi: 10.1103/PhysRevE.65.056109.

BELLINGERI M, CASSI D, and VINCENZI S. Efficiency of attack strategies on complex model and real-world networks [J]. Physica A, 2014, 414: 174-180. doi: 10.1016/j.physa.2014. 06.079.

NIE T Y, GUO Z, ZHAO K, et al. New attack strategies for complex networks[J]. Physica A, 2015, 424: 248-253. doi: 10.1016/j.physa.2015.01.004.

聂廷远, 郭征, 李坤龙. 复杂网络的攻击策略研究[J]. 计算机仿真, 2015, 32(7): 286-289. doi: 10.3969/j.issn.1006-9348. 2015.07.063.

NIE Tingyuan, GUO Zheng, and LI Kunlong. A study of attack strategies for complex networks[J]. Computer Simulation, 2015, 32(7): 286-289. doi: 10.3969/j.issn.1006- 9348.2015.07.063.

XIAO S and XIAO G. On intentional attacks and protections in complex communication networks[C]. Proceedings of IEEE Global Telecommunications Conference, San Francisco, CA, USA, 2006: 1-5.

李涛, 裴文江. 针对重叠社团结构的复杂网络多靶向攻击策略[J]. 北京邮电大学学报, 2010, 33(3): 34-39. doi: 10.3969/ j.issn.1007-5321.2010.03.007.

LI Tao and PEI Wenjiang. Multi-targets attack strategy based on the overlapping community structure of complex networks[J]. Journal of Beijing University of Posts and Telecommunications, 2010, 33(3): 34-39. doi: 10.3969/j.issn. 1007-5321.2010.03.007.

WANG H, HUANG J Y, XU X M, et al. Damage attack on complex networks[J]. Physica A, 2014, 408: 134-148. doi: 10. 1016/j.physa.2014.04.001.

ANURAG S, RAHUL K, and YATINDRA N S. Impact of structural centrality based attacks in complex networks[J]. Acta Physica Polonica B, 2015, 46(2): 305-324. doi: 10.5506/ APhysPolB.46.305.

DENG Y, WU J, and TAN Y J. Optimal attack strategy of complex networks based on tabu search[J]. Physica A, 2016, 442: 74-81. doi: 10.1016/j.physa.2015.08.043.

HERRNANN H J, SCHNEIDER C M, MOREIRA A A, et al. Onion-like network topology enhances robustness against malicious attacks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2011, 1: P01027. doi: 10.1088/1742-5468/ 2011/01/P01027.

SCHNEIDER C M, MOREIRA A A, ANDRADE J S, et al. Mitigation of malicious attacks on networks[J]. Proceedings of the National Academy of Sciences, of the United States of America 2011, 108(10): 3838-3841. doi: 10.1073/pnas. 1009440108.

LOUZADA V H P, DAOLIO F, HERRMANN H J, et al. Smart rewiring for network robustness[J]. Journal of Complex Networks, 2013, 1(2): 150-159. doi: 10.1093/comnet/xxx000.

BURKE E K and KENDALL G. Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques[M]. New York: Springer, 2005: 165.

LATORA V and MARCHIORI M. Efficient behavior of small-world networks[J]. Physical Review Letters, 2001, 87(19): 198701. doi: 10.1103/PhysRevLett.87.198701.

陈勇, 胡爱群, 胡啸. 通信网中节点重要性的评价方法[J]．通信学报, 2004, 25(8): 129-135. doi: 10.3321/ j.issn:1000-436X. 2004.08.018.

CHEN Yong, HU Aiqun, and HU Xiao. Evaluation method for node importance in communication networks[J]. Journal on Communications, 2004, 25(8): 129-135. doi: 10.3321/j.issn: 1000-436X.2004.08.018.

于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法[J]. 物理学报, 2013, 62(2): 1-9. doi: 10.7498/ aps.62.020204.

YU Hui, LIU Zun, and LI Yongjun. Key nodes in complex networks identified by multi-attribute decision-making method[J]. Acta Physica Sinica, 2013, 62(2): 1-9. doi: 10.7498 /aps.62.020204.

秦李, 杨子龙, 黄曙光. 复杂网络的节点重要性综合评价[J]. 计算机科学, 2015, 42(2): 60-64. doi: 10. 11896/j.issn.1002- 137X.2015.2.013.

QIN Li, YANG Zilong, and HUANG Shuguang. Synthesis evaluation method for node importance in complex networks [J]. Computer Science, 2015, 42(2): 60-64. doi: 10.11896/ j.issn.1002-137X.2015.2.013.

PAGE L and PERRY J. Reliability polynomials and links importance in networks[J]. IEEE Transactions on Reliability, 1994, 43(1): 51-58. doi: QK.IEL.1994.0000024.0007056. 00285108.

施引文献

资源附件(0)

访问统计