Key nodes identification method of complex network based on two-hop Laplacian centrality

doi:10.23919/JSEE.2026.000030

Abstract

Abstract:

In the study of complex networks, the identification of key nodes is crucial but challenging. Traditional centrality indicators (such as degree, betweenness, and closeness centrality) are difficult to achieve a balance between accuracy, effectiveness and time complexity, time-consuming and resource-consuming, or unable to accurately locate key nodes. In order to solve these problems, based on the commonly used Laplacian centrality (LC), a two-hop LC (TLC) index is proposed, which aims to improve the index recognition performance by introducing second-order neighbor node information. The two-hop degree centrality (TDC) is proposed and combined with LC to derive the TLC, whose superiority is verified through multi-dimensional comparative analysis. Meanwhile, the application of higher-order hop degree centrality in the derivation of LC is deduced, and it is proved that it is not feasible to apply three-hop and above degree centrality to the derivation of LC.

Key words: complex network analysis, key node identification, laplacian centrality, two-hop degree centrality

Weijie Lin, Qinghua Xing, Chengli Fan, Bo Cao, Zhanfu Song, Dengxiu Yu. Key nodes identification method of complex network based on two-hop Laplacian centrality[J]. Journal of Systems Engineering and Electronics, 2026, 37(5): 1691-1702.

Figures/Tables 10

Fig 1

Fig 2

Fig 3

Table 1

Table 2

Table 3

Table 4

Fig 4

Fig 5

Fig 6

References 33

1	Zhong L F. Research on mining algorithms for key nodes in complex networks. Chengdu: University of Electronic Science and Technology of China, 2018. (in Chinese)
2	Dambra J, Wilson C S Explaining perceived performance of the World Wide Web: uncertainty and the task-technology fit model. Internet Research, 2004, 14 (4): 294. doi: 10.1108/10662240410555315
3	Wang Z Y, Chen G, Liu L, et al Cascading risk assessment in power-communication interdependent networks. Physica A: Statistical Mechanics and its Applications, 2020, 540, 120496. doi: 10.1016/j.physa.2019.01.065
4	Phua C, Lee V, Smith K, et al. A comprehensive survey of data mining-based fraud detection research[EB/OL]. [2025-01-01]. https://doi.org/10.48550/arXiv.1009.6119.
5	Li X J, Han S, Xie W K The analysis of logistics influence of the important node cities of Beijing-Tianjin-Hebei. International Journal of Business and Economics Research, 2017, 6, 88. doi: 10.11648/j.ijber.20170605.11
6	Zhao F F, Zeng Y, Xu B A brain-inspired decision-making spiking neural network and its application in unmanned aerial vehicle. Frontiers in Neurorobotics, 2018, 12, 56. doi: 10.3389/fnbot.2018.00056
7	Wen T, Cheong K H, Lai J W, et al Extending the lifespan of multicellular organisms via periodic and stochastic intercellular competition. Physical Review Letters, 2022, 128 (21): 218101. doi: 10.1103/PhysRevLett.128.218101
8	Wang B, Wang Y Y, Sheng J F, et al Identification of key nodes in complex networks based on node trust degree. Journal of Chinese Computer Systems, 2019, 40 (11): 2337.
9	Li Y S, Ma D Z, Zhang H G, et al Critical nodes identification of power systems based on controllability of complex networks. Applied Sciences, 2015, 5 (3): 622. doi: 10.3390/app5030622
10	Albert R, Jeong H, Barabasi A L Error and attack tolerance of complex networks. Nature, 2000, 406 (6794): 378. doi: 10.1038/35019019
11	Yang J X. Research on key node identification algorithms in complex networks[D]. Lanzhou: Lanzhou University of Technology, 2024. (in Chinese)
12	Krnc M, Skrekovski R Group degree centrality and centralization in networks. Mathematics, 2020, 8 (10): 1810. doi: 10.3390/math8101810
13	Lu L, Zhou T, Zhang Q M, et al The H-index of a network node and its relation to degree and coreness. Nature Communications, 2016, 7 (1): 10168. doi: 10.1038/ncomms10168
14	Kartun-giles A P, Bianconi G Beyond the clustering coefficient: a topological analysis of node neighbourhoods in complex networks. Chaos, Solitons & Fractals: X, 2019, 1, 100004.
15	Tang Y. Research on influence maximization based on semi-local centrality and structural holes [D]. Lanzhou: Lanzhou University, 2021. (in Chinese)
16	Zhang Q, Deng R H, Ding K X, et al Structural analysis and the sum of nodes’ betweenness centrality in complex networks. Chaos, Solitons & Fractals, 2024, 185, 115158.
17	Evans T S, Chen B Linking the network centrality measures closeness and degree. Communications Physics, 2022, 5 (1): 172. doi: 10.1038/s42005-022-00949-5
18	Xu Q, Sun L Z, Bu C J The two-steps eigenvector centrality in complex networks. Chaos, Solitons & Fractals, 2023, 173, 113753.
19	Lu P L, Yu Z A node ranking method for complex networks based on degree and H-index extension. Journal of Lanzhou University of Technology, 2020, 46 (5): 100.
20	Liu Y, Tang M, Zhou T, et al Core-like groups result in invalidation of identifying super-spreader by k-shell decomposition. Scientific Reports, 2015, 5 (1): 9602. doi: 10.1038/srep09602
21	Wang G, Sun Z J, Wang T Q, et al Finding influential nodes in complex networks based on Kullback–Leibler model within the neighborhood. Scientific Reports, 2024, 14 (1): 13269. doi: 10.1038/s41598-024-64122-4
22	Xiao Y, Chen Y, Zhang H Y, et al A new semi-local centrality for identifying influential nodes based on local average shortest path with extended neighborhood. Artificial Intelligence Review, 2024, 57 (5): 115. doi: 10.1007/s10462-024-10725-2
23	Zhao L, Sun P, Zhang J Y, et al A complex network important node identification based on the KPDN method. Applied Sciences, 2023, 13 (14): 8303. doi: 10.3390/app13148303
24	Wang B, Zhang J K, Dai J Y, et al Influential nodes identification using network local structural properties. Scientific Reports, 2022, 12 (1): 1833. doi: 10.1038/s41598-022-05564-6
25	Chaharborj S S, Nabi K N, Feng K L, et al Controlling COVID-19 transmission with isolation of influential nodes. Chaos, Solitons & Fractals, 2022, 159, 112035.
26	Zhao N, Bao J J, Chen N Ranking influential nodes in complex networks with information entropy method. Complexity, 2020, 2020 (1): 5903798.
27	Albert R, Barabasi A L Statistical mechanics of complex networks. Reviews of Modern Physics, 2002, 74 (1): 47. doi: 10.1103/RevModPhys.74.47
28	Freeman L C Centrality in social networks: conceptual clarification. Social Networks, 2002, 1 (3): 238.
29	Borgatti S P, Everett M G A graph-theoretic perspective on centrality. Social Networks, 2006, 28 (4): 466. doi: 10.1016/j.socnet.2005.11.005
30	Freeman L C A set of measures of centrality based on betweenness. Sociometry, 1977, 40 (1): 35.
31	Qi X, Duval R D, Christensen K, et al Terrorist networks, network energy and node removal: a new measure of centrality based on Laplacian energy. Social Networking, 2013, 2 (1): 19. doi: 10.4236/sn.2013.21003
32	Phalke S, Vaidya Y, Metkar S. Big-O time complexity analysis of algorithm[C]// Signal and Information Processing, 2022: 1.
33	Mala F A, Ali R The Big-O of mathematics and computer science. Journal of Applied Mathematics and Computation, 2022, 6 (1): 1.

Node	DC	CC	BC	LC	TLC	SIR
0	3	0.381	0	0.318	640	523
1	4	0.411	0	0.393	810	705
2	4	0.431	0	0.393	808	703
3	3	0.379	0	0.343	682	538
4	3	0.275	0	0.306	564	544
5	4	0.485	0	0.368	734	712
6	6	0.529	14	0.579	1380	1062
7	3	0.378	0	0.294	520	544
8	1	0.301	0	0.122	166	194
9	5	0.667	0	0.394	796	905
10	4	0.455	0	0.393	860	706

Index	TLC	LC	DC	CC	BC	SIR
TLC	1	0.878	0.253	0.153	0.383	0.857
LC	0.878	1	0.277	0.165	0.440	0.850
DC	0.253	0.277	1	0.123	0.219	0.284
CC	0.153	0.165	0.123	1	0.367	0.173
BC	0.383	0.440	0.219	0.367	1	0.450
SIR	0.857	0.850	0.284	0.173	0.450	1

Index	Monotonicity
TLC	0.999
LC	0.977
DC	0.741
CC	0.879
BC	0.710

Network	\|V\|	\|E\|	<k>	<d>	β
G₁	83	210	2.413	2.530	0.208
G₂	659	1570	2.368	2.382	0.103
G₃	833	1481	12.61	1.778	0.195
G₄	650	2658	3.810	4.089	0.122
G₅	196	541	2.971	2.760	0.181
G₆	460	1206	3.552	2.622	0.191
G₇	201	994	3.041	4.945	0.253
G₈	463	2541	3.542	5.488	0.223