面向目标体系网络的节点重要性排序方法

doi:10.12382/bgxb.2022.0762

摘要/Abstract

摘要：

针对现有复杂网络节点重要性排序方法无法处理目标体系网络节点异质连边有向有权的难题,提出一种面向目标体系网络的节点重要性排序方法。利用K-shell算法计算网络节点的初始重要值,并在PageRank算法的节点重要性传递中考虑重要性分配趋强的特点和连边权重,提出K-shell和PageRank扩展(Extended K-shell and PageRank,EKSPR)算法,并给出EKSPR算法的收敛性证明,进行了作战仿真实验验证和算例对比分析。实验结果表明,EKSPR算法相对于K-shell算法和PageRank算法更适用于处理目标体系网络节点重要性排序,并且效率优于均值EKSPR算法。

关键词: 目标体系网络, 节点重要性, K-shell算法, PageRank算法, K-shell和PageRank扩展算法

Abstract:

The existing node importance ranking methods of complex networks cannot deal with the target system of systems (SoS) network with heterogeneous nodes and directed and weighted edges. To solve this problem, a node importance ranking method for the target SoS network is proposed. It uses the K-shell algorithm to calculate the initial importance value of network nodes. In the node importance transfer of the PageRank algorithm, the characteristics of strong importance distribution and edge weight are considered. The extended K-shell and PageRank (EKSPR) algorithm is proposed, and the convergence proof of the EKSPR algorithm is given. It is verified by the combat simulation experiment and compared with the numerical example. The experimental results show that the EKSPR algorithm is more suitable than the K-shell and PageRank algorithms for the node importance ranking of the target SoS network, and that its efficiency is better than the average EKSPR algorithm.

Key words: target SoS network, node importance, K-shell algorithm, PageRank algorithm, extended K-shell and PageRank algorithm

中图分类号:

TP391

袁博文, 刘东波, 刘兆鹏, 杨伟龙. 面向目标体系网络的节点重要性排序方法[J]. 兵工学报, 2024, 45(2): 488-496.

YUAN Bowen, LIU Dongbo, LIU Zhaopeng, YANG Weilong. Node Importance Ranking Method for Target SoS Network[J]. Acta Armamentarii, 2024, 45(2): 488-496.

图/表 10

参考文献 25

[1]	陈晓楠, 胡建敏, 池本亮, 等. 复杂作战网络体系博弈与重构方法[J]. 兵工学报, 2021, 42(5): 1111-1120. doi: 10.3969/j.issn.1000-1093.2021.05.024
	CHEN X N, HU J M, CHI B L, et al. Game and reconfiguration method of complex combat network system[J]. Acta Armamentarii, 2021, 42(5): 1111-1120. (in Chinese) doi: 10.3969/j.issn.1000-1093.2021.05.024
[2]	艾伯特-拉斯洛·巴拉巴西. 网络科学[M]. 沈华伟, 黄俊铭, 译. 郑州: 河南科学技术出版社, 2020.
	ALBERT-L B. Network science[M]. SHEN H W, HUANG J M, translated. Zhengzhou: Henan Science and Technology Press, 2020. (in Chinese)
[3]	张强, 李建华, 沈迪, 等. 基于复杂网络的作战体系网络建模与优化研究[J]. 系统工程与电子技术, 2015, 37(5): 1066-1071.
	ZHANG Q, LI J H, SHEN D, et al. Research on network modeling and optimization of operation systems based on complex network[J]. Systems Engineering and Electronics, 2015, 37(5): 1066-1071. (in Chinese)
[4]	CARES J R. An information age combat model[C]//Proceedings of the 9th International Command and Control Research and Technology Symposium. Copenhagen, Denmark: Command and Control Research Program, 2004.
[5]	李尔玉, 龚建兴, 黄健. 基于功能链的融合网络功能抗毁性评估[J]. 兵工学报, 2019, 40(7): 1450-1459. doi: 10.3969/j.issn.1000-1093.2019.07.015
	LI E Y, GONG J X, HUANG J. Analysis about functional invulnerability of convergent network based on function chain[J]. Acta Armamentarii, 2019, 40(7): 1450-1459. (in Chinese) doi: 10.3969/j.issn.1000-1093.2019.07.015
[6]	谢丽霞, 孙红红, 杨宏宇, 等. 基于K-shell的复杂网络关键节点识别方法[J]. 清华大学学报(自然科学版), 2022, 62(5): 849-961.
	XIE L X, SUN H H, YANG H Y, et al. Key node recognition in complex networks based on the K-shell method[J]. Journal of Tsinghua University (Science and Technology), 2022, 62(5): 849-961. (in Chinese)
[7]	NAMTIRTHA A, DUTTA A, DUTTA B. Weighted kshell degree neighborhood: a new method for identifying the influential spreaders from a variety of complex network connectivity structures[J]. Expert Systems with Application, 2020, 139: 112859. doi: 10.1016/j.eswa.2019.112859 URL
[8]	BERAHMAND K, BOUYER A, SAMADI N. A new local and multidimensional ranking measure to detect spreaders in social networks[J]. Computing, 2019, 101(11): 1711-1733. doi: 10.1007/s00607-018-0684-8
[9]	BASARAS P, KATSAROS D, TASSIULAS L. Detecting influential node ranking in complex social networks[J]. Computer, 2013, 46(4): 24-49.
[10]	LÜ L Y, ZHANG Y C, YEUNG C H, et al. Leaders in social networks, the delicious case[J]. PloS One, 2011, 6(6): 21202. doi: 10.1371/journal.pone.0021202 pmid: 21738620
[11]	SU Q Y, CHEN C, SUN Z L, et al. Identification of critical nodes for cascade faults of grids based on electrical PageRank[J]. Global Energy Interconnection, 2021, 4(6): 587-595. doi: 10.1016/j.gloei.2022.01.006 URL
[12]	GU K, FAN Y, DI Z R. Signed PageRank on online rating system[J]. Journal of Systems Science & Complexity, 2022, 35(1): 58-80.
[13]	KOENE J. Applied network analysis: a methodological introduction[J]. North-Holland, 1984, 17(3): 422-423.
[14]	YAN X L, CUI Y P, NI S J. Identifying influential spreaders in complex networks based on entropy weight method and gravity law[J]. Chinese Physics B, 2020, 29(4): 048902. doi: 10.1088/1674-1056/ab77fe
[15]	FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35-41. doi: 10.2307/3033543 URL
[16]	ULLAH A, WANG B, SHENG J F, et al. Identification of influential nodes via effective distance-based centrality mechanism in complex networks[J]. Complexity, 2021, 2021: 8403738.
[17]	WANG J S, WU X P, BO Y, et al. Improved method of node importance evaluation based on node contraction in complex networks[J]. Procedia Engineering, 2011, 15(1): 1600-1604. doi: 10.1016/j.proeng.2011.08.298 URL
[18]	BONACICH P. Factoring and weighting approaches to status scores and clique identification[J]. The Journal of Mathematical Sociology, 1972, 2(1):113-120. doi: 10.1080/0022250X.1972.9989806 URL
[19]	DAI J Y, WANG B, SHENG J F, et al. Identifying influential nodes in complex networks based on local neighbor contribution[J]. IEEE Access, 2019, 7: 131719-131731. doi: 10.1109/ACCESS.2019.2939804 URL
[20]	郭程远, 陈鸿昶, 王庚润, 等. 复杂网络节点重要性排序算法及应用综述[J]. 信息工程大学学报, 2021, 22(3): 313-320, 358.
	GUO C Y, CHEN H C, WANG G R, et al. Node importance ranking based on complex network[J]. Journal of Information Engineering University, 2021, 22(3): 313-320, 358. (in Chinese)
[21]	KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6: 888-893. doi: 10.1038/nphys1746
[22]	BRIN S, PAGE L. The anatomy of a large-scale hyper-textual web search engine[J]. Comput Networks and ISDN System, 1998, 30(1-7):107-117. doi: 10.1016/S0169-7552(98)00110-X URL
[23]	ORTEGA J M, RHEINBOLDT W C. Iterative solution of nonlinear equations in several variables[M]. New York, NY, US: Academic Press,1970.
[24]	施仁杰. 马尔科夫链基础及其应用[M]. 西安: 西安电子科技大学出版社, 1992.
	SHI R J. The basis of Markov chain and its application[M]. Xi’an: Xidian University Press, 1992. (in Chinese)
[25]	汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用[M]. 北京: 清华大学出版社, 2006:9-11.
	WANG X F, LI X, CHEN G R. Complex network theory and its application[M]. Beijing: Tsinghua University Press, 2006: 9-11. (in Chinese)

阵营	武器装备	部署地	数量
蓝方	指挥所C	Area-1	1
蓝方	远程防空武器系统A₁	Area-1	1
蓝方	近程防空武器系统A₂	Area-1	1
蓝方	雷达站L	Area-1	1
蓝方	机场J	Area-1	1
蓝方	S1型驱逐舰	Area-2附近	2
蓝方	S2型巡洋舰	Area-2附近	2
蓝方	S3型航母	Area-2附近	1
蓝方	S4型海洋监测船	Area-2附近	2
蓝方	F1型战斗机	机场J	14
蓝方	R型侦察无人机	机场J	2
蓝方	F2型舰载战斗机	S3型航母	12
蓝方	E型预警机	S3型航母	2

阵营	武器装备	部署地	数量
蓝方	指挥所C	Area-1	1
蓝方	远程防空武器系统A₁	Area-1	1
蓝方	近程防空武器系统A₂	Area-1	1
蓝方	雷达站L	Area-1	1
蓝方	机场J	Area-1	1
蓝方	S1型驱逐舰	Area-2附近	2
蓝方	S2型巡洋舰	Area-2附近	2
蓝方	S3型航母	Area-2附近	1
蓝方	S4型海洋监测船	Area-2附近	2
蓝方	F1型战斗机	机场J	14
蓝方	R型侦察无人机	机场J	2
蓝方	F2型舰载战斗机	S3型航母	12
蓝方	E型预警机	S3型航母	2

节点	K-shell 算法	PageRank 算法	均值EKSPR 算法	EKSPR 算法
v₁	1	0.057372	0.012315	0.012315
v₂	2	0.008605	0.052366	0.052366
v₃	2	0.029334	0.054918	0.054918
v₄	2	0.045323	0.035497	0.035497
v₅	2	0.064368	0.036450	0.036450
v₆	2	0.073093	0.020504	0.020504
v₇	1	0.254715	0.009373	0.009373
v₈	2	0.025516	0.009748	0.009748
v₉	2	0.025098	0.014805	0.014805
v₁₀	3	0.026572	0.081312	0.081312
v₁₁	3	0.052292	0.069325	0.069325
v₁₂	2	0.058110	0.024147	0.024147
v₁₃	2	0.019042	0.019471	0.019471
v₁₄	2	0.027717	0.021787	0.021787
v₁₅	2	0.014966	0.019367	0.019367
v₁₆	2	0.014966	0.019367	0.019367
v₁₇	2	0.047572	0.029494	0.029494
v₁₈	2	0.043824	0.095073	0.095073
v₁₉	3	0.062392	0.247671	0.247671
v₂₀	3	0.022539	0.099596	0.099596
v₂₁	2	0.026572	0.027403	0.027403

节点	K-shell 算法	PageRank 算法	均值EKSPR 算法	EKSPR 算法
v₁	1	0.057372	0.012315	0.012315
v₂	2	0.008605	0.052366	0.052366
v₃	2	0.029334	0.054918	0.054918
v₄	2	0.045323	0.035497	0.035497
v₅	2	0.064368	0.036450	0.036450
v₆	2	0.073093	0.020504	0.020504
v₇	1	0.254715	0.009373	0.009373
v₈	2	0.025516	0.009748	0.009748
v₉	2	0.025098	0.014805	0.014805
v₁₀	3	0.026572	0.081312	0.081312
v₁₁	3	0.052292	0.069325	0.069325
v₁₂	2	0.058110	0.024147	0.024147
v₁₃	2	0.019042	0.019471	0.019471
v₁₄	2	0.027717	0.021787	0.021787
v₁₅	2	0.014966	0.019367	0.019367
v₁₆	2	0.014966	0.019367	0.019367
v₁₇	2	0.047572	0.029494	0.029494
v₁₈	2	0.043824	0.095073	0.095073
v₁₉	3	0.062392	0.247671	0.247671
v₂₀	3	0.022539	0.099596	0.099596
v₂₁	2	0.026572	0.027403	0.027403