基于支持向量机的“一带一路”航空网络的链路预测

侯泽林 姚红光 戚莹

摘  要：链路预测可以探寻“一带一路”航空网络中的链接偏好，为“一带一路”航空网络提供一定的理论依据。文章选取8个网络结构相似性指标，基于支持向量机分类算法从国家和机场两个层面对“一带一路”沿线航空网络进行链路预测。结果发现：越宏观的航空网络，其预测精确度越高；同时，链路预测模型的预测精确度与指标中包含的网络结构信息相关，指标中包含的网络结构信息越多，预测精确度越高，且对于“一带一路”航空网络中的节点，链路预测中Katz指标的预测准确度最高。

关键词：一带一路；航空网络；链路预测；支持向量机

中图分类号：F560    文献标志碼：A    DOI：10.13714/j.cnki.1002-3100.2023.09.021

Abstract： Link prediction can explore the link preference in "the belt and road" aviation network， and provide a theoretical basis for "the belt and road" aviation network. In this paper， eight network structure similarity indexes are selected to predict the link of aviation network along "the belt and road" from the national and airport levels based on support vector machine classification algorithm. The results show that the larger the aviation network， the higher the prediction accuracy; at the same time， the prediction accuracy of the link prediction model is related to the network structure information contained in the index. The more the network structure information contained in the index， the higher the prediction accuracy. For the nodes in "the belt and road" aviation network， the Katz index has the highest prediction accuracy.

Key words： the belt and road; aviation network; link prediction; support vector machine

0  引  言

21世纪以来，经济全球化和区域经济一体化进程加速，国际航空运输的地位日益重要，逐渐成为国际运输的重要载体。2013年，由习近平主席提出“一带一路”倡议开启了我国全方位对外开放新格局，而民航运输的产业属性和独特优势决定了民航运输业对“一带一路”国家战略实施具有重要作用。自“一带一路”倡议提出以来，学者多有围绕此战略开展研究。“一带一路”倡议将设施联通作为对外合作战略的重点之一[1]。目前国内外学者对于航空网络的研究重点关注在航空网络的拓扑结构特性上[2-4]。Zhou Y[5]分析“一带一路”国家层面航空网络的网络结构，应用重力模型量化枢纽中心性，评估了多式联运枢纽现状，并推荐新的枢纽，以增加“一带一路”的辐射范围。王姣娥等[6]分析了中国与“一带一路”沿线国家的国际航空运输空间格局和国际航空枢纽。卓志强等[7]研究发现“一带一路”沿线航空网络为小世界无标度网络，对随机攻击具有强鲁棒性，面对蓄意攻击时鲁棒性很差。Wang K等[8]分析中亚五国航空市场，发现“一带一路”倡议提出的更自由的航空政策可能有助于克服现有的高服务壁垒。杜方叶[9]从国际航线、国际航班以及通航城市三个方面分析“一带一路”倡议提出以来中国国际航空网络的空间格局及其演变特征。以及其他学者研究交通复杂性[10]，航空网络在时间空间上的演化特性[11]。

在探究航空网络拓扑结构的同时，学者们也在探究复杂网络中的内在联系以及学者们期望通过研究网络连接机制以预测网络未来发展趋势。Liben-Nowell等[12]定义了网络拓扑结构的相似性方法，将相似性指标分为节点和路径，并且分析了多种指标在社会合作网络中的预测效果。近年来，逐渐有学者开始研究将链路预测技术应用于航空运输网络未来可能新增的航线[13]。Takahashi等[14]采用基于相似性的链路预测方法，考虑网络结构特征，识别航空运输网络中未来可能的新增航线。Najari等[15]改进基于相似性的链路预测方法，将航空运输网络按航空公司分层，考虑层内及层间的结构相似性，进行新增航线预测。刘宏鲲等[16]采用链路预测技术分析航空运输网络的演变及其影响因素，指出通航城市属性在预测中的重要性。Zheng等[17]考虑网络结构和航班频率，构建加权局部贝叶斯模型预测未来新增航线。

随着机器学习和数据挖掘方向的发展，机器学习逐渐和链路预测方法相结合[18]。翟东升[19]根据专利之间的引用关系，运用IPC建立技术类别之间的关系网络，计算网络中的IPC对之间的特征指标，使用SVM进行训练，获得未来链路预测模型。

Pc A[20]把机器学习技术支持向量机应用在股市中进行预测。Wang Q等[21]用最小二乘支持向量机（LSSVM）对电池容量进行估计，计算时间短，误差小。Hasan[22]研究结果显示，在BIOBASE和DBLP数据库中，SVM的预测精度要优于其他机器学习算法。

总体来讲，采用链路预测技术对航空网络的相关研究仍处于探索阶段，且目前主要采用基于相似性的预测方法，存在网络信息挖掘不充分、相似性指标选取主观化等问题。采用机器学习方法进行链路预测，能够避免上述问题，并且处理高维数据时能够避免维数灾难，减少计算的复杂度。

1  “一带一路”航空网络的构建

以“一带一路”沿线国家为节点，构建“一带一路”沿线国家航空网络G。“一带一路”沿线国家为文献中常定义的65个国家[23]。本文认为两个国家间存在航班联系，则两个国家节点存在连接；反之，则不存在联系。“一带一路”沿线国家航空网络中的实际连边数量为679条。

以“一带一路”沿线机场为节点，构建“一带一路”沿线机场航空网络O。本文认为两个不同国家的机场间存在直达航班的，则认为两个机场节点存在连接。也就是“一带一路”沿线机场航空网络只考虑跨国航班以及存在跨国航班的机场，其他机场将被剔除，共有585个机场，“一带一路”沿线机场航空网络实际连边数量为3 540条。

2  基于支持向量机的“一带一路”沿线航空网络链路预测

2.1  支持向量机的建模理论

支持向量分类机的本质上就是对样本数据求分类函数，也就是模型的决策函数，根据决策值正确划分样本类别，如式（1）：

fx=signwx+b                                            （1）

其中：wx+b=0表示分类的超平面，记为L。w是法向量，为垂直于超平面的方向。b是样本到超平面之间的距离。对于点x，y，当wx+b>0时，该点为一类；当wx+b<0时，该点表示另一类。那么样本到分类超平面距离的绝对值为：

r=                                                （2）

对于样本来说，分类超平面有很多，但是只有使分类间隔最大时的分类超平面为最优分类平面。此时，在支持向量机中寻找决策函数问题就变为寻找超平面间的最大分類间隔问题。分类间隔为两类样本中离超平面最近的两点间的距离。假设所有数据点离最优分类平面的距离都大于1，就可以实现正确分类，那么样本x，y满足式（3）：

（3）

根据图1所示，距离超平面L最近的几个样本数据使得上式的等号成立，称这几个点为支持向量。支持向量之间的间隔为：

γ=                               （4）

对于最好的分类平面来说，他的γ值最大，那么寻找最优分类平面就变为寻找w和b使得γ最大，如式（5）所示：

（5）

s.t. ywx+b≥1， i=1，2，…，n

当样本数据量较大时，会有一噪声数据。为了最大化间隔的同时，不满足约束的样本要尽可能的少，也就是被错误划分种类的样本要少，所以，在此基础上增加松弛因子ξ和惩罚参数C，那么优化目标就变为：

min||w||+Cξ                                             （6）

s.t. ywx+b≥1-ξ， ξ≥0， i=1，2，…，n

其中：松弛因子ξ是用来衡量预测结果与样本实际结果的便利程度，它的值越小，说明模型的鲁棒性越好。惩罚参数C是用来代表错误划分样本的惩罚力度，用于调节正则化和经验风险之间的平衡。

对于在样本空间内无法线性可分的情况，可以将样本空间映射到高维空间来实现线性可分。在支持向量机中采用核方法，也就是引入核函数的方法将输入变量映射到高维空间。根据大量研究，常用的核函数有以下5种，如表1所示。

引入核函数后，优化目标变为：

||w||+Cξ             （7）

s.t. ywkx，x+b≥1-ξ， ξ≥0， i=1，2，…，n

求解上述最优解就可以得到本文要找的最优分类平面，以此划分样本类别。

2.2  链路预测指标和评价指标

基于网络结构相似性的指标众多，可以分为三大类：基于局部信息的相似性指标、基于半局域信息的相似性指标、基于全局信息的相似性指标。准确定义节点之间的相似性不是一件容易的事情，这些相似性指标无法保证在所有网络中都拥有较好的预测结果，所以本文将基于网络结构相似性从三个分类中选取共8个链路预测指标。

2.2.1  基于局部信息的相似性指标

（1）CN指标

CN指标认为两个节点间的共同邻居越多，两个节点越有可能相连。在“一带一路”国家航空网络中指两个国家间共同存在航班连接的国家数量越多，两个国家越有可能有航班联系。

S=Γi∩Γj                                           （8）

公式中的Γi、Γj分别表示i节点和j节点的邻居节点的集合。

（2）AA指标

AA指标将共同邻居节点度值的大小考虑进来，认为共同邻居的度值越小，这两个节点越相似，则越可能有连接。

S=                                            （9）

公式中的k为节点i和节点j的共同邻居k的度值。

（3）RA指标

RA指标与AA指标类似，只是对度值的惩罚权重不同。

S=                                             （10）

2.2.2  基于半局域信息的相似性指标

（1）LP指标

LP指标是在CN指标的基础上考虑多三阶路径。当ε等于0时，LP指标就是CN指标。

S=A+εA                                             （11）

公式中A、A分别指节点i和节点j之间路径长度为2和3的路径数。

（2）LRW指標

LRW指标为考虑有限步数t内的随机游走过程。

St=qρt+qρt                                        （12）

q=k/M表示节点i的初始资源分布，M为网络中的总边数，k为节点i的度值。ρt表示离子在t时刻从节点i出发，在t+1时刻刚好在节点j的概率。

（3）SRW指标

SRW指标是将LRW指标t步及以前的结果进行加总。这个指标给临近目标节点的点更多的机会与目标节点相连，考虑了网络的局域性。

S=Sl=qρl+qρl                                 （13）

2.2.3  基于全局信息的相似性指标

（1）Katz指标

Katz指标考虑了网络中所有路径，根据路径长度给定不同的惩罚机制。对于路径长度短的赋予较小的惩罚，对于路径长度长的赋予较大的惩罚，权重呈衰减系数。

S=β×A                                           （14）

公式中A为节点i和节点j间路径长度为i的路径数。β要小于邻接矩阵最大特征值的倒数。

（2）RWR指标

RWR指标是PageRank的拓展应用。它假设网络中的粒子，每游走一步都有一定概率返回原始出发点，是具有重启特性的随机游走。某一个粒子t时刻在节点i处，那么t+1时刻该粒子达到网络各个节点的概率向量为：

ρt+1=cPρt+1-ce                                        （15）

公式中c为粒子不返回原始点的概率，e表示一个一维一列向量仅有第i个元素为1，其他都是0，P为该网络的马尔科概率转移矩阵。

所以RWR相似性为：

S=ρ+ρ                                              （16）

公式中ρ为节点i出发的粒子走到节点j的概率。

2.2.4  评价指标

本文将使用AUC指标，对预测结果进行评价，在链路预测中可以代表链路预测算法的。在链路预测中，将AUC问题理解为在测试集N中随机选取一个节点对的分值大于一个不存在边集M中节点对的分值的概率。具体到模型来说就是，每次从测试集中N选取一个节点对，再随机从不存在边集N中选取一个节点对，如果前者的分支大于后者，则加1分；如果两个值一样就加0.5分，然后重复操作n次。如果任意测试集N中节点对的分值大于不存在边集M中节点对的分值，则AUC的值为1，为最好的链路预测算法。AUC定义如下：

AUC=                                            （17）

其中：n表示测试集中的分值大于不存在边集的次数，n表示二者分值相同的次数。

3  预测结果

在支持向量机分类模型中，评价指标有ROC曲线和正确率Accuracy指标。但是对于在不同类别上分布非常不均衡的样本，ROC曲线指标的结果更为客观。在本支持向量分类机中，主要目的是將已经有航班联系和未知即将有航班联系的节点对预测正确，而不是预测出不存在航班联系的节点对，所以本文选取ROC曲线来评价模型好坏。

将8个相似性指标作为特征单独输入支持向量分类机。由于8个特征的数据范围变为较大，为统一样本的统计性分布，本文对数据进行-1，1的归一化处理。也就是所有特征的数值变化范围都映射到了-1和1之间。为探究在相同相似性指标输入、核函数相同、参数默认的情况下，基于支持向量机的链路预测在“一带一路”不同层面航空网络的表现结果，选取径向基RBF核函数。以5折交叉验证的方式划分训练集和测试集。因篇幅原因，取部分图放置。

图2中（a）为Katz指标在“一带一路”沿线国家航空网络链路预测结果，（b）为LP指标在“一带一路”沿线机场航空网络链路预测结果。具体链路预测结果如表2、表3所示。

4  结  论

以支持向量机为分类模型，对“一带一路”沿线航空网络进行链路预测，把8个网络结构相似性指标作为单独的8个特征输入，得到如下结论：

（1）在基于支持向量机模型进行链路预测时，以8个网络结构相似性指标为特征输入，得到的“一带一路”沿线国家航空网络链路预测精确度AUC，要高于“一带一路”沿线机场航空网络。即越宏观的航空网络，其预测精度越高。

（2）基于支持向量机进行链路预测时，Katz指标几乎涵盖了所有能够预测链路的信息。相较于其他7个指标，Katz指标有最高的预测精确度，是一个比较重要且具有代表性的指标。

参考文献：

[1] 刘卫东. “一带一路”：引领包容性全球化[J]. 中国科学院院刊，2017，32（4）：331-339.

[2]  GANESH BAGLER. Analysis of the airport network of India as a complex weighted network[J]. Physica A， 2008，387（12）：2972-2980.

[3]  WANG， RU， CAI， et al. Hierarchical structure， disassortativity and information measures of the us flight network[J]. Chinese Physics Letters， 2005，22（10）：2715.

[4] 徐凤，朱金福，苗建军. 基于复杂网络的空铁复合网络的鲁棒性研究[J]. 复杂系统与复杂性科学，2015，12（1）：40-45.

[5]  ZHOU Y， KUNDU T， GOH M， et al. Multimodal transportation network centrality analysis for belt and road initiative[J]. Transportation Research Part E Logistics and Transportation Review， 2021，149（2）：102292.

[6] 王姣娥，王涵，焦敬娟. “一带一路”与中国对外航空运输联系[J]. 地理科学进展，2015，34（5）：554-562.

[7] 卓志强，姚红光. “一带一路”沿线航空网络结构及其鲁棒性研究[J]. 物流科技，2018，41（5）：78-84.

[8]  WANG K， FU X， CZERNY A I， et al. Modeling the potential for aviation liberalization in central Asia-market analysis and implications for the belt and road initiative[J]. Transportation Research Part A Policy and Practice， 2020，134：184-210.

[9] 杜方叶，王姣娥，谢家昊，等. “一带一路”背景下中国国际航空网络的空间格局及演变[J]. 地理科学进展，2019，38（7）： 963-972.

[10] 董兵. 航空交通系统的交通复杂性研究[D]. 成都：西南交通大学，2016.

[11] 洪彦. 从“集聚”走向“均衡”—中国航空网络与城市关联体系空间演化研究[D]. 上海：华东师范大学，2016.

[12]  LIBEN-NOWELL D， KLEINBERG J. The link-prediction problem for social networks[J]. Journal of the American Society for Information Science and Technology， 2007，58（7）：1019-1031.

[13]  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 & Information Processing， 2017，5（2）：49-66.

[14]  NAJARI S， SALEHI M， RANJBAR V， et al. Link prediction in multiplex networks based on interlayer similarity[D]. Univ Tehran， Fac New Sci & Tehran， Tehran， Lran， 2019.

[15] 劉宏鲲，吕琳媛，周涛. 利用链路预测推断网络演化机制[J]. 中国科学，2011，41（7）：816-823.

[16]  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.

[17] 李泽荃，杨曌，刘嵘，等. 复杂网络与机器学习相结合的研究进展[J]. 计算机应用与软件，2019，36（4）：10-28，62.

[18]  SHIBATA N， KAJIKAWA Y， SAKATA I. Link prediction in citation networks[J]. Journal of the American Society for Information Science & Technology， 2012，63（1）：78-85.

[19] 翟东升，刘鹤，张杰，等. 一种基于链路预测的技术机会挖掘方法[J]. 情报学报，2016，35（10）：1090-1100.

[20]  PC A， MS B， AK C. The applications of artificial neuralnetworks， support vector machines， and long-short term memory forstockmarket prediction[J]. Decision Analytics Journal， 2022（2）：100015.

[21]  WANG Q， YE M， WEI M， et al. Co-estimation of state of charge and capacity for lithium-ion battery based on recurrent neural network and support vector machine[J]. Energy Reports， 2021（7）：7323-7332.

[22]  HASAN， MOHAMMAD A. Link prediction using supervised learning[D]. Rensselaer Polytechnic Institute， Troy， New York， 2005.

[23] 种照辉，覃成林. “一带一路”贸易网络结构及其影响因素——基于网络分析方法的研究[J]. 国际经贸探索，2017，33（5）：16-28.