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

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

Abstract

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

CLC Number:

TP393

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

Figures/Tables 9

Fig.1

Table 1

Fig.2

Fig.3

Table 2

Table 3

Table 4

Fig.4

Fig.5

References 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]	Bingxue ZHANG, Xisheng LI, Jia YOU, Weiren SONG. End-edge collaborative network generation algorithm based on node composite characteristics [J]. Systems Engineering and Electronics, 2023, 45(8): 2588-2596.
[2]	Cong WANG, Huiliang SHEN, Yongxiang XIA, Guanghan BAI, Yining FANG. Analysis of critical nodes in equipment support system [J]. Systems Engineering and Electronics, 2022, 44(10): 3134-3142.
[3]	Yantao WANG, Zheng YANG. Propagation and control improvement of flight operation risk network [J]. Systems Engineering and Electronics, 2021, 43(9): 2544-2552.
[4]	Kexin BI, Minggong WU, Wenbin ZHANG, Xiangxi WEN, Kan DU. Modeling and analysis of flight conflict network based onvelocity obstacle method [J]. Systems Engineering and Electronics, 2021, 43(8): 2163-2173.
[5]	Ang LI, Dangmin NIE, Xiangxi WEN, Zekun WANG, Chengxiu YANG. Operation situation assessment of control system based on interdependent network and SVM [J]. Systems Engineering and Electronics, 2021, 43(5): 1287-1294.
[6]	Lingfeng GU, Ming HE, Guoyou CHEN, Minhui JI, Jintao LIU. Research on unmanned aerial vehicle swarm system resilience [J]. Systems Engineering and Electronics, 2021, 43(1): 156-162.
[7]	LI Jiawei, WU Minggong, WEN Xiangxi, LIU Fei. Identifying key nodes and edges of complex networks based on the minimum connected dominating set [J]. Systems Engineering and Electronics, 2019, 41(11): 2541-2549.
[8]	WANG Ershen, WANG Yuwei, QU Pingping, LAN Xiaoyu, CHEN Jiamei. Effectiveness analysis of complex network edge attack strategy with cost [J]. Systems Engineering and Electronics, 2018, 40(4): 919-926.
[9]	HAO Yucheng, LI Chengbing, WEI Lei. Cascading failure model of complex networks considering overloaded nodes [J]. Systems Engineering and Electronics, 2018, 40(10): 2282-2287.
[10]	ZAN Xiang, CHEN Chunliang, ZHANG Shixin, CHEN Weilong, ZHANG Lijun. Dynamic evaluation method for equipment important degree considering weight-evolving [J]. Systems Engineering and Electronics, 2017, 39(9): 2022-2030.
[11]	WANG Yunming, PAN Chengsheng, CHEN Bo, ZHANG Duoping. Evolution model of weighted command and control network based on local world [J]. Systems Engineering and Electronics, 2017, 39(7): 1596-1603.
[12]	ZHU Lin, FANG Shengliang, HU Qing, LUO Sheng, FAN Fuhua. Evaluation method for time-varying satellite topology network node importance [J]. Systems Engineering and Electronics, 2017, 39(6): 1274-1279.
[13]	XU Jianguo, LI Mengjun, JIANG Jiang, YOU Hanlin. Data-driven motif analysis of technology breakthrough network [J]. Systems Engineering and Electronics, 2017, 39(5): 1072-1077.
[14]	ZHOU Dong-qing, WANG Xing, CHENG Si-yi, CHEN You. Community detection algorithm via discrete PSO [J]. Systems Engineering and Electronics, 2016, 38(2): 428-433.
[15]	XU Xue-fei, LI Jian-hua, SHEN Di, GUO Rong, YANG Ying-hui. Research of air-ground multi-element frequency optimization model in complex networks [J]. Systems Engineering and Electronics, 2016, 38(1): 77-83.

Network damage maximization algorithm based on topology potential

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 31

Related Articles 15

Recommended Articles

Metrics

Comments

算法比较	γ
算法比较	1.5	2	2.5	3	3.5	4	4.5	5
R_TPCELF>R_GABIN	12	4	10	22	12	15	8	12
R_TPCELF < R_GABIN	54	19	36	21	5	3	2	1
R_TPCELF=R_GABIN	34	77	54	57	83	82	90	87
R_TPCELF≥R_others	93	93	89	99	97	100	100	100
R_GABIN≥R_others	95	97	89	99	97	100	99	100