基于拓扑势的网络毁伤最大算法

doi:10.12305/j.issn.1001-506X.2023.09.20

摘要/Abstract

摘要：

针对攻击代价相等时的有限资源网络毁伤问题, 给出了网络毁伤最大化的定义。为了改进近似求解算法求解毁伤最大化问题时复杂度较高的缺陷, 提出了基于拓扑势和CELF(cost-effective lazy-forward)的TPCELF(algorithm based on topology potential and CELF)算法。利用无标度网络和实测网络进行实验, 结果表明，TPCELF算法在计算速度上有较大的提升, 网络平均毁伤效果接近于近似求解算法; 且优于采用常见重要性度量指标排序算法得到的平均毁伤效果。所提方法可从网络毁伤的角度为复杂网络关键节点挖掘提供参考。

关键词: 复杂网络, 拓扑势, 毁伤最大化, CELF算法

Abstract:

In view of the problem of network damage with limited resources when the attack cost is equal, the definition of network damage maximization is given. In order to improve the defect that the approximate algorithm suffers high computation complexity when solving network damage maximization problem, the algorithm based on topology potential and cost-effective lazy-forward (TPCELF) is proposed. Experiments with simulated scale-free networks and real network show that the TPCELF algorithm has a greater improvement in calculation speed, and the average damage effect of the network is close to the approximate algorithm. What's more, the TPCELF algorithm is better than other commonly used importance metric ranking algorithms in average network damage effect. The proposed approach can provide a reference for mining key nodes in complex networks from the perspective of network damage.

Key words: complex network, topology potential, damage maximization, cost-effective lazy-forward (CELF) algorithm

中图分类号:

TP393

俞锦涛, 肖兵, 熊家军. 基于拓扑势的网络毁伤最大算法[J]. 系统工程与电子技术, 2023, 45(9): 2812-2818.

Jintao YU, Bing XIAO, Jiajun XIONG. Network damage maximization algorithm based on topology potential[J]. Systems Engineering and Electronics, 2023, 45(9): 2812-2818.

图/表 9

图1

表1

图2

图3

表2

表3

表4

图4

图5

参考文献 31

1	WU X T , DONG H R , TSE C K , et al. Analysis of metro network performance from a complex network perspective[J]. Physica A: Statistical Mechanics and its Applications, 2018, 492, 553- 563. doi: 10.1016/j.physa.2017.08.074
2	MAHMOUD S , YUSEF E , AHMED M . Applications of complex network analysis in electric power systems[J]. Energies, 2018, 11 (6): 1381. doi: 10.3390/en11061381
3	刘同林, 杨芷柔, 张虎, 等. 基于复杂网络的军事通信网络建模与性能分析[J]. 系统工程与电子技术, 2020, 42 (12): 2892- 2898.
	LIU T L , YANG Z R , ZHANG H , et al. Modeling and performance analysis of military communication network based on complex network[J]. System Engineering and Electronics, 2020, 42 (12): 2892- 2898.
4	翟慧敏, 张子莺, 赵晓利, 等. 基于网络结构分析的信阳市绿色基础设施优化研究[J]. 信阳师范学院学报(自然科学版), 2021, 34 (2): 260- 266.
	ZHAI H M , ZHANG Z Y , ZHAO X L , et al. Optimization of green infrastructure in Xinyang city based on network structure analysis[J]. Journal of Xinyang Normal University (Natural Science Edition), 2021, 34 (2): 260- 266.
5	刘德胜. 基于复杂网络分析方法的作战体系评估研究综述[J]. 军事运筹与系统工程, 2020, 34 (3): 66- 73. doi: 10.3969/j.issn.1672-8211.2020.03.011
	LIU D S . Review on combat system evaluation based on complex network analysis method[J]. Military Operations Research and Systems Engineering, 2020, 34 (3): 66- 73. doi: 10.3969/j.issn.1672-8211.2020.03.011
6	LIU F Z , XIAO B , LI H . Finding key node sets in complex networks based on improved discrete fireworks algorithm[J]. Journal of Systems Science and Complexity, 2021, 34, 1014- 1027. doi: 10.1007/s11424-020-9023-1
7	SHAO C C , CUI P S , XUN P , et al. Rank correlation between centrality metrics in complex networks: an empirical study[J]. Open Physics, 2018, 16 (1): 1009- 1023. doi: 10.1515/phys-2018-0122
8	FREEMAN L C . A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40 (1): 35- 41. doi: 10.2307/3033543
9	DU Y X , GAO C , CHEN X , et al. A new closeness centrality measure via effective distance in complex networks[J]. Chaos, 2015, 25 (3): 440- 442.
10	JOONHYUN B , SANGWOOK K . Identifying and ranking influential spreaders in complex networks by neighborhood coreness[J]. Physica A: Statal Mechanics and its Applications, 2014, 395 (4): 549- 559.
11	JIANG Z Y , LIU Z Q , HE X , et al. Cascade phenomenon against subsequent failures in complex networks[J]. Physica A: Statal Mechanics and its Applications, 2018, 499, 472- 480. doi: 10.1016/j.physa.2018.02.071
12	SOHEILA M , REZA F , MOSTAFA S , et al. Identifying influential nodes in heterogeneous networks[J]. Expert Systems with Applications, 2020, 160, 113580. doi: 10.1016/j.eswa.2020.113580
13	丁学君, 李梦雨. 在线社会网络中考虑用户体验的谣言阻断策略[J]. 系统工程学报, 2020, 35 (6): 721- 735. doi: 10.13383/j.cnki.jse.2020.06.001
	DING X J , LI M Y . Rumor blocking strategies considering user experience in online social network[J]. Journal of Systems Engineering, 2020, 35 (6): 721- 735. doi: 10.13383/j.cnki.jse.2020.06.001
14	BANERJEE S , JENAMANI M , PRATIHAR D K . A survey on influence maximization in a social network[J]. Knowledge and Information Systems, 2020, 62, 3417- 3455. doi: 10.1007/s10115-020-01461-4
15	TANG J X , ZHAO F Q , ZHANG R S , et al. A sequential seed scheduling heuristic based on determinate and latent margin for influence maximization problem with limited budget[J]. International Journal of Modern Physics C, 2021, 32 (6): 2150079. doi: 10.1142/S0129183121500790
16	ZHANG L , XIA J J , CHENG F , et al. Multi-objective optimization of critical node detection based on cascade model in complex networks[J]. IEEE Trans.on Network Science and Engineering, 2020, 7 (3): 2052- 2066. doi: 10.1109/TNSE.2020.2972980
17	FAN C J , ZENG L , SUN Y Z , et al. Finding key players in complex networks through deep reinforcement learning[J]. Nature Machine Intelligence, 2020, 2 (6): 317- 324. doi: 10.1038/s42256-020-0177-2
18	王超, 郭基联, 符凌云. 基于拓扑势的作战体系网络节点重要度评估方法[J]. 兵工学报, 2020, 41 (8): 188- 194.
	WANG C , GUO J L , FU L Y . Research on evaluation method of node importance of combat system-of-systems network based on topological potential[J]. Acat Armamentarii, 2020, 41 (8): 188- 194.
19	DOMINGOS P, RICHARDSON M. Mining the network value of customers[C]//Proc. of the 7th International Conference on Knowledge Discovery and Data Mining, 2001: 57-66.
20	LESKOVEC J, KRAUSE A, GUESTRIN C, et al. Cost-effective outbreak detection in networks[C]//Proc. of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007: 420-429.
21	LATORA V , MARCHIORI M . A measure of centrality based on the network efficiency[J]. New Journal of Physics, 2007, 9 (6): 188. doi: 10.1088/1367-2630/9/6/188
22	NEMHAUSER G , WOLSEY L , FISHER M . An analysis of the approximations for maximizing submodular set functions[J]. Mathematical Programming, 1978, 14 (1): 265- 294. doi: 10.1007/BF01588971
23	刘凤增, 肖兵, 金宏斌, 等. 基于有限节点集的网络毁伤最大化问题研究[J]. 控制与决策, 2020, 35 (4): 937- 942.
	LIU F Z , XIAO B , JIN H B , et al. Network damage maximization based on finite node set[J]. Control and Decision, 2020, 35 (4): 937- 942.
24	YUAN H N , HAN Y N , CAI N , et al. A multi-granularity backbone network extraction method based on the topology potential[J]. Complexity, 2018, 8604132.
25	WANG S L , MALANG K , YUAN H N , et al. Extracting skeleton of the global terrorism network based on m-modified topology potential[J]. Complexity, 2020, 7643290.
26	LIU Y S , YE X F , ZHAN X H , et al. TPQCI: a topology potential-based method to quantify functional influence of copy number variations[J]. Methods, 2021, doi: 10.1016/j.ymeth.2021.04.015
27	淦文燕, 赫南, 李德毅, 等. 一种基于拓扑势的网络社区发现方法[J]. 软件学报, 2009, 20 (8): 2241- 2254.
	GAN W Y , HE N , LI D Y , et al. Community discovery method in networks based on topological potential[J]. Journal of Software, 2009, 20 (8): 2241- 2254.
28	LI M , LU Y , WANG J X , et al. A topology potential-based method for identifying essential proteins from PPI networks[J]. IEEE Trans.on Computational Biology and Bioinformatics, 2015, 12 (2): 372- 383. doi: 10.1109/TCBB.2014.2361350
29	TANG J , TANG X Y , YUAN J S . An effcient and effective hop-based approach for infuence maximization in social networks[J]. Social Network Analysis and Mining, 2018, 8, 10. doi: 10.1007/s13278-018-0489-y
30	蓝羽石, 毛少杰, 王珩. 指挥信息系统结构理论与优化方法[M]. 北京: 国防工业出版社, 2015.
	LAN Y S , MAO S J , WANG H . The theory and optimization method of command information system structure[M]. Beijing: National Defense Industry Press, 2015.
31	LESKOVEC J. Autonomous systems-Oregon-1[EB/OL]. [2021-04-07]. http://snap.stanford.edu/data/Oregon-1.html.

节点数	算法
节点数	TPCELF	GABIN	GREEDY
50	0.060 5	0.219 3	0.478 1
60	0.062 2	0.223 4	0.568 9
70	0.071 3	0.226 0	0.679 8
80	0.072 8	0.235 6	0.804 6
90	0.087 2	0.240 4	0.917 6
100	0.092 0	0.262 8	1.063 1
200	0.100 4	0.335 6	2.332 9
300	0.110 1	0.493 0	4.220 8
400	0.164 1	0.869 5	8.772 0
500	0.177 0	1.189 0	14.216 5
600	0.292 1	1.616 5	23.543 7
700	0.304 9	2.135 4	35.286 5

γ	Δ_TG	Δ_TG	Δ_TD	Δ_TB	Δ_TC
1.5	0.008 5	－0.002 44	0.049 9	0.035 8	0.052 9
2	0.002 7	－0.000 93	0.035 5	0.038 0	0.058 6
2.5	0.032 2	－0.004 11	0.153 5	0.180 6	0.314 4
3	0.037 8	0.000 51	0.150 4	0.276 1	0.321 4
3.5	0.009 8	0.000 26	0.084 2	0.287 1	0.264 1
4	0.005 3	0.000 16	0.062 8	0.209 0	0.227 3
4.5	0.001 3	0.000 03	0.052 5	0.203 0	0.216 0
5	0.003 3	0.000 06	0.042 6	0.125 3	0.197 0

[1]	张冰雪, 李希胜, 尤佳, 宋委任. 基于节点复合特性的端-边协同网络生成算法[J]. 系统工程与电子技术, 2023, 45(8): 2588-2596.
[2]	王琮, 沈会良, 夏永祥, 白光晗, 方依宁. 装备保障体系关键节点分析[J]. 系统工程与电子技术, 2022, 44(10): 3134-3142.
[3]	王岩韬, 杨拯. 航班运行风险网络的传播与控制改进[J]. 系统工程与电子技术, 2021, 43(9): 2544-2552.
[4]	毕可心, 吴明功, 张文斌, 温祥西, 杜坎. 基于速度障碍法的飞行冲突网络建模与分析[J]. 系统工程与电子技术, 2021, 43(8): 2163-2173.
[5]	李昂, 聂党民, 温祥西, 王泽坤, 杨诚修. 基于相依网络和SVM的管制系统运行态势评估[J]. 系统工程与电子技术, 2021, 43(5): 1287-1294.
[6]	顾凌枫, 何明, 陈国友, 季敏惠, 刘锦涛. 无人机集群系统弹性研究[J]. 系统工程与电子技术, 2021, 43(1): 156-162.
[7]	李佳威, 吴明功, 温祥西, 刘飞. 基于最小连通支配集的复杂网络关键节点与连边识别方法[J]. 系统工程与电子技术, 2019, 41(11): 2541-2549.
[8]	王尔申, 王玉伟, 曲萍萍, 蓝晓宇, 陈佳美. 基于代价的复杂网络边攻击策略有效性分析[J]. 系统工程与电子技术, 2018, 40(4): 919-926.
[9]	郝羽成, 李成兵, 魏磊. 考虑节点过载的复杂网络级联失效模型[J]. 系统工程与电子技术, 2018, 40(10): 2282-2287.
[10]	昝翔, 陈春良, 张仕新, 陈伟龙, 张立君. 考虑权重演化的装备重要度动态评估方法[J]. 系统工程与电子技术, 2017, 39(9): 2022-2030.
[11]	王运明, 潘成胜, 陈波, 张多平. 基于局域世界的加权指控网络演化模型[J]. 系统工程与电子技术, 2017, 39(7): 1596-1603.
[12]	朱林, 方胜良, 胡卿, 骆盛, 樊甫华. 卫星时变拓扑网络节点重要度评估方法[J]. 系统工程与电子技术, 2017, 39(6): 1274-1279.
[13]	周东青, 王星, 程嗣怡, 陈游. 离散粒子群社区检测算法[J]. 系统工程与电子技术, 2016, 38(2): 428-433.
[14]	徐雪飞, 李建华, 沈迪, 郭蓉, 杨迎辉. 地空多元复杂网络用频优选模型研究[J]. 系统工程与电子技术, 2016, 38(1): 77-83.
[15]	陆余良, 杨斌. 域间路由系统级联失效分析与建模[J]. 系统工程与电子技术, 2016, 38(1): 172-178.