基于链路预测的未来新增航线发现  

Future air routes discovery based on link prediction

作　　者：冯霞 王尧[1,2] FENG Xia;WANG Yao(Information Technology Research Base of Civil Aviation Administration of China,Tianjin 300300,China;School of Computer Science and Technology,Civil Aviation University of China,Tianjin 300300,China)

机构地区：[1]中国民航信息技术科研基地,天津300300 [2]中国民航大学计算机科学与技术学院,天津300300

出　　处：《北京航空航天大学学报》2021年第9期1729-1738,共10页Journal of Beijing University of Aeronautics and Astronautics

基　　金：国家自然科学基金(61502499);中央高校基本科研业务费专项资金(3122018C024);天津市自然科学基金(18JCYBJC85100)。

摘　　要：针对新增航线发现研究中存在的航线选择主观化、网络信息挖掘不充分等问题,考虑航空运输网络的拓扑结构特征和节点(通航城市)层次属性,提出了一种基于链路预测的未来新增航线发现(NARP)模型。NARP模型提取局部封闭子图构建子图邻接矩阵,基于距离标记子图节点结构重要性,采用因子分析和层次聚类提取节点层次属性。在此基础上,融合子图结构和节点属性2类特征,采用深度图卷积神经网络(DGCNN)进行链路预测,实现新增航线发现。在中国航空运输网络实际运行数据上的实验结果表明:较之基准方法,NARP模型的预测准确率最高提升9.28%;在网络极度不完整时,预测准确率可以保持在80%左右;预测结果符合航空运输网络的实际演变情况。In view of the problems of subjective route selection and insufficient network information mining in the research of new air routes discovery,and considering the topological structure characteristics and nodes(navigable cities)hierarchical attributes of air transport network,a New Air Routes Prediction(NARP)model based on link prediction is proposed.The NARP model extracted local enclosing subgraphs to construct subgraph adjacency matrices,marked the structural importance of nodes based on distance,and obtained nodes hierarchical attributes through factor analysis and hierarchical clustering.Then the two types of features of subgraph structure and nodes attributes were fused,and the Deep Graph Convolutional Neural Network(DGCNN)was used to perform link prediction to discover the future new air routes.The experimental results on the actual operation data of Chinese air transport network show that,compared with the benchmark algorithm,the prediction accuracy rate of NARP model is improved by 9.28%at most.When the network is extremely incomplete,the prediction accuracy rate can remain around 80%.The predicted results are in line with the actual evolution of air transport network.

关 键 词：航空运输网络 链路预测 未来新增航线发现(NARP) 节点层次属性 深度图卷积神经网络(DGCNN) 

分 类 号：V11[航空宇航科学与技术—人机与环境工程] TP399[自动化与计算机技术—计算机应用技术]