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

doi:10.13700/j.bh.1001-5965.2020.0335

北京航空航天大学学报 ›› 2021, Vol. 47 ›› Issue (9): 1729-1738.doi: 10.13700/j.bh.1001-5965.2020.0335

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

冯霞^1,2, 王尧^1,2

1. 中国民航信息技术科研基地, 天津 300300;
2. 中国民航大学计算机科学与技术学院, 天津 300300

收稿日期:2020-07-13 发布日期:2021-10-09
通讯作者: 冯霞 E-mail:caucfx@126.com
基金资助:
国家自然科学基金（61502499）；中央高校基本科研业务费专项资金（3122018C024）；天津市自然科学基金（18JCYBJC85100）

Future air routes discovery based on link prediction

FENG Xia^1,2, WANG Yao^1,2

1. Information Technology Research Base of Civil Aviation Administration of China, Tianjin 300300, China;
2. School of Computer Science and Technology, Civil Aviation University of China, Tianjin 300300, China

Received:2020-07-13 Published:2021-10-09
Supported by:
National Natural Science Foundation of China (61502499); the Fundamental Research Funds for the Central Universities (3122018C024); Tianjin Municipal Natural Science Foundation (18JCYBJC85100)

摘要/Abstract

摘要： 针对新增航线发现研究中存在的航线选择主观化、网络信息挖掘不充分等问题，考虑航空运输网络的拓扑结构特征和节点（通航城市）层次属性，提出了一种基于链路预测的未来新增航线发现（NARP）模型。NARP模型提取局部封闭子图构建子图邻接矩阵，基于距离标记子图节点结构重要性，采用因子分析和层次聚类提取节点层次属性。在此基础上，融合子图结构和节点属性2类特征，采用深度图卷积神经网络（DGCNN）进行链路预测，实现新增航线发现。在中国航空运输网络实际运行数据上的实验结果表明：较之基准方法，NARP模型的预测准确率最高提升9.28%；在网络极度不完整时，预测准确率可以保持在80%左右；预测结果符合航空运输网络的实际演变情况。

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

Abstract: 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.

Key words: air transport network, link prediction, New Air Routes Prediction (NARP), nodes hierarchical attributes, Deep Graph Convolutional Neural Network (DGCNN)

中图分类号:

V11
TP399

冯霞, 王尧. 基于链路预测的未来新增航线发现[J]. 北京航空航天大学学报, 2021, 47(9): 1729-1738.

FENG Xia, WANG Yao. Future air routes discovery based on link prediction[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(9): 1729-1738.

参考文献

[1] KASTURI E,DEVI S P,KIRAN S V,et al.Airline route profitability analysis and optimization using BIG DATA analytics on aviation data sets under heuristic techniques[J].Procedia Computer Science,2016,87:86-92.
[2] 葛伟,朱金福,吴薇薇.蛛网式航线网络模型设计[J].交通运输系统工程与信息,2012,12(4):172-177.GE W,ZHU J F,WU W W.Design of cobweb air route network model[J].Journal of Transportation Systems Engineering and Information Technology,2012,12(4):172-177(in Chinese).
[3] MARTINEZ V,BERZAL F,CUBERO J C.A survey of link prediction in complex networks[J].ACM Computing Surveys,2017,49(4):1-33.
[4] LIBEN-NOWELL D,KLEINBERG J.The link-prediction problem for social networks[J].Journal of the Association for Information Science and Technology,2007,58(7):1019-1031.
[5] LEI C,RUAN J.A novel link prediction algorithm for reconstructing protein-protein interaction networks by topological similarity[J].Bioinformatics,2013,29(3):355-364.
[6] YUE X,WANG Z,HUANG J,et al.Graph embedding on biomedical networks:Methods,applications and evaluations[J].Bioinformatics,2020,36(4):1241-1251.
[7] TAKAHASHI Y,OSAWA R,SHIRAYAMA S.A basic study of the forecast of air transportation networks using different forecasting methods[J].Journal of Data Analysis and Information Processing,2017,5(2):49-66.
[8] NAJARI S,SALEHI M,RANJBAR V,et al.Link prediction in multiplex networks based on interlayer similarity[J].Physica A-Statistical Mechanics and Its Applications,2019,536:120-978.
[9] 刘宏鲲,吕琳媛,周涛.利用链路预测推断网络演化机制[J].中国科学:物理学力学天文学,2011,41(7):816-823. LIU H K,LV L Y,ZHOU T.Uncovering the network evolution mechanism by link prediction[J].Scientia Sinica Physica,Mechanica & Astronomica,2011,41(7):816-823(in Chinese).
[10] ZHENG Y,LI W,CAO X,et al.Optimization of air transportation network using link prediction methods[C]//Proceedings of the 17th COTA International Conference of Transportation Professionals,2018:991-1000.
[11] ZHANG M,CHEN Y.Link prediction based on graph neural networks[C]//Advances in Neural Information Processing Systems.Cambridge:MIT Press,2018,31:5171-5181.
[12] ZHANG M,CUI Z,NEUMANN M,et al.An end-to-end deep learning architecture for graph classification[C]//Proceedings of 32nd AAAI Conference on Artificial Intelligence.Palo Alto:AAAI Press,2018:4438-4445.
[13] 中国民用航空局发展计划司.中国民航统计年鉴2016[M].北京:中国民航出版社,2016:52-140.PL CAAC.China civil aviation statistical yearbook 2016[M].Beijing:China Civil Aviation Publishing House,2016:52-140(in Chinese).
[14] 中国民用航空局发展计划司.从统计看民航2017[M].北京:中国民航出版社,2017:53-137.PL CAAC.Statistical data on civil aviation of China[M].Beijing:China Civil Aviation Publishing House,2017:53-137(in Chinese).
[15] ZHOU T,LV L Y,ZHANG Y C.Predicting missing links via local information[J].The European Physical Journal B, 2009,71(4):623-630.
[16] GOYAL P,FERRARA E.Graph embedding techniques,applications,and performance:A survey[J].Knowledge-Based Systems,2018,151:78-94.
[17] MUTLU E C,OGHAZ T A.Review on graph feature learning and feature extraction techniques for link prediction[EB/OL].(2019-01-10)[2020-06-27].https://arxiv.org/abs/1901.03425.
[18] ADAMIC L A,ADAR E.Friends and neighbors on the Web[J].Social Networks,2003,25(3):211-230.
[19] DAI W,LIU X,CAO Y B,et al.Matrix factorization-based prediction of novel drug indications by integrating genomic space[J].Computational and Mathematical Methods in Medicine,2015,2015:1-9.
[20] OU M D,CUI P,PEI J,et al.Asymmetric transitivity preserving graph embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM Press,2016:1105-1114.
[21] PEROZZI B,AI-RFOU R,SKIENA S.DeepWalk:Online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM Press,2014:701-710.
[22] GROVER A, LESKOVEC J.node2vec:Scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM Press,2016:855-864.
[23] TANG J,QU M,WANG M,et al.LINE:Large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web,2015:1067-1077.
[24] KIPF T N,MAX W.Variational graph auto-encoders[EB/OL].(2016-11-21)[2020-07-01].https://arxiv.org/abs/1611.07308.

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

Future air routes discovery based on link prediction

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	李雯, 徐可宁, 黄勇, 胡文颖, 王道宽, 姚思齐. 基于SLM的模拟月壤原位成形技术[J]. 北京航空航天大学学报, 2019, 45(10): 1931-1937.
[2]	呼延嘉玥, 徐立军, 李小路. 自研激光雷达三维点云配准技术[J]. 北京航空航天大学学报, 2019, 45(10): 2099-2107.
[3]	傅超琦, 王瑛, 李超, 孙贇. 不同增长机制下航空网络自愈特性[J]. 北京航空航天大学学报, 2018, 44(6): 1221-1229.
[4]	唐伟财, 陈善广, 肖毅, 姜国华, 田志强. 空间立体信息缺失对机械臂遥操作任务的影响[J]. 北京航空航天大学学报, 2017, 43(2): 335-343.
[5]	汪启跃, 王中宇, 王岩庆, 姚贞建. 乏信息空间机械臂随机振动信号的灰自助评估[J]. 北京航空航天大学学报, 2016, 42(4): 858-864.
[6]	李锋, 吕付国, 罗卫国, 赵凯, 王昌胜, 熊溢威. 超声速气流中液体横向射流的破碎特性[J]. 北京航空航天大学学报, 2015, 41(12): 2356-2362.
[7]	全齐全, 史晓萌, 唐德威, 姜生元, 邓宗全. 模拟月壤钻进取样量影响因素分析及试验研究[J]. 北京航空航天大学学报, 2015, 41(11): 2052-2060.
[8]	罗卫东, 李锋, 孙佰刚, 赵凯, 熊溢威, 王昌胜. MHD控制微电离等离子体射流[J]. 北京航空航天大学学报, 2015, 41(9): 1758-1764.
[9]	汪启跃王中宇王岩庆姚贞建. 乏信息空间机械臂随机振动信号的灰自助评估[J]. 北京航空航天大学学报, 0, (): 0-0.
[10]	郜林. 基于信道估计自适应算法的AVLC重发机制仿真[J]. 北京航空航天大学学报, 2015, 41(2): 289-295.
[11]	孟偲, 周娜, 张亚妮. 基于下降图像三维地形重建的参数自适应生成[J]. 北京航空航天大学学报, 2014, 40(7): 887-892.
[12]	王家俊, 王春洁, 宋顺广. 基于响应面法的月球着陆器软着陆性能优化[J]. 北京航空航天大学学报, 2014, 40(5): 707-711.
[13]	苏庆华, 赵剡, 杨奎, 张少辰. 月球着陆器悬停阶段相对自主导航方法[J]. 北京航空航天大学学报, 2014, 40(3): 377-382.
[14]	吴建云, 王春洁, 汪翰. 月球着陆器模型参数修正[J]. 北京航空航天大学学报, 2013, 39(10): 1366-1369,1375.
[15]	苏庆华, 赵剡. 月球着陆器着陆安全分析方法[J]. 北京航空航天大学学报, 2012, (11): 1522-1526.