基于复杂网络传播特性的目标节点重要度评估研究

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

摘要/Abstract

摘要：

在复杂网络中，确定重要目标对于提升系统效率和增强能力至关重要。本文提出一种基于二阶度分解的改进K-shell分解方法。针对复杂网络中的传播特性，将原始K-shell依托节点度分解的步骤替换为依托节点的二阶度分解，并且在相同二阶度分解的K-shell层内，引入改进的网络约束系数用于判定同一K-shell层内的节点是否有更多的结构洞连接。这种方法旨在提供一个更全面和准确地反映节点在网络中的重要性。该方法通过改进的K-shell分解和网络约束系数，有效地评估了不同网络中的关键传播节点。与传统方法相比，该方法在计算复杂度和结果精度方面具有明显的优势，通过实验验证，即使Kendall系数效果不佳，该方法在不同网络中也能有效评估关键传播节点。

关键词: 复杂网络, 二阶度, 节点重要性, K-shell, 传播特性

Abstract:

Identifying critical targets in complex networks is essential for enhancing system efficiency and capabilities. This paper proposes an improved K-shell decomposition method based on second-order degree decomposition. To address the propagation characteristics in complex networks, the original node degree decomposition step in K-shell analysis is replaced with second-order degree decomposition. Furthermore, within the same K-shell layer derived from second-order degree decomposition, an enhanced network constraint coefficient is introduced to evaluate structural hole connections among nodes in identical K-shell layers. This method aims to provide a more comprehensive and accurate reflection of the importance of nodes in the network. Through the improved K-shell decomposition and network constraint coefficients, the method effectively evaluates key propagation nodes in different network. Compared with conventional approaches, it demonstrates superior performance in both computational efficiency and result precision. Experimental validation confirms the method’s robustness in evaluating key propagation nodes across various networks, even when Kendall’s coefficient exhibits sub-optimal performance.

Key words: complex network, second-order degree, node importance, K-shell, propagation property

中图分类号:

TP 301.6

梁威, 孙鹏, 赵亮. 基于复杂网络传播特性的目标节点重要度评估研究[J]. 系统工程与电子技术, 2026, 48(6): 1991-1999.

Wei LIANG, Peng SUN, Liang ZHAO. Research on target node importance evaluation based on complex network propagation characteristics[J]. Systems Engineering and Electronics, 2026, 48(6): 1991-1999.

图/表 11

图1

图2

表1

表2

表3

表4

表5

表6

表7

图3

图4

参考文献 34

1	ZHANG Y H, LU Y L, YANG G Z, et al. Multi-attribute decision-making method for node importance metric in complex network[J]. Applied Sciences, 2022, 12 (4): 1944- 1957. doi: 10.3390/app12041944
2	KANG R, MOU R L, LI L L, et al. Critical path identification and destructive resistance study of aircraft field taxiing[J]. Journal of Chongqing University of Technology （Natural Science）, 2024, 38 (2): 32- 44.
3	CAI X N, ZHENG Z T. Evaluation of node importance in complex networks based on improved random walk[J]. Operations Research and Fuzziology, 2023, 13 (1): 329- 340. doi: 10.12677/ORF.2023.131036
4	YAN H Z, FENG Y, ZHANG W Q, et al. Research on overlapping community detection algorithm of label propagation based on node pair extension[J]. Journal of Physics: Conference Series, 2024, 2898, 012036- 012041. doi: 10.1088/1742-6596/2898/1/012036
5	ZHAO J, SONG Y T, LIU F, et al. The identification of influential nodes based on structure similarity[J]. Connection Science, 2020, 33 (2): 201- 218. doi: 10.1080/09540091.2020.1806203
6	WANG B, ZHANG J K, DAI J Y, et al. Influential nodes identification using network local structural properties[J]. Scientific Reports, 2022, 12 (1): 1833- 1845. doi: 10.1038/s41598-022-05564-6
7	LI Z, HUANG X Y. Identifying influential spreaders by gravity model considering multi-characteristics of nodes[J]. Scientific Reports, 2022, 12 (1): 9879- 9889. doi: 10.1038/s41598-022-14005-3
8	YANG M, SUN H, GENG S Y. On the quantitative resilience assessment of complex engineered systems[J]. Process Safety and Environmental Protection, 2023, 174, 941- 950. doi: 10.1016/j.psep.2023.05.019
9	杨琦, 张雅妮, 周雨晴, 等. 复杂网络理论及其在公共交通韧性领域的应用综述[J]. 中国公路学报, 2022, 35 (4): 215- 229. doi: 10.3969/j.issn.1001-7372.2022.04.018
	YANG Q, ZHANG Y N, ZHOU Y Q, et al. Review of complex network theory and its application in the field of public transport resilience[J]. Highway Journal of China, 2022, 35 (4): 215- 229. doi: 10.3969/j.issn.1001-7372.2022.04.018
10	倪顺江. 基于复杂网络理论的传染病动力学建模与研究[D]. 北京: 清华大学, 2009.
	NI S J. Modeling and study of infectious disease dynamics based on complex network theory [D]. Beijing: Tsinghua University, 2009.
11	YANG H H, AN S. Robustness evaluation for multi-subnet composited complex network of urban public transport[J]. Alexandria Engineering Journal, 2021, 60 (2): 2065- 2074. doi: 10.1016/j.aej.2020.12.016
12	SUN J. Combat network link prediction based on embedding learning[J]. Journal of Systems Engineering and Electronics, 2022, 33 (2): 345- 353. doi: 10.23919/JSEE.2022.000036
13	张嗣瀛. 复杂系统、复杂网络自相似结构的涌现规律[J]. 复杂系统与复杂性科学, 2006, 3 (4): 41- 51. doi: 10.3969/j.issn.1672-3813.2006.04.006
	ZHANG S Y. The emergence law of the self-similarity structure of complex systems and complex networks[J]. Complex Systems and Complexity Science, 2006, 3 (4): 41- 51. doi: 10.3969/j.issn.1672-3813.2006.04.006
14	卫婧. 基于复杂网络拓扑结构软件系统可靠性研究[D]. 西安: 西安电子科技大学, 2018.
	WEI J. Study on system reliability of software based on complex network topology structure [D]. Xi’an: Xidian University, 2018.
15	BARABASI A L, GULBAHCE N. Network medicine: a network-based approach to human disease[J]. Nature Reviews Genetics, 2011, 12 (1): 56- 68. doi: 10.1038/nrg2918
16	ZHU P C, ZHI Y, GUO Y M, et al. Analysis of epidemic spreading process in adaptive networks[J]. IEEE Trans. on Circuits and Systems II: Express Briefs, 2019, 66 (7): 1252- 1256.
17	CSERMELY P, KORCSMAROS T, KISS H J M, et al. Structure and dynamics of molecular networks: a novel paradigm of drug discovery a comprehensive review[J]. Pharmacology & Therapeutics, 2013, 138 (3): 333- 408. doi: 10.1016/j.pharmthera.2013.01.016
18	XU W Z, LI T, LIANG W F, et al. Identifying structural hole spanners to maximally block information propagation[J]. Information Sciences, 2019, 505, 100- 126. doi: 10.1016/j.ins.2019.07.072
19	MAO Z F, JIANG S F. Review of engineering change[J]. Light Industry Machinery, 2015, 33 (4): 106- 110.
20	周中月. 基于复杂网络的谣言溯源技术研究[D]. 乌鲁木齐: 新疆师范大学, 2021.
	ZHOU Z Y. Research on rumor traceability technology based on complex network [D]. Wulumuqi: Xinjiang Normal University, 2021.
21	王爱华, 李辉. 网络黑产犯罪的复杂结构识别与精准治理探究—基于复杂网络理论的分析[J]. 中国人民公安大学学报（社会科学版）, 2022, 38 (5): 9- 18.
	WANG A H, LI H. Exploration on the complex structure identification and accurate governance of network black production crime—analysis based on complex network theory[J]. Journal of People’s Public Security University of China （Social Science Edition）, 2022, 38 (5): 9- 18.
22	CASTELLANO N G, CERQUETI R, FRANCES B M. Evaluating risks-based communities of Mafia companies: a complex networks perspective[J]. Review of Quantitative Finance and Accounting, 2021, 57 (4): 1463- 1486. doi: 10.1007/s11156-021-00984-3
23	SPADON G, SCABORA L C, OLIVEIRA P H, et al. Behavioral characterization of criminality spread in cities[J]. Procedia Computer Science, 2017, 108, 2537- 2541. doi: 10.1016/j.procs.2017.05.118
24	LI Y, WEI L S, LIU J L, et al. Secure state estimation for complex networks with multi-channel oriented round robin protocol[J]. Nonlinear Analysis: Hybrid Systems, 2023, 49, 101371- 101385. doi: 10.1016/j.nahs.2023.101371
25	ZHANG H W, MI Y, FU Y M, et al. Security defense decision method based on potential differential game for complex networks[J]. Computers & Security, 2023, 129, 103187- 103197. doi: 10.1016/j.cose.2023.103187
26	WU H Y, LIU Q S. Secure synchronization for multiple coupled complex networks with time-varying delays under DoS attacks[J]. International Journal of Control, 2023, 97 (11): 2526- 2538. doi: 10.1080/00207179.2023.2284254
27	李柳池. 空管运行复杂安全网络理论模型构建研究[D]. 德阳: 中国民用航空飞行学院, 2023.
	LI L C. Research on the theoretical model construction of complex safety network in air traffic control operation [D]. Deyang: The Civil Aviation Flight Academy of China, 2023.
28	AMREEN A, TANVIR A, MUSHEER A, et al. A complex network-based approach for security and governance in the smart green city[J]. Expert Systems with Applications, 2022, 214, 119094- 119105. doi: 10.1016/j.eswa.2022.119094
29	MA J L, XIANG T T, ZHAO Y B. Epidemic spreading dynamics on two-layer complex networks[J]. International Journal of Modern Physics C: Computational Physics & Physical Computation, 2024, 35(3): 2450023.
30	阮逸润, 老松杨, 汤俊, 等. 基于引力方法的复杂网络节点重要度评估方[J]. 物理学报, 2022, 71 (17): 298- 309.
	RUAN Y R, LAO S Y, TANG J, et al. Assessment of node importance in complex networks based on gravitational methods[J]. Journal of Physics, 2022, 71 (17): 298- 309.
31	尹梦梦, 王磊, 姚昌华, 等. 基于 VIKOR 模型的复杂网络节点重要度评估[J]. 信息网络安全, 2022, 22 (1): 87- 94. doi: 10.3969/j.issn.1671-1122.2022.01.011
	YIN M M, WANG L, YAO C H, et al. Assessment of node importance in complex networks based on the VIKOR model[J]. Information Network Security, 2022, 22 (1): 87- 94. doi: 10.3969/j.issn.1671-1122.2022.01.011
32	李世魁. 基于复杂网络拓扑结构的重要节点识别方法研究 [D]. 兰州: 兰州交通大学, 2022.
	LI S K. Research on the important node identification method based on complex network topology [D]. Lanzhou: Lanzhou Jiaotong University, 2022.
33	CAO B W, GUAN G, SHEN S L, et al. Dynamical behaviors of a delayed SIR information propagation model with forced silence function and control measures in complex networks[J]. The European Physical Journal Plus, 2023, 138 (5): 402- 406. doi: 10.1140/epjp/s13360-023-04005-1
34	KIM H S, BEZNOSOV K, YONEKI E. Finding influential neighbors to maximize information diffusion in twitter[C]//Proc. of the 23rd International Conference on World Wide Web, 2014: 701−706.

维度	病毒传播（SIR模型）	本文方法（IKSP-2D）
传播驱动力	动态感染率（β）与恢复率（γ）	静态网络拓扑结构（度、结构洞、层间差异）
反馈机制	无需反馈，单向传播	无动态反馈，依赖结构特征的间接“反馈”（如INCC修正权重）
适用场景	实时传播模拟（如疫情预测）	关键节点预筛选（如网络加固、传播源头控制）
传播驱动力	动态感染率（β）与恢复率（γ）	静态网络拓扑结构（度、结构洞、层间差异）
计算复杂度	高（需多次仿真，时间复杂度$ O({N}^{3}) $）	低（单次结构分析，时间复杂度$ O(N+E+N\cdot \left\langle k \right\rangle ) $）

数据集名称	节点	边数	平均度	图密度/%	聚类系数/%
Infect-hyper	113	2196	19.4336	17.35	53.48
Infect-dublin	410	2765	6.7439	1.65	45.58
DD244	291	822	2.8247	0.97	51.59
Infect-euroroad	1174	1417	1.2070	0.10	1.67
Mammalia-dophin- florida-social	151	1554	10.2913	6.86	78.82

节点重要度	DC	CI	BC	K-shell	HC	CC	IKSP-2D	ISM	CR
1	284	7	402	181	401	401	284	284	157
2	236	43	284	499	7	402	848	7	950
3	107	284	277	180	402	403	847	107	544
4	137	499	453	454	453	432	405	137	187
5	39	107	452	7	411	1019	404	43	120
6	7	401	403	234	253	253	310	401	541
7	401	137	401	179	403	452	297	39	1145
8	181	39	404	107	232	404	296	236	673
9	499	236	837	673	400	232	291	499	700
10	141	181	836	541	452	284	285	181	121

节点重要度	DC	CI	BC	K-shell	HC	CC	IKSP-2D	ISM	CR
1	116	116	111	124	116	116	48	24	4
2	111	111	116	119	111	111	3	3	101
3	119	119	3	118	24	119	118	61	66
4	24	24	43	108	119	24	32	101	40
5	63	63	119	148	63	63	94	56	111
6	3	3	23	101	3	3	108	4	3
7	101	101	146	98	146	146	124	116	2
8	129	129	48	94	101	61	67	40	99
9	61	61	32	89	129	101	28	32	70
10	146	146	24	67	61	129	146	89	63

节点重要度	DC	CI	BC	K-shell	HC	CC	IKSP-2D	ISM	CR
1	157	157	274	410	157	274	183	157	2
2	304	304	304	380	274	157	12	304	50
3	372	148	157	362	304	243	200	372	222
4	148	372	243	343	333	333	7	274	300
5	314	333	333	291	243	1	193	333	111
6	217	314	30	286	148	304	148	314	90
7	282	282	212	283	1	150	372	217	99
8	60	274	148	239	372	297	270	305	7
9	286	217	297	235	150	30	74	150	9
10	333	210	218	182	314	305	201	318	200