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

冯霞; 王尧

doi:10.13700/j.bh.1001-5965.2020.0335

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

doi: 10.13700/j.bh.1001-5965.2020.0335

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

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

基金项目:

国家自然科学基金 61502499

中央高校基本科研业务费专项资金 3122018C024

天津市自然科学基金 18JCYBJC85100

详细信息

通讯作者:
冯霞, E-mail: caucfx@126.com

中图分类号: V11;TP399
计量
- 文章访问数: 482
- HTML全文浏览量: 110
- PDF下载量: 96
- 被引次数: 0
出版历程
- 收稿日期: 2020-07-13
- 录用日期: 2020-09-27
- 网络出版日期: 2021-09-20

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

Funds:

National Natural Science Foundation of China 61502499

the Fundamental Research Funds for the Central Universities 3122018C024

Tianjin Municipal Natural Science Foundation 18JCYBJC85100

More Information

Corresponding author: FENG Xia, E-mail: caucfx@126.com

摘要

摘要:
针对新增航线发现研究中存在的航线选择主观化、网络信息挖掘不充分等问题，考虑航空运输网络的拓扑结构特征和节点(通航城市)层次属性，提出了一种基于链路预测的未来新增航线发现(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.
- air transport network /
- link prediction /
- New Air Routes Prediction (NARP) /
- nodes hierarchical attributes /
- Deep Graph Convolutional Neural Network (DGCNN)

HTML全文

图 1 NARP模型的主要框架

Figure 1. Major framework of NARP model

下载: 全尺寸图片幻灯片

图 2 节点对(x, y)的1跳局部封闭子图

Figure 2. The 1-hop local enclosing subgraph for node pairs (x, y)

下载: 全尺寸图片幻灯片

图 3 节点标记示意图

Figure 3. Schematic diagram of node labeling

下载: 全尺寸图片幻灯片

图 4 节点属性示意图

Figure 4. Schematic diagram of node attributes

下载: 全尺寸图片幻灯片

图 5 子图节点信息矩阵示意图

Figure 5. Schematic diagram of subgraph node information matrix

下载: 全尺寸图片幻灯片

图 6 DGCNN结构示意图

Figure 6. Schematic diagram of DGCNN structure

下载: 全尺寸图片幻灯片

图 7 不同基准方法的类型划分

Figure 7. Type division of each benchmark method

下载: 全尺寸图片幻灯片

图 8 不同数据集划分下各模型的AUC值

Figure 8. AUC values of each model under different dataset partition

下载: 全尺寸图片幻灯片

图 9 不同数据集划分下各模型的AUC值变化情况对比

Figure 9. Comparison of AUC changes of each model under different dataset partition

下载: 全尺寸图片幻灯片

表 1 DGCNN的主要参数设置

Table 1. Main parameter setting in DGCNN

参数	数值
迭代数num_epochs	30
批大小batch_size	30
学习率learning_rate	0.000 4
子图数占比p	0.6
优化器optimizer	RMS prop
丢弃函数droupout	Yes

下载: 导出CSV

表 2 数据集7∶3划分下各模型的AUC值

Table 2. AUC value of each model under dataset 7∶3 partition

模型	AUC/%
AA	82.37±0.62
Katz	85.78±0.93
SVD	89.88±0.70
HOPE	90.59±0.79
DeepWalk	89.04±2.03
node2vec	89.83±1.28
LINE	88.42±3.14
GAE	86.84±1.12
NARP-s	91.65±0.95
NARP	92.47±0.67

下载: 导出CSV

表 3 NARP预测的TOP-15新增航线

Table 3. Top-15 new air routes predicted by NARP

序号	新增航线
1	TAO-SYX
2	WUH-SJW
3	TAO-URC
4	HET-WNZ
5	KWL-CGQ
6	HAK-LJG
7	TAO-ZUH
8	HGH-DSN
9	CTU-YNZ
10	HAK-YNZ
11	TNA-HFE
12	SHA-LXA
13	HAK-CZX
14	CKG-ACX
15	INC-NGB

下载: 导出CSV

参考文献(24)

[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. doi: 10.1016/j.procs.2016.05.131
[2]	葛伟, 朱金福, 吴薇薇. 蛛网式航线网络模型设计[J]. 交通运输系统工程与信息, 2012, 12(4): 172-177. doi: 10.3969/j.issn.1009-6744.2012.04.025 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). doi: 10.3969/j.issn.1009-6744.2012.04.025
[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. http://www.researchgate.net/profile/Fernando_Berzal/publication/310912568_A_Survey_of_Link_Prediction_in_Complex_Networks/links/5a3caf220f7e9b10e23c7ee9/A-Survey-of-Link-Prediction-in-Complex-Networks.pdf
[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. doi: 10.1093/bioinformatics/bts688
[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. http://arxiv.org/abs/1906.05017
[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. doi: 10.4236/jdaip.2017.52004
[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. http://www.researchgate.net/publication/345497534_Discovering_spurious_links_in_multiplex_networks_based_on_interlayer_relevance
[9]	刘宏鲲, 吕琳媛, 周涛. 利用链路预测推断网络演化机制[J]. 中国科学: 物理学力学天文学, 2011, 41(7): 816-823. https://www.cnki.com.cn/Article/CJFDTOTAL-JGXK201107003.htm 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). https://www.cnki.com.cn/Article/CJFDTOTAL-JGXK201107003.htm
[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. doi: 10.1140/epjb/e2009-00335-8
[16]	GOYAL P, FERRARA E. Graph embedding techniques, applications, and performance: A survey[J]. Knowledge-Based Systems, 2018, 151: 78-94. doi: 10.1016/j.knosys.2018.03.022
[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. doi: 10.1016/S0378-8733(03)00009-1
[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. http://www.onacademic.com/detail/journal_1000040466888510_76c2.html
[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.