航空公司超网络的拓扑结构与鲁棒性分析

2021-03-01术永昊郭进利

智能计算机与应用 2021年12期

术永昊，郭进利

（上海理工大学管理学院，上海 200093）

0 引言

截止到2020 年，中国境内运输机场（不含香港、澳门和台湾地区）共有241 个，其中定期航班通航机场240 个［1］。这些机场包含许多航空公司，其中东航2020 年旅客运输量实现7 458 万人次［2］；南航运输9 700 万人次，全年航班正常率连续五年在三大国有航司中排名第一［3］；厦门航空运输2 141 万人次，是全球唯一保持34 年持续盈利的航司［4］。随着中国航空公司数量的不断增加，冲突也在加深，航空公司所面临的突发事件所带来的一系列反应对航空公司超网络的损毁程度，严重影响航空运输的高效性和经济性。因此本文对航司超网的拓扑结构与鲁棒性进行分析，并提出相应的优化网络建议。

1 文献综述

在大多数拓扑结构中，航空网络可以由一组节点（机场或航点）和链接（航班线路或航线段）组成，其中链接表示两个节点之间的交互。在文献中，许多作者广泛使用复杂网络理论应用于相关领域的研究，得出对航空网络静态和动态方面的影响。Song and Yeo 采用复杂网络方法，研究了全球1 060个机场的航空运输网络，采用若干中心性指标来识别具有高中心性指标的机场，并分析国家层面的航空网络连接结构［5］；Lin and Ban 从中心性分布和结构属性两个方面分析了1990～2010 年美国航空网络的时间演化，研究发现关键结构特征形成于航空网络发展的早期阶段，经济和地缘政治因素是决定航空网络发展的主要因素［6］；Kim 和Yoon 研究了亚洲东北部航线网络，将航空网络描述为航线段网络，通过网络鲁棒性分析，发现航空网络在一组高中心性的关键节点上比随机故障更容易受到攻击，加强了区域协调以减轻各种风险的必要性［7］；吴佳益通过对比历年中国航空网络模型，运用多层复杂网络理论建立以航司为节点的中国航空多层网络，并分析其结构特征与演化规律［8］。

通过上述分析发现，当前关于航空方面的研究文献大多数是基于复杂网络方面的观点，但复杂网络在描述协同关系方面有一定的局限性，而在超网络中每条超边可以包含多个节点，并且超边又可以表示节点之间的的共同作用。例如：索琪总结了基于超图的超网络的相关概念以及静态拓扑指标［9］；陆睿敏将公交站点视为超边，线路视为节点，构建了公交超网络，并分析其网络特性，最后通过分析网络的抗毁性得出随机攻击的稳定性要强于蓄意攻击［10］；胡枫等人以蛋白质为节点，复合物为超边构建了超网络，分析网络的结构特征，识别出关键蛋白质，并对其数据进行了验证［11］；王志平等人通过利用超网络，将舆论中的关键词作为节点，关键词构成的话题作为超边，构建了舆论演化动态的超网络模型，得出节点超度符合幂律分布这一特征的结论［12］。

本文将航空公司作为节点，运输机场作为超边，可以更好地体现各航空公司在机场中的分布情况，分析组成的航空公司超网络的拓扑特性与稳定性，针对网络的抗毁性提出合理的优化建议。

2 超网络的相关概念

网络中的节点类型越来越多样，之间的相互作用也越来越复杂，而超网络的提出给出了一种对于高阶相互作用最普遍、最不受约束的一种表达。超网络一般分为两种，基于网络的超网络，基于超图的超网络。前者关注现实网络多层、多级、多维网络流的复杂特性，适合解决多层次网络的建模问题；后者以超图理论为基础，超图中每条超边包含多个节点，节点之间的相互联系可以通过超图清晰的表达。本文选择基于超图的超网络构建模型，研究机场中各航司的拓扑结构及其稳定性。

2.1 超图的概念

超图是由节点集V＝｛v1，v2，…，vn｝和超边集E＝｛E1，E2，…，Em｝组成，其中ei≠Φ（i＝1，2，…，m）［13］。超图H＝｛E1，E2，…，Em｝，同时还满足：Ei⊂Ej⇒i＝j。如果某一条超边Ep（p＝1，2，…，m）同时包含节点vi和vj，即这两个节点归属于同一条超边，则称vi和vj（i，j＝1，2，…，n）是邻接的，称Ep与vi（或vj）相关联。若Ep∩Eq≠Φ，即两条超边的交集不为空，则称超边Ep与Eq（p，q＝1，2，…，m）邻接。

超图的示例如图1 所示。节点集V＝｛v1，v2，v3，v4，v5，v6，v7，v8｝，超边集E＝｛E1，E2，E3，E4｝，其中，E1＝｛v1，v2，v5，v6｝，E2＝｛v2，v3，v6｝，E3＝｛v4，v5，v6｝，E4＝｛v7，v8｝。图1 中E1、E2、E3、E4所包含的节点数不全相同，即为非均匀超图。如果每条超边中的节点数相同，则称为均匀超图或一致超图。

在超图中也可以用关联矩阵来描述节点与超边的关系。如果节点vi与超边Ej相关联，则第i行和第j列中的项为1，否则为0［14］。于是，得到图1 的关联矩阵Im×n，其中每一行代表一个节点vn，列代表每一条超边Em，如图2 所示。

图1 非均匀超图Fig.1 Non uniform hypergraph

图2 关联矩阵Fig.2 Incidence matrix

2.2 超网络的概念

假设Ω＝｛（V，E）│（V，E）是有限超图｝，G是从T＝［0，＋∞）到Ω的映射，对于任意给定的t≥0，G（t）＝（V（t），E（t））是一个有限的超图，指标t通常被认为是时间。超网络｛G（t）│t∈T｝是指超图的集合，从超网络的定义可以看出：超网络是超图概念的推广，超网络更多的是用来描述网络的动态特征［15］。

2.3 拓扑参数的定义

（1）节点度：超网络中，超边包含该节点，则视超边连接了这个节点。同一条超边的节点视为相互连接，包含相同节点的两条超边视为相互邻接。节点度指与节点vi邻接的其它节点数量，记为di［16］。在图1 中，d1＝3，d2＝4，d3＝2，d4＝2，d5＝4，d6＝5，d7＝1，d8＝1。

（2）节点超度：节点超度定义为包含节点vi的超边个数，记为dH（vi）［17］。在图1 中，dH（v1）＝1，dH（v2）＝2，dH（v3）＝1，dH（v4）＝1，dH（v5）＝2，dH（v6）＝3，dH（v7）＝1，dH（v8）＝1。在图1 的关联矩阵中，第n行元素之和也可以计算出节点超度。

（3）超边度、超边超度：超边度是指超边所邻接的其它超边个数，即与该超边存在公共节点的超边数，记为dhd（Ei）。超边超度是指超边所包含的节点个数，记为ds（Ej），在图1 的关联矩阵中，第m列元素之和也可以计算出超边超度。

（4）聚类系数：聚类系数反映了节点的邻域密度［18］。节点i与ki个节点通过超边直接相连，ki个节点间实际存在的超边数为Ni，这ki个节点间可能存在的最大超边数为ki（ki－1）∕2，那么节点i的聚类系数Ci为：

（5）平均路径长度：网络中从一个节点（超边）到达另一个节点（超边）所需距离可体现网络的效率或能力。超网络中两超边的距离是指超边之间最少的连接数，定义超网络平均距离长度为任意两条超边距离的平均值［19］。

3 航空公司超网络模型构建与拓扑特性分析

3.1 航空公司超网络模型

本研究的数据来自中国民航局（http：／／www.caac.gov.cn／）以及各航空公司官网。选取2020 年民航机场生产统计公报中吞吐量前二十的民航机场：广州白云、成都双流、深圳宝安、重庆江北、北京首都、昆明长水、上海虹桥、西安咸阳、上海浦东、杭州萧山国际机场等作为超边，以机场中运营的国内东方航空、国际航空、深圳航空、山东航空、吉祥航空等44 家航空公司作为节点，构建航空公司超网络模型示意图，如图3 所示。

图3 航空公司超网络模型示意图Fig.3 Diagram of airlines hypernetwork model

3.2 超网络拓扑特性分析

3.2.1 度分布

度分布P（di）表示在节点度值分布空间内，节点度为di的节点数量占所有节点数量的比例分布情况。航空公司超网络包含44 家航空公司，超网络的度值分布如图4 所示，平均度＜di ＞为36.341，说明每家航司大约与36 家航司存在联系，平均度值较大，说明大多数航司通过机场相互连接，航空公司间的紧密程度较高。度值最小为15，度值最大为43。航司超网络中度值较大的国际航空、东方航空、深圳航空、海南航空、山东航空等相连的航司较多，因此在网络中起到关键中心的作用。

图4 航空公司超网络节点度值分布Fig.4 Degree distribution of airline hypernetwork nodes

3.2.2 超度分布

超度分布P（dH）表示在点超度值分布空间内，点超度为dH的节点数量占所有节点数量的比例分布情况。超网络的超度分布如图5 所示，平均超度＜dH ＞为10.205，说明每家航司被10 座机场包含，超度值越大，说明该节点在超网络中具有关键作用，也是网络中脆弱性节点，需要加强对航司的运营保护，保证整个网络的安全。

图5 航空公司超网络节点超度值分布Fig.5 Hyperdegree distribution of airline hypernetwork nodes

衡量网络中航司的重要性时，需要同时考虑节点的点度与超度，因此本文做散点图来进行分析，如图6 所示。当网络中某个节点的点度和超度较大，那么该节点在网络中较为重要，图6 中位于右上角的节点：东方航空、国际航空为网络中最关键的节点。

图6 超网络点度与点超度的散点图Fig.6 Scatter graphs of degree and hyperdegree

3.2.3 超边超度

超边超度ds（Ej）在超网络中指每座机场所包含的航司数量，在航空公司超网络中超边超度的分布情况如图7 所示。超边超度较大的机场，如：长沙黄花、海口美兰、昆明长水等是中国航空公司超网络中较为重要的机场。

图7 超网络超边超度分布Fig.7 Hyperedge hyperdegree distribution of hypernetwork

3.2.4 平均路径长度和聚类系数

本文节点数和超边数分别代表航空公司和民用运输机场的数量。如果两家航空公司同时出现在一个超边中，这时认为这两家航空公司是有连边的。使用Gephi 软件，将超网络转化为普通的复杂网络，形成航空公司超网络的投影网络，如图8 所示，计算得出网络的平均路径长度为1.177 和聚类系数为0.904。

图8 航空公司超网络的投影网络Fig.8 Projection network of airline hypernetwork

3.2.5 航司网络的特性

由于航空公司超网络的平均路径长度与聚类系数接近于1，说明网络的航司与航司之间传播迅速，节点分布较为密集，大多数节点可以经过少量的边到达另外某个节点。这意味着航空公司超网络所对应的投影网络极为稠密，连通程度高，节点近似全连接，在这种网络上传播的速度极快，节点与节点之间可以通过某几个节点相互到达，因此该航司超网络具有小世界特性。

另外一种特性则是网络中的幂律分布，其显著特征是大部分节点的节点度值较小，少部分节点度值较大，也就意味着绝大多数的事件重要性都很小，只有极少数的事件重要性很大，而幂律分布又称无标度分布。根据网络中的数据分析航空公司超网络的节点的双对数度分布如图9 所示，得到拟合幂函数，式（2）：

图9 双对数坐标下节点度累计分布图Fig.9 Cumulative distribution of node degree in double logarithmic coordinates

同时得到图10 的节点超度的累计概率分布图，拟合幂函数，式（3）：

图10 双对数坐标下节点超度累计分布图Fig.10 Cumulative distribution of node hyperdegree in double logarithmic coordinates

由式（2）可知，节点度累计概率分布的指数为－3.280 1，小于0，并不服从幂律分布的定义，并且在式（3）节点超度的累计概率分布函数中指数为－0.637，同样小于0，因此认为航空公司超网络的拓扑结构不具备无标度特性。

通过分析航空公司超网络的拓扑结构指标，认为航空公司超网络具有明显的小世界特性，网络本身节点通过较少的转换就能连通，网络聚集程度高，连通效率高。

4 航空公司超网络鲁棒性分析

通过分析航空公司超网络的基本拓扑性质，进而了解航空公司在各座机场的分布。现实民用运输机场的稳定性及抗毁能力不仅会受到航空公司的影响，同样也会受到外界环境对网络的影响，如航空器故障、危险物品污染、挟持、爆炸物威胁等。因此本文从网络的鲁棒性指标出发，分析不同情况下航空公司超网络的稳定性。

4.1 鲁棒性指标

网络鲁棒性直观地来说是指网络在受到外部不确定干扰或者内部不稳定因素时，能够保持其功能正常工作的能力［20］。在航空公司超网络中，鲁棒性体现在民用运输机场在遭遇突发事件时保持其稳定的能力，通常采用的衡量指标包括聚类系数、全局网络效率、最大连通子图和平均最短路径等。全局网络效率用来衡量网络的有效性，聚类系数通常用来衡量具有相同邻居节点之间的连通性，所有的系数都在0－1 之间，其值高说明聚类系数高，网络的连通性强。因此本文选取全局网络效率和聚类系数作为航空公司超网络的鲁棒性指标进行分析。

聚类系数公式如式（1），节点聚类系数的变化幅度大小可以衡量网络的鲁棒性。全局网络效率的公式如式（4）：

其中，N表示超网络中航空公司的数量，dij表示节点与节点间的距离（最短路径）。

由于本文为非加权超网络，因此节点与节点间的最短距离为两节点间的最少超边数量。

4.2 攻击策略

本文对于航空公司网络的鲁棒性分析，主要体现在随机攻击和蓄意攻击两种攻击策略对网络效率与聚类系数的变化情况，同时对网络的鲁棒性进行评价优化。具体来讲，航空公司超网络可能会面临如危险物品污染、临时取消航班、改签等随机攻击，或者发生爆炸物威胁、挟持等蓄意攻击事件，分析其稳定性，并提出优化意见。

4.3 鲁棒性分析

4.3.1 随机攻击

将超网络中每家航空公司进行随机排序，依次选择4 个节点进行删除，计算网络的网络效率与聚类系数的指标。为了保证实验的准确性，该实验重复随机进行50 次，取50 次实验中的平均值作为最后结果。

4.3.2 蓄意攻击

为了分析基于蓄意攻击策略的航空公司超网络的鲁棒性，首先将超网络中节点的度和超度从大到小排序，依次攻击，再用同样的方法计算网络的鲁棒性指标。本文分析随机攻击与蓄意攻击对航空公司超网络的网络效率与聚类系数所产生的影响，仿真计算这两种策略下网络的聚类系数与网络效率的变化曲线，如图11 和图12 所示。

图11 随机攻击与蓄意攻击聚类系数对比Fig.11 Comparison of clustering coefficient between random attack and deliberate attack

图12 随机攻击与蓄意攻击网络效率对比Fig.12 Comparison of network efficiency between random attack and deliberate attack

当某家航空公司或者机场受到攻击时，网络中节点和超边数量的减少，节点的邻居节点之间互连的概率同样也会减少，导致航空公司超网络的聚类系数降低。又由于网络的连接程度降低，两家航空公司无法进行中转或改签服务，最终导致网络的全局效率降低。

在图11 中，当节点失效数逐渐增加时，基于节点超度攻击的网络聚类系数下降最快，节点度攻击次之，说明以某机场为攻击对象进而攻击其它机场，导致网络的聚类系数下降快于点度攻击，点度攻击通过攻击航空公司来破坏网络，因为本身网络是小世界网络，其中一家航空公司被攻击，与之相互有连接关系的航空公司之间没有影响，因此，点度攻击对聚类系数的影响要小于点超度攻击，而随机攻击下降最慢。网络被随机攻击36 个节点后，开始呈现断崖式下降，当网络的所有节点全部失效后，网络的聚类系数为0；而点超度攻击在节点失效数为24 时开始下降，直到失效28 个节点时，网络的聚类系数为0。因此对于网络的聚类系数而言，随机攻击的鲁棒性要强于蓄意攻击。

在图12 中，网络的点度攻击和点超度攻击对全局效率的影响相差不大，基于随机攻击的鲁棒性要优于蓄意攻击，随机攻击36 个节点网络的全局效率呈断崖式下降，当达到40 个失效数时，网络已达到崩溃状态。而蓄意攻击在节点失效数达到28 时，网络的全局效率为0，网络完全失去作用。

最后，由于图11 中网络的全局效率与聚类系数变化情况在随机攻击与蓄意攻击对网络抗毁程度方面的分析基本一致，说明了上述分析结果更加可信。