A method of identifying key nodes in complex networks based on weighted cycle ratio

XIE Hanchen; WU Minggong; WEN Xiangxi; ZHANG Mingyu

doi:10.7498/aps.74.20250338

Abstract
In the face of the surge of air transport demand and the increasing risk of flight conflicts, it is very important to effectively manage flight conflicts and accurately identify key conflict aircraft. This paper presents a novel method for identifying critical nodes in flight conflict networks by integrating complex network theory with a weighted cycle ratio (WCR). By modeling aircraft as nodes and conflict relationships as edges, we construct a flight conflict network where the urgency of conflicts is reflected in edge weights. We extend the traditional cycle ratio (CR) concept to propose the WCR, which accounts for both the topological structure of the network and the urgency of conflicts. Furthermore, we combine the WCR with node strength (NS) to form an adjustable mixed indicator (MI) that adaptively balances the importance of nodes based on their involvement in cyclic conflict structure and their individual conflict strength. Through extensive simulations, including node deletion experiments and network robustness analyses, we demonstrate that our method can precisely pinpoint critical nodes in flight conflict networks. The results indicate that regulating these critical nodes can significantly reduce network complexity and conflict risks. Importantly, the effectiveness of our method increases with the complexity of the flight conflict network, making it particularly suitable for scenarios with high aircraft density and complex conflict patterns. Overall, this study not only deepens the theoretical understanding of complex aviation network analysis but also provides a practical tool for improving air traffic control efficiency and safety, thereby contributing to achieving more environmentally friendly and sustainable air transportation.

Keywords:
complex network /

cycle ratio /

weighted cycle ratio /

vital node
FullText HTML

Cited By

图 1 树状网络脆弱性示例

Figure 1. Examples of tree network vulnerabilities.

DownLoad: Full-Size Img PowerPoint

图 2 树状网络节点删除示例

Figure 2. Example of node removal in a tree-like network.

DownLoad: Full-Size Img PowerPoint

图 3 示例网络及圈矩阵　(a)示例网络拓扑结构; (b)圈矩阵及节点1圈比的计算过程

Figure 3. Example network and cycle ratio matrix: (a) Example network topology; (b) cycle matrix and node 1 cycle ratio procedure.

DownLoad: Full-Size Img PowerPoint

图 4 加权示例网络及加权圈比矩阵　(a)加权示例网络拓扑结构; (b)加权圈矩阵及节点1加权圈比计算过程

Figure 4. Weighted example network and weighted cycle ratio matrix: (a) Weighted example network topology; (b) weighted cycle matrix and node 1 weighted cycle ratio calculation procedure.

DownLoad: Full-Size Img PowerPoint

图 5 示例网络2拓扑结构

Figure 5. Example network 2 topology.

DownLoad: Full-Size Img PowerPoint

图 6 改进后的加权圈矩阵及节点1加权圈比的计算过程

Figure 6. Improved weighted cycle matrix and calculation procedure for node 1 weighted cycle ratio.

DownLoad: Full-Size Img PowerPoint

图 7 网络中节点重要性6个指标的平均相关性矩

Figure 7. Average correlation moments for six indicators of node importance in the network.

DownLoad: Full-Size Img PowerPoint

图 8 邮件网络节点排名可视图

Figure 8. E-mail network node ranking viewable.

DownLoad: Full-Size Img PowerPoint

图 9 海豚社交网络节点排名可视图

Figure 9. Dolphin network node ranking viewable.

DownLoad: Full-Size Img PowerPoint

图 10 6种节点重要性指标对6种真实网络节点移除的网络效率变化

Figure 10. Changes in network efficiency of six node importance metrics for six real network node removals.

DownLoad: Full-Size Img PowerPoint

图 11 不同时刻节点累积数量

Figure 11. Cumulative number of nodes at different moments.

DownLoad: Full-Size Img PowerPoint

图 12 不同时刻指标排名

Figure 12. Ranking of indicators at different moments.

DownLoad: Full-Size Img PowerPoint

图 A1 网络拓扑结构　(a) Dolphinq网络; (b) Email网络

Figure A1. Network topology (a) Dolphinq network; (b) Email network.

DownLoad: Full-Size Img PowerPoint

表 1 每个节点的基本圈以及其他指标的值

Table 1. Value of the base cycle for each node as well as other metrics.

节点	基本圈	WCR	WCR¹	CR	NS	BC	CC	EC
1	{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 2, 5}	2.72	3.76	3.92	1.93	5	0.101	0.158
2	{2, 3, 1}, {2, 4, 1}, {2, 5, 1}, {2, 4, 3}	2.98	3.80	3.92	1.47	25.75	0.117	0.099
3	{3, 1, 4}, {3, 2, 4}, {3, 2, 1}, {3, 10, 11, 9}	3.63	4.78	5.67	2.60	22	0.109	0.170
4	{4, 1, 2}, {4, 1, 3}, {4, 2, 3}	1.90	2.33	2.50	1.47	2.25	0.100	0.080
5	{5, 1, 2}	1.32	1.57	1.50	2.13	21	0.105	0.143
6		0	0	0	0.60	0	0.051	0.031
7		0	0	0	2.07	17	0.070	0.092
8		0	0	0	0.53	0	0.053	0.027
9	{9, 11, 10, 3}	2.156	2.38	3.25	0.60	8	0.099	0.027
10	{9, 11, 10, 3}	1.90	2.38	3.25	1.73	0	0.058	0.117
11	{9, 11, 10, 3}	2.47	3	3.25	1.20	0	0.074	0.055

DownLoad: CSV

表 2 6个真实网络的基本拓扑特征

Table 2. Six basic topological characteristics of real networks.

	节点	连边	平均度	同配性	平均聚类系数
Usa	332	2.1 k	12	–0.20788	0.625
Dolphin	291	3.2 k	21	0.177476	0.68233
Email	906	12.1 k	26	–0.0878	0.6139
Rw496	496	2 k	7	0.045056	0.395
Road	1.2 k	1.4 k	2	0.126684	0.0167
Advogato	5.2 k	47.3 k	18	–0.0834	0.2868

DownLoad: CSV

表 3 邮件网络部分节点排序

Table 3. Email network partial node ordering.

排名	指标
排名	CR	WCR	NS	BC	CC	EC
1	1874	1874	1874	1669	599	1874
2	1258	1258	1258	1874	1669	1258
3	453	999	999	599	1731	999
4	999	453	1586	453	1874	1963
5	1669	1963	1963	713	1854	1586
6	1586	1669	1576	1952	272	1576
7	1963	1586	1987	702	339	1987
8	203	1159	1120	1258	344	1792
9	1987	1768	1792	511	1453	1120
10	1159	203	1669	1159	1782	465
11	511	1377	419	272	74	1323
12	1768	1440	1440	585	92	419
13	412	511	1323	1563	108	1669
14	1440	1987	465	1987	136	1440
···	···	···	···	···	···	···
n	2029	2029	2028	2029	2028	984

DownLoad: CSV

表 4 海豚社交网络部分节点排序

Table 4. Dolphin network partial node ordering.

排名	指标
排名	CR	WCR	NS	BC	CC	EC
1	202	202	43	89	118	43
2	32	118	118	79	202	118
3	118	32	32	32	129	232
4	185	185	173	271	173	243
5	173	173	202	202	174	49
6	4	43	232	133	4	185
7	271	4	107	174	32	107
8	222	232	243	4	35	202
9	174	107	185	222	42	173
10	43	174	49	35	133	32
11	201	222	20	47	135	164
12	232	271	164	118	218	20
13	86	201	4	291	222	266
14	47	243	86	201	243	225
···	···	···	···	···	···	···
n	156	156	156	285	156	274

DownLoad: CSV

表 5 不同指标下各网络的鲁棒性R

Table 5. The robustness of each network under different metrics R.

Networks	CR	WCR	NS	BC	CC	EC
USAair	0.0740	0.0738	0.1047	0.0817	0.2520	0.1147
Dolphin	0.3801	0.3713	0.4293	0.3577	0.3793	0.3889
Email	0.0173	0.0141	0.0205	0.0146	0.0287	0.1003
Rw496	0.2177	0.1548	0.200	0.1919	0.2508	0.2150
Road	0.1341	0.1031	0.1221	0.0979	0.1838	0.3152
Advogato	0.2746	0.2575	0.2800	0.2632	0.706	0.3006

DownLoad: CSV

表 6 各指标下的平均排名和R平均值

Table 6. Average ranking and R-mean under each indicator.

	CR	WCR	NS	BC	CC	EC
平均排名	3.67	1.5	4.167	1.67	4.67	5.3
R平均值	0.1830	0.1626	0.1928	0.1678	0.2275	0.2391

DownLoad: CSV

表 7 各指标下累积节点排名

Table 7. Cumulative node rankings under each indicator.

	t =1	t = 2	t = 4	t = 6	t = 8	t = 10	平均排名
CR	2.67	2. 83	2.83	2.67	2.67	2.67	2.72
WCR	1.67	1. 50	1.33	1.33	1.33	1.33	1.42
NS	3.50	4.00	4.50	4.50	4.50	4.50	4.25
BC	3.33	2.83	2.50	2.50	2.50	2.50	2.69
CC	4.67	4.67	4.67	4.83	4.83	4.83	4.75
EC	5.17	5.17	5.17	5.17	5.17	5.17	5.17

DownLoad: CSV

表 A1 Email和Advogato网络中CR与WCR指标下节点排名

Table A1. Ranking of nodes under CR and WCR metrics in E-mail and Advogato networks.

排名	Email		Advogato
排名	CR WCR		CR WCR
1	1874	1874	157	157
2	1258	1258	46	46
3	453	999	597	597
4	999	453	30	30
5	1669	1963	232	126
6	1586	1669	328	328
7	1963	1586	126	232
8	203	1159	438	438
9	1987	1768	286	286
10	1159	203	1223	610
11	511	1377	610	1223
12	1768	1440	429	62
13	412	511	9	1378
14	1440	1987	736	429
15	1792	412	62	736
16	1377	457	22	22
17	457	1792	1378	780
18	1706	1576	780	9
19	585	1587	19	604
20	1751	585	326	326
21	1587	852	604	19
22	1952	1144	194	175
23	1144	1833	329	739
24	852	1751	214	329
25	1278	1323	739	214
26	713	1278	1775	1992
27	1277	1277	1992	172
28	1576	1510	801	45
29	155	155	172	719
30	1287	1952	175	1775
31	350	329	45	801
32	1998	419	399	194
33	1833	1287	719	584
34	1550	1894	584	764
···	···	···	···	···
n	2029	2029	6550	6550

DownLoad: CSV

[1]	Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U 2006 Phys. Rep. 424 175 Google Scholar
[2]	Lü L, Chen D, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1 Google Scholar
[3]	Yang M, Seklouli A S, Zhang H, Ren L, Yu X, Ouzrout Y 2023 Proceedings of the 2023 International Conference on Computer Applications Technology Guiyang, China, September 15-17, 2023 p97
[4]	Albert R, Albert I, Nakarado G L 2004 Phys. Rev. E 69 025103 Google Scholar
[5]	Easley D, Kleinberg J 2010 IEEE Technol. Soc. Mag. 32 3
[6]	Freeman L C 1978 Soc. Networks 1 215 Google Scholar
[7]	Bonacich P 1972 J. Math. Sociol. 2 113 Google Scholar
[8]	Freeman L C 1977 Sociometry 40 35 Google Scholar
[9]	刘臣, 李丹丹, 韩林, 安永雪 2019 计算机应用研究 1 4 Liu C, Li D D, Han L, An Y X 2019 Appl. Res. Comput. 1 4
[10]	J Hu, B Wang, D Lee 2010 IEEE/ACM Int'l Conference on Green Computing and Communications & Int'l Conference on Cyber, Physical and Social Computing Hangzhou, China, December 18-20, 2010 p792
[11]	张格豪, 刘伟, 王睿鑫垚, 厉鑫鹏, 龚子忱, 陈一源, 陈海洋 2023 无线互联科技 6 116 Google Scholar Zhang G H, Liu W, Wang R X Y, Li X P, Gong Z C, Chen Y Y, Chen H Y 2023 Wireless Int. Technol. 6 116 Google Scholar
[12]	Lambiotte R, Rosvall M 2019 Nat. Phys. 15 313 Google Scholar
[13]	Perera S, Bell M G, Bliemer M C 2017 Appl. Netw. Sci. 2 33 Google Scholar
[14]	Battiston F, Cencetti G, Iacopini I, Latora V, Lucas M, Patania A, Young J G, Petri G 2020 Phys. Rep. 874 1 Google Scholar
[15]	Song J, Wang Y, Xu G 2024 Comput. Netw. 220 108969
[16]	Shi D H, Lu L Y, Chen G R 2019 Natl. Sci. Rev. 6 962 Google Scholar
[17]	Shi D H, Chen R, Thong W W K, Yan X Y 2013 IEEE Circuits Syst. Mag. 13 66 Google Scholar
[18]	Lou Y, Wang L, Chen G 2018 IEEE Trans. Circuits Syst. I Regul. Pap. 65 983
[19]	Sizemore A E, Giusti C, Kahn A, Vettel J M, Betzel R F, Bassett D S 2017 J. Comput. Neurosci. 44 115
[20]	Watts D J, Strogatz S H 1998 Nature 393 440 Google Scholar
[21]	Fronczak A, Hołst J A, Jedynak M, Sienkiewicz J 2002 Physica A 316 688 Google Scholar
[22]	Caldarelli G, Pastor-Satorras R, Vespignani A 2004 Eur. Phys. J. B 38 183 Google Scholar
[23]	Kim H J, Kim J M 2005 Phys. Rev. E 72 036109 Google Scholar
[24]	Fan T L, Lü L Y, Shi D H, Zhou T 2021 Commun. Phys. 4 272 Google Scholar
[25]	Croft D P, James R, Krause J 2008 Exploring Animal Social Networks (Princeton: Princeton University Press)pp1-18
[26]	Cha M, Haddadi H, Benevenuto F, Gummadi K P 2010 Proceedings of the Fourth International AAAI Conference on Weblogs and Social Media Washington, DC, USA, May 23-26, 2010 p10
[27]	Guimerà R, Mossa S, Turtschi A, Amaral L A N 2005 Proc. Natl. Acad. Sci. U. S. A. 102 7794 Google Scholar
[28]	Kossinets G, Watts D J 2006 Science 311 88 Google Scholar
[29]	Yang H, Bell M G H 1998 Transp. Rev. 18 257 Google Scholar
[30]	Lü J, Zhang B, Zhou T 2015 Physica A 418 65 Google Scholar
[31]	Helander M, Kertész J 2021 EPJ Data Sci. 11 1 Google Scholar
[32]	Noschese S, Reichel L 2024 Numer. Algor. 95 451 Google Scholar
[33]	Zhang J, Liu X 2022 J. Comput. Sci. 60 101591 Google Scholar
[34]	Kendall M 1938 Biometrika 30 81 Google Scholar
[35]	Callaway D S, Newman M E J, Strogatz S H, Watts D J 2000 Phys. Rev. Lett. 85 5468 Google Scholar
[36]	Cohen R, Erez K, Ben-Avraham D, Havlin S 2001 Phys. Rev. Lett. 86 3682 Google Scholar
[37]	田柳, 狄增如, 姚虹 2011 物理学报 60 028901 Google Scholar Tian L, Di Z R, Yao H 2011 Acta Phys. Sin. 60 028901 Google Scholar
[38]	Pastor-Satorras R, Castellano C, Van Mieghem P, Vespignani A 2015 Rev. Mod. Phys. 87 925 Google Scholar
[39]	Gubar E, Zhu Q, Taynitskiy V 2017 Proceedings of the 7th EAI International Conference on Game Theory for Networks Knoxville, Tennessee, USA, May 9, 2017 p108
[40]	Zhou F, Lü L Y, Mariani M S 2019 Commun. Nonlinear Sci. Numer. Simul. 74 69 Google Scholar

[1]	XING Zihan, LIU Siyu, LIU Hui, CHEN Lingxiao. An Algorithm for Mining Key Node Groups in Large-Scale Complex Networks Based on Spectral Graph Theory. Acta Physica Sinica, doi: 10.7498/aps.74.20250416
[2]	HOU Shiyu, LIU Ying, TANG Ming. Identification of key spreaders in complex network by integrating dynamic characteristics and local structure of nodes. Acta Physica Sinica, doi: 10.7498/aps.74.20250179
[3]	Wang Ting-Ting, Liang Zong-Wen, Zhang Ruo-Xi. Importance evaluation method of complex network nodes based on information entropy and iteration factor. Acta Physica Sinica, doi: 10.7498/aps.72.20221878
[4]	Ruan Yi-Run, Lao Song-Yang, Tang Jun, Bai Liang, Guo Yan-Ming. Node importance ranking method in complex network based on gravity method. Acta Physica Sinica, doi: 10.7498/aps.71.20220565
[5]	Kong Jiang-Tao, Huang Jian, Gong Jian-Xing, Li Er-Yu. Evaluation methods of node importance in undirected weighted networks based on complex network dynamics models. Acta Physica Sinica, doi: 10.7498/aps.67.20172295
[6]	Su Zhen, Gao Chao, Li Xiang-Hua. Analysis of the effect of node centrality on diffusion mode in complex networks. Acta Physica Sinica, doi: 10.7498/aps.66.120201
[7]	Ruan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Chen Li-Dong. Node importance measurement based on neighborhood similarity in complex network. Acta Physica Sinica, doi: 10.7498/aps.66.038902
[8]	Han Zhong-Ming, Chen Yan, Li Meng-Qi, Liu Wen, Yang Wei-Jie. An efficient node influence metric based on triangle in complex networks. Acta Physica Sinica, doi: 10.7498/aps.65.168901
[9]	Han Zhong-Ming, Wu Yang, Tan Xu-Sheng, Duan Da-Gao, Yang Wei-Jie. Ranking key nodes in complex networks by considering structural holes. Acta Physica Sinica, doi: 10.7498/aps.64.058902
[10]	Liu Jian-Guo, Ren Zhuo-Ming, Guo Qiang, Wang Bing-Hong. Node importance ranking of complex networks. Acta Physica Sinica, doi: 10.7498/aps.62.178901
[11]	Ren Zhuo-Ming, Liu Jian-Guo, Shao Feng, Hu Zhao-Long, Guo Qiang. Analysis of the spreading influence of the nodes with minimum K-shell value in complex networks. Acta Physica Sinica, doi: 10.7498/aps.62.108902
[12]	Yu Hui, Liu Zun, Li Yong-Jun. Key nodes in complex networks identified by multi-attribute decision-making method. Acta Physica Sinica, doi: 10.7498/aps.62.020204
[13]	Liu Jin-Liang. Research on synchronization of complex networks with random nodes. Acta Physica Sinica, doi: 10.7498/aps.62.040503
[14]	Lü Tian-Yang, Xie Wen-Yan, Zheng Wei-Min, Piao Xiu-Feng. Analysis of community evaluation criterion and discovery algorithm of weighted complex network. Acta Physica Sinica, doi: 10.7498/aps.61.210511
[15]	Zhou Xuan, Zhang Feng-Ming, Zhou Wei-Ping, Zou Wei, Yang Fan. Evaluating complex network functional robustness by node efficiency. Acta Physica Sinica, doi: 10.7498/aps.61.190201
[16]	LÜ Ling, Liu Shuang, Zhang Xin, Zhu Jia-Bo, Shen Na, Shang Jin-Yu. Spatiotemporal chaos anti-synchronization of a complex network with different nodes. Acta Physica Sinica, doi: 10.7498/aps.61.090504
[17]	Zhou Xuan, Zhang Feng-Ming, Li Ke-Wu, Hui Xiao-Bin, Wu Hu-Sheng. Finding vital node by node importance evaluation matrix in complex networks. Acta Physica Sinica, doi: 10.7498/aps.61.050201
[18]	Chen Hua-Liang, Liu Zhong-Xin, Chen Zeng-Qiang, Yuan Zhu-Zhi. Research on one weighted routing strategy for complex networks. Acta Physica Sinica, doi: 10.7498/aps.58.6068
[19]	Lü Ling, Zhang Chao. Chaos synchronization of a complex network with different nodes. Acta Physica Sinica, doi: 10.7498/aps.58.1462
[20]	Li Ji, Wang Bing-Hong, Jiang Pin-Qun, Zhou Tao, Wang Wen-Xu. Growing complex network model with acceleratingly increasing number of nodes. Acta Physica Sinica, doi: 10.7498/aps.55.4051

Metrics

Abstract views: 356
PDF Downloads: 6
Cited By: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

Search

Article

留言板