基于复杂网络的中国民航网络鲁棒性分析

谢本凯，李 琴，黄龚迪，林睿浚，李五双

（1.郑州航空工业管理学院 管理工程学院，河南 郑州 450046；2.郑州航空工业管理学院 信息管理学院，河南 郑州 450046；3.航空经济发展河南省协同创新中心，河南 郑州 450000）

1 引言

民航网络是实现航空交通运输的基础条件，它的稳定性和规范化是国家在航空领域发展水平的一个直观体现，其与其它类型的交通运输网络有较大不同，无论是在科技水平、空间跨度还是推动经济发展方面都更加亮眼突出。我国民航业处于成长时期，民航网络在工作效率和容错度等方面还不足以满足社会发展的需要，有明显的可提升空间。由于各种人为因素和自然因素，无法避免和预测的不稳定因素都可能对我国民航网络带来冲击和考验。怎么使我国民航网络改善优化、提高效率，从而大大提升我国民航竞争力是一个值得探讨的方向。

20 世纪中期随机图理论被提出，为复杂网络研究打开了大门。20世纪末Watts[1]和Barabasi[2]分别提出了被视为为复杂网络研究掀开新篇章的小世界网络模型和无标度网络模型。随后，关于复杂网络的剖析也开始渐渐深入，与此同时越来越多的学者将该理论应用于对现实网络的研究中。Oriol Lordan[3]等对全球民航网络的统计参数进行了研究，并分析了其鲁棒性，结果发现运用介数中心性自适应策略可以精准找出重要机场；Wei[4]等利用荷兰中压电力网的数据，研究了不同信息网拓扑和两类攻击方式对电力CPS 连锁故障的影响，得出小世界网络的信息网拓扑能使该网络鲁棒性更好；Lara-Cabrera[5]等利用复杂网络的拓扑性质分析CIG网络，研究了大规模结构、增长机制和其他特征之间的协作模式。徐伟举[6]等人分析了在动态和静态攻击两种模式下美国航空网络、SW 网络和BA 网络的抗毁性；魏震波[7]等总结归纳了在电网分析中应用到的一些研究成果，并针对研究方法和成果的质疑进行了较全面的分析；田庆飞[8]基于复杂网络理论和交通拥堵分析，对城市公交网络生成与优化的相关算法与方法进行了研究。而本文从随机攻击和蓄意攻击两个方面，采用平均路径长度、介数等参数分析了中国民航网络的整体鲁棒性。

2 理论概述

2.1 图论基础

民航网络可以被描述为一个二元组G=（V,E）,其中V={v1,v2,…,vn}是机场的节点集，E={e1,e2,…,em}是航线的边集，vi代表节点，ej代表边。用|V|表示V中的节点个数，|E|表示E的边数。在本文中，它被定义为无向无权网络，也就是说它的节点（va,vb）和（vb,va）表示同一条边，并且每条边不赋予权值。

2.2 平均路径长度

它可以描述民航网络中的平均分离程度。在所有连通节点va和vb的路径中，节点最少的那一条被称为两点间的最短路径，而最短路径的边数被称为节点va与vb之间的最短距离，它是指网络中所有最短距离里的最大数。而所有节点对的平均值就是平均距离L，一般计算公式为：

2.3 聚集系数

它是用来度量网络中节点聚集情况的参数，表现了网络的簇拥状态。通常可以用这一系数来描述网络局部的结构性质。记有ka个节点与va直接连接，则在无向网络中ka个节点最多可能有ka(ka-1)/2 条边，而真实存在的边数记为Ma,可将节点va的聚集系数定义为：

本文研究的我国民航网络，机场的簇拥情况就是节点的聚集系数。若机场的聚集系数大，说明它与其周围所连接的机场所构成的网络比较密集。

2.4 度与度的分布

度在复杂网络中是用来描述节点特性的基础参数，节点Va的相邻边数目就是它的度。度值的大小可以说明节点在网络中的重要程度。引用邻接矩阵C去定义它，那么C的某一行或某一列非零元素个数就是节点的度，用公式表现如下：

其中Cab表示矩阵C中非零元素。大多数真实网络节点度符合一定的概率分布，度的分布也是可以用来描述复杂网络统计特征的重要参数。在本文中P(k)就是用来描述中国民航网络中航线是k的机场占总机场数的比率，同时本文利用累计度分布表示度的分布状况。

2.5 连通子图和连通度

连通子图是指在网络中的一个子图内，任意两个节点间都最少存在一条连通的边。在一个复杂网络中，可能有许多相对独立的连通子图存在。而当无论在该子图中加入任何另外的节点都会影响这个子图的连通性时，这个子图被称为最大连通子图，也称为连通分支。连通图的连通程度就是连通度，它分为点连通度和边连通度，一般来说连通度越好，这个网络图也就越稳定。

2.6 小世界网络和无标度网络

小世界网络是指在一个结构很大的网络中，节点之间的连接相对密切的情况，它的统计特点在于聚集系数大，但平均距离较小；在复杂网络中的节点度分布如果符合幂律分布，就被称为无标度网络。

3 中国民航网络建模与统计特性分析

3.1 建立模型

本文以中国民航网络中的机场作为节点，并将机场之间的航线作为边进行建模。以2017年民航机场吞吐量排名的报告中我国现存机场为基准，共216个机场节点，经统计共有2 363条无向边。

由于中国民航网络的节点复杂性、结构复杂性和运行复杂性等会导致各种不确定因素产生，本文对实际民航网络做出如下设定：

（1）模型中中国民航网络的边就是民航的运行线路，并且所有边都是无向边；

（2）研究对象仅限于机场节点和机场之间的民航运输线路，不考虑其他的相关对象；

（3）民航航线的拓扑特性均相同，即不考虑航空效率是否不同，也不考虑机场功能参数的不同，也就是说在进行鲁棒性分析时网络中的所有节点和均是无权的；

（4）对于拥有两个或者超过两个机场的城市均视为一个节点，即将机场合并使图相应简化。

3.2 统计特性分析

机场节点度K表示的是与它有航线的机场的数目。经计算得出中国民航网络中的总度数为4 290，那么总的平均度就约为19.86，也就是说平均每一个机场与其他节点直接连接的航线约有20条。对数据进行统计分析可以得出图1的度分布曲线图。

图1 度分布图

中国民航网络的平均路径长度为2.41，这说明每两个城市的机场之间通过约2 次的转机就可以相互到达，而明显的是该网络的聚类系数较大，表现出强聚集性。由这两个特点可知其满足小世界特性，而在度分布图可以直观的观察到曲线中的最高点属于度数较小的节点，曲线的最低点属于度数较大的节点，说明该网络中有许多边数较少的节点和少量边数众多的集散节点，这明显是无标度网络的特征。综合而言，它具备小世界特性，但更多地体现无标度特性。表1是对近些年来相关文献中中国民航网络的特征参数值变化情况进行的统计。

表1 中国民航网络统计参数特征比较

从表中数据对比可知，我国民航机场数不断增加，从2005年至今已经扩建了将近100个机场；机场的大量增加使得网络中的航线也不断扩充，每个节点的度值增大，所以网络的平均度也逐渐增大；而平均路径长度在2012年前均不断减小，但2018年却大幅度增加，究其原因可能是增加机场时航线设定不够规范、合理。

4 中国民航网络鲁棒性分析

4.1 中国民航网络鲁棒性

网络鲁棒性一般指其节点或边被破坏的时候，网络能继续工作的能力，也叫做容错能力、抗毁性。网络的鲁棒性也与其规模的大小有关，若网络的规模越大，那么它可以替代的边就越多，但如果规模过大，它发生意外和故障的几率也比一般的网络大得多。

本文中国民航网络的鲁棒性为在该网络正常运转或者受到两类攻击时，具有一定的抵抗能力，这种能力的强弱程度称为鲁棒程度。当遭受不在承受能力范围内的意外攻击时，网络便无法保持原状。

4.2 干扰措施

分析中国民航网络的鲁棒性时，本文基于移出网络中节点从而引发故障的情况，对网络整体进行分析。当节点突然遭受袭击时，整个网络会发生一定的变化。对于节点的攻击分为随机攻击和蓄意攻击两种，随机攻击的发生可能是由于一些意外如天气原因等，这类攻击一般可以自我修复或重新连接以抵抗外部干扰；而蓄意攻击的情况，一般会有很强的目的性，使没有准备好的节点受到严重破坏，无法正常工作，深度影响网络功能并大大降低了网络维持自我安全的能力，恢复工作也会进行的很困难。本文为了更全面的分析中国民航网络，将从随机和蓄意两方面去考虑，以提高容错能力。

4.3 评估指标

本文选取平均路径长度、最大连通度与介数作为评估指标，对中国民航网络的鲁棒性进行分析。

（1）中国民航网络平均路径长度L。它是指网络中任两个不同机场节点之间的最短连接距离的平均值。用n 代表网络的节点数，dab表示节点a 与节点b之间的距离，则：

（2）最大连通度Gmax。这里指的是中国民航网络在受到干扰以后，它所有依然连接且还能正常运转的节点的网络中，所含最多节点数的集团中节点数占有其他剩余节点的比例：

（3）介数B。它是用来反映中国民航网络全局性的指标。在网络中有一些节点虽然度较小，但却是某两个集团的中间连接点，那么它也同样很重要，用介数便可以定义这样的节点。本文在进行蓄意攻击时，会选取介数值大的节点依次进行攻击，再进行特征参数分析。

4.4 仿真流程

针对中国民航网络的拓扑结构和其本身的复杂性，本节总结出了研究该网络鲁棒性的主要步骤，如图2所示。

图2 鲁棒性分析仿真流程图

5 基于复杂网络的中国民航网络鲁棒性仿真分析

5.1 仿真实验

在实验中模拟随机攻击时，首先进行随机节点选取，依次将故障点数设为节点总数的5%、10%、15%，并每次进行5 次实验取参数平均值以得到结果；而在模拟蓄意攻击时，先计算得出每个点的介数值，再按介数值由高到低排序，并从数值高的开始同样依次移出节点总数的5%、10%、15%。特别说明的是，本文利用数字表示每一个城市的机场，机场间的航线用如A—B的形式表示，模拟节点遭受攻击时便会将该节点所在的航线全部删除。

中国民航网络模型中节点总数为216，那么由216×5%、216×10%和216×15%可得出攻击的节点数为10 个、21 个和32 个。在仿真实验的随机攻击中，移除10 个节点平均有两个孤立节点，移除21 个节点和32 个节点均平均有3 个孤立节点；而蓄意攻击中，移除10 个节点后有12 个孤立节点出现，移除21个节点后有18个孤立节点出现，移除32个节点后有32个孤立节点出现。具体如图3-图5所示。

图3 平均路径长度变化趋势

5.2 仿真结果分析

在未进行两种攻击前，中国民航网络的平均路径长度为2.412，最大连通度为1，介数值为0.15。而在进行仿真模拟攻击后，每个数值都发生了一定的变化。显而易见的是，蓄意攻击后无论是哪一种参数增大或减小的趋势相较于随机攻击都更加剧烈。

（1）平均路径长度L。它是可以用来描述一个复杂网络中节点间连接密切程度情况的统计参数。若平均路径长度数值小，则说明节点之间关系密切，从某一节点到其他节点所用的时间更少，网络的整体连接性较好；若平均路径长度数值较大，则说明节点若想与某一非邻边节点有联系要经过更多的边和节点，在这期间意外情况很可能发生，这在中国民航网络中表现为从某机场出发要去某地的话周转次数将变多，所要消耗的时间也更长。由上一节的仿真结果可以分析出：

图4 最大连通度变化趋势

图5 介数变化趋势

在随机攻击模式下，尽管移出的节点数不断增加，该网络的平均路径长度的波动幅度却并不大，对于整个网络来说几乎没有什么影响；而在蓄意攻击模式下，中国民航网络的平均路径长度随着移除节点数变多，数值不断变大。由此可见中国民航网络在遭遇蓄意攻击时，若网络节点不断减少，系统内节点间的联系会不断的减弱，网络会显得更加脆弱，所以该指标参数反映了网络鲁棒性的降低。不仅如此，由统计曲线可以看出，在蓄意攻击模式下平均路径长度增大的速度相比之下也较快。也就是说，当故意移除重要性大的节点时，网络中受影响的节点会不断增多，网络内的故障会像病毒一样传染开来。

（2）最大连通度。这一统计参数可以用来反映当网络受到攻击后，该网络中依旧能正常工作的集团里包含的最多节点数。当网络的最大连通度为1时，表示网络处于正常状态。当最大连接度不断降低时，说明网络在受到破坏后规模在不断缩小，使得它无法将整个网络的所有节点都建立起连接，节点之间的沟通力在下降，系统也处于鲁棒性差的状态。由上一节关于最大连通度的仿真结果可以分析出：

在随机攻击的模式下，尽管移出的节点在不断增多，网络的最大连通度却变化不大，基本处于比较稳定的状态，当该网络中某几个节点发生意外时，对整个网络的最大连通度几乎没有影响；在蓄意攻击的模式下，随着移除节点的增多，网络中没有连接的单个节点的数目也在不断增大，网络的最大连通度越来越小，这说明网络在面临蓄意攻击时极大可能会产生分裂。该参数的变化曲线与平均路径长度呈现相似的趋势。

两种情况对比来看，因为随机攻击中移出的多是介数偏小的节点，保留了相对重要的节点，所以对于整个网络的性能影响并不明显，依然保持较好的鲁棒性。而带有针对性的蓄意攻击则会移出介数偏大的节点，随之而来的与其有连接的节点都会受到干扰甚至破坏，这也导致了网络中单个节点的出现，使整个网络鲁棒性变差。

（3）介数。在设定蓄意攻击时，便是依次移除介数值大的节点，再对整体进行分析，研究介数对于研究整个复杂网络的鲁棒性来说是必不可少的一步。在网络中，其他的统计参数会随着介数高的节点的消失发生相对而言很大的变化。在仿真实验中无论是哪种攻击，在移除节点后整体网络的介数都会产生一定变化，不过显然蓄意攻击情况下变化更剧烈些。在故意移除较多的介数数值高的节点时，整体介数值也变大了许多。

尽管有众多研究复杂网络鲁棒性的参数和方法，依然无法将真实网络的实际情况完全表现和拟设出来。许多实际的网络在运转的同时也在不断地变化着，并且可能产生干扰的因素也是数不胜数，每一个因素都会带来无法预知的后果。所以本文仅是构建出了简单的中国民航网络用于鲁棒性的演化模型，并对其进行两种干扰模式下的理论数据分析，协助产生更规范化的民航网络。

5.3 综合分析

经过上述分析，中国民航网络在随机攻击后各项评价指标均变化不大，但在蓄意攻击后平均路径长度迅速增加，最大连通度大幅度下降，并且整体介数值也发生了较大变化。也就是说，面对随机攻击时中国民航网络表现出明显的鲁棒性，而当蓄意攻击介数值较大的节点时，网络的鲁棒性较差。

6 结论

本文选用中国民航网络为基础模型，以复杂网络理论为基础对其进行鲁棒性分析。通过建立网络模型，分析了其平均路径长度和度分布等统计特性，得出其具备小世界特性、但更多地体现无标度特性的结论。在确定两种干扰措施和三个评估指标后，进行仿真实验。实验中随机攻击时依次随机选取一定量的节点移除，蓄意攻击时按介数值从大到小排序并依次移除一定量节点，最后利用统计参数分析中国民航网络鲁棒性。结果表明，随机攻击对网络的鲁棒性没有太大影响，但蓄意攻击某些介数大的节点时网络的平均路径长度增大，最大连通度变小，鲁棒性明显变差。

在实际运转的过程中，需要重点保障核心机场的正常运行，防止蓄意破坏的发生影响网络全局。本文实验分析所得出的结果，可以为中国民航网络的标准化和规范化提供参考，促进民航业进一步的发展。