Identification Method for Key Nodes in En-Route Network
-
摘要:
有效辨识关键节点对增强网络韧性、提高运行能力具有重要现实意义,为提高航路网络关键节点识别的准确性,提出基于TOPSIS-灰色关联分析法的综合评价方法和航路网络节点分级方法. 首先,从复杂网络统计特性、交通流量特性、脆弱性三个方面构建航路网络关键节点评价指标体系;通过引入相对熵改进逼近理想值排序(technique for order preference by similarity to an ideal solution,TOPSIS)法,同时结合灰色关联分析法综合评价航路点重要程度,采用基于K-means聚类方法有效划分航路节点等级;最后,以民航空管实际运行数据为实例,开展关键节点识别. 研究表明:相较于单一指标,所建航路网络节点评价指标体系获得的评价结果更加全面;同时改进TOPSIS-灰色关联分析方法相较于传统TOPSIS法评价结果更加准确;本研究所提识别方法发现了我国华东地区典型繁忙航路网络中有29个关键节点,其在网络结构及交通流量方面起着较为关键的作用.
Abstract:Accurate identification of key nodes is of great practical significance for enhancing network resilience and improving operational capabilities. In order to improve the identification accuracy of key nodes in the en-route network, a comprehensive evaluation method based on the technique for order preference by similarity to an ideal solution (TOPSIS)-grey correlation analysis method and a node classification method for the en-route network were proposed. Firstly, an evaluation index system of key nodes in the en-route network was constructed from three perspectives: complex network characteristics, traffic volume, and vulnerability. Then, the relative entropy was introduced to improve the TOPSIS method, and the importance of en-route waypoints was comprehensively evaluated by combining this method with the grey correlation analysis method. The K-means clustering method was used to effectively divide the levels of en-route waypoints. Finally, key node identification was carried out based on the actual operation data of civil air traffic management. It finds that the results obtained by the constructed evaluation index system of key nodes in the en-route network are more comprehensive than the evaluation results of a single index. At the same time, the improved TOPSIS-grey correlation analysis is more accurate than the traditional TOPSIS method. The proposed identification method finds that there are 29 key nodes in the typical busy en-route network in Eastern China, which play a key role in the network structure and traffic volume.
-
Key words:
- complex networks /
- TOPSIS /
- relative entropy /
- grey relational degree /
- K-means clustering
-
表 1 华东地区航路点评价指标规范化数值
Table 1. Normalized values of evaluation indexes for en-route waypoints in Eastern China
航路点序号 z11 z12 z13 z14 z21 z22 z23 z31 z32 z33 1 0.222 0.095 0.610 0.095 0.533 0.354 0.447 0.000 0.097 0.897 2 0.111 0.018 0.794 0.077 0.000 0.000 0.000 0.000 0.068 0.831 3 0.444 0.130 0.871 0.130 0.733 0.459 0.505 0.000 0.134 0.789 4 0.111 0.391 0.691 0.012 0.667 0.078 0.107 0.000 0.130 0.838 5 0.111 0.114 0.765 0.032 0.333 0.131 0.184 0.000 0.089 0.835 6 0.111 0.055 0.251 0.005 0.533 0.158 0.175 0.500 0.242 0.869 7 0.111 0.027 0.847 0.086 0.733 0.231 0.243 0.000 0.085 0.850 8 0.556 0.604 0.924 0.153 0.600 0.208 0.252 0.000 0.407 0.892 9 0.111 0.103 0.613 0.007 0.200 0.024 0.058 0.000 0.129 0.811 10 0.111 0.031 0.285 0.000 0.267 0.010 0.029 0.000 0.061 0.840 表 2 航路网络排名前二十的评价结果
Table 2. Evaluation results of top 20 points in en-route network
排名 $ {G_i} $ TOPSIS $ G_i^{'} $ 值 航路点 值 航路点 值 航路点 1 0.703 TOL 0.867 TOL 0.697 TOL 2 0.685 HFE 0.759 HFE 0.603 HFE 3 0.639 JTN 0.724 JTN 0.593 JTN 4 0.620 ELNEX 0.729 ELNEX 0.495 ELNEX 5 0.603 P215 0.726 P215 0.500 P215 6 0.602 SHR 0.692 SHR 0.449 SHR 7 0.601 DST 0.699 DST 0.687 DST 8 0.588 DO 0.533 DO 0.641 DO 9 0.563 BK 0.608 BK 0.519 BK 10 0.561 AND 0.605 AND 0.412 NOBEM 11 0.559 SHZ 0.552 SHZ 0.617 SHZ 12 0.551 KAKIS 0.612 KAKIS 0.488 BZ 13 0.533 NINAS 0.541 NINAS 0.472 LYG 14 0.531 LASAN 0.533 LASAN 0.536 SUPAR 15 0.511 UGAGO 0.526 UGAGO 0.424 UGAGO 16 0.493 SASAN 0.509 SASAN 0.431 YCH 17 0.503 PINOT 0.497 PINOT 0.429 RUPUD 18 0.504 P263 0.509 XUVGI 0.433 PK 19 0.502 JDZ 0.498 MADUK 0.424 OSIKI 20 0.508 BZ 0.499 OF 0.612 OF -
[1] NEWMAN M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256. doi: 10.1137/S003614450342480 [2] 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 [3] CHEN D B, LÜ L Y, SHANG M S, et al. Identifying influential nodes in complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2012, 391(4): 1777-1787. doi: 10.1016/j.physa.2011.09.017 [4] 闫玲玲,陈增强,张青. 基于度和聚类系数的中国航空网络重要性节点分析[J]. 智能系统学报,2016,11(5): 586-593.YAN Lingling, CHEN Zengqiang, ZHANG Qing. Analysis of key nodes in China s aviation network based on the degree centrality indicator and clustering coefficient[J]. CAAI Transactions on Intelligent Systems, 2016, 11(5): 586-593. [5] WANG H Y, SONG Z Q, WEN R Y, et al. Study on evolution characteristics of air traffic situation complexity based on complex network theory[J]. Aerospace Science and Technology, 2016, 58: 518-528. doi: 10.1016/j.ast.2016.09.016 [6] BELKOURA S, COOK A, PEÑA J M, et al. On the multi-dimensionality and sampling of air transport networks[J]. Transportation Research Part E: Logistics and Transportation Review, 2016, 94: 95-109. doi: 10.1016/j.tre.2016.07.013 [7] WANG H Y, XU X H, ZHAO Y F. Empirical analysis of aircraft clusters in air traffic situation networks[J]. Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, 2017, 231(9): 1718-1731. doi: 10.1177/0954410016660870 [8] 任新惠,杨丽. 中国航空货运网络脆弱性分析[J]. 安全与环境学报,2020,20(3): 840-848.REN Xinhui, YANG Li. Vulnerability analysis of China air cargo transportation network[J]. Journal of Safety and Environment, 2020, 20(3): 840-848. [9] 徐开俊,肖成坤,杨泳,等. 基于复杂网络理论的中国城市航空网络有向加权分析[J]. 科学技术与工程,2021,21(36): 15669-15673.XU Kaijun, XIAO Chengkun, YANG Yong, et al. Directed Weighted Analysis of Chinese Urban Aviation Network Based on Complex Network Theory. Science Technology and Engineering[J], 2021, 21(36): 15669-15673. [10] BAE J, KIM S. Identifying and ranking influential spreaders in complex networks by neighborhood coreness[J]. Physica A Statistical Mechanics and Its Applications, 2014, 395: 549-559. doi: 10.1016/j.physa.2013.10.047 [11] LIU Y, TANG M, ZHOU T, et al. Identify influential spreaders in complex networks, the role of neighborhood[J]. Physica A: Statistical Mechanics and Its Applications, 2016, 452: 289-298. doi: 10.1016/j.physa.2016.02.028 [12] ZAOLI S, MAZZARISI P, LILLO F. Trip Centrality: walking on a temporal multiplex with non-instantaneous link travel time[J]. Scientific Reports, 2019, 9: 10570.1-10570.11. [13] ULLAH A, WANG B, SHENG J F, et al. Identification of nodes influence based on global structure model in complex networks[J]. Scientific Reports, 2021, 11: 6173.1-6173.11. [14] ULLAH A, WANG B, SHENG J F, et al. Identifying vital nodes from local and global perspectives in complex networks[J]. Expert Systems with Applications, 2021, 186: 115778.1-115778.10. [15] GUIMERÀ R, MOSSA S, TURTSCHI A, et al. The worldwide air transportation network: anomalous centrality, community structure, and cities' global roles[J]. Proceedings of the National Academy of Sciences of the United States of America, 2005, 102(22): 7794-7799. [16] 段东立,战仁军. 基于相继故障信息的网络节点重要度演化机理分析[J]. 物理学报,2014,63(6): 385-393.DUAN Dongli, ZHAN Renjun. Evolution mechanism of no de imp ortance based on the information ab out cascading failures in complex networks[J]. Acta Physica Sinica, 2014, 63(6): 385-393. [17] MORONE F, MAKSE H A. Influence maximization in complex networks through optimal percolation[J]. Nature, 2015, 524: 65-68. doi: 10.1038/nature14604 [18] 程光权,陆永中,张明星,等. 复杂网络节点重要度评估及网络脆弱性分析[J]. 国防科技大学学报,2017,39(1): 120-127.CHENG Guangquan, LU Yongzhong, ZHANG Mingxing, et al. Node importance evaluation and network vulnerability analysis on complex network[J]. Journal of National University of Defense Technology, 2017, 39(1): 120-127. [19] DU W B, ZHANG M Y, ZHANG Y, et al. Delay causality network in air transport systems[J]. Transportation Research Part E: Logistics and Transportation Review, 2018, 118: 466-476. doi: 10.1016/j.tre.2018.08.014 [20] WANG Z K, WEN X X, WU M G. Identification of key nodes in aircraft state network based on complex network theory[J]. IEEE Access, 2019, 7: 60957-60967. doi: 10.1109/ACCESS.2019.2915508 [21] 冯霞,贾宏璨. 考虑节点失效和边失效的航空网络鲁棒性[J]. 北京交通大学学报,2021,45(5): 84-92.FENG Xia, JIA Hongcan. Aviation network robustness considering node failure and edge failure[J]. Journal of Beijing Jiaotong University, 2021, 45(5): 84-92. [22] LORDAN O, SALLAN J M, SIMO P, et al. Robustness of the air transport network[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 68: 155-163. doi: 10.1016/j.tre.2014.05.011 [23] CHEN Y, WANG J E, JIN F J. Robustness of China’s air transport network from 1975 to 2017[J]. Physica A: Statistical Mechanics and Its Applications, 2020, 539: 122876.1-122876.12. [24] LI W, CAI X. Statistical analysis of airport network of China[J]. Phys Rev E Stat Nonlin Soft Matter Phys, 2004, 69(4):046106.1-046106.11. [25] ZHOU Y M, WANG J W, HUANG G Q. Efficiency and robustness of weighted air transport networks[J]. Transportation Research Part E: Logistics and Transportation Review, 2019, 122: 14-26. doi: 10.1016/j.tre.2018.11.008 [26] QI X Q, FULLER E, WU Q, et al. Laplacian centrality: a new centrality measure for weighted networks[J]. Information Sciences, 2012, 194: 240-253. doi: 10.1016/j.ins.2011.12.027 [27] WANG N, GAO Y, HE J T, et al. Robustness evaluation of the air cargo network considering node importance and attack cost[J]. Reliability Engineering & System Safety, 2022, 217: 108026.1-108026.15. [28] 陈静,孙林夫. 复杂网络中节点重要度评估[J]. 西南交通大学学报,2009,44(3): 426-429. doi: 10.3969/j.issn.0258-2724.2009.03.021CHEN Jing, SUN Linfu. Evaluation of node importance in complex networks[J]. Journal of Southwest Jiaotong University, 2009, 44(3): 426-429. doi: 10.3969/j.issn.0258-2724.2009.03.021 [29] 张喜平,李永树,刘刚,等. 节点重要度贡献的复杂网络节点重要度评估方法[J]. 复杂系统与复杂性科学,2014,11(3): 26-32,49.ZHANG Xiping, LI Yongshu, LIU Gang, et al. Evaluation method of importance for nodes in complex networks based on importance contribution[J]. Complex Systems and Complexity Science, 2014, 11(3): 26-32,49.