考虑节点失效和边失效的航空网络鲁棒性

冯 霞，贾宏璨

(中国民航大学 a.民航信息技术科研基地，b.计算机科学与技术学院，天津 300300)

航空网络是以通航城市为节点，以通航城市之间的航线为边构成的复杂网络.恶劣天气、突发公共卫生事件[1]、恐怖袭击等事件都可能导致通航城市机场关闭或航线停飞，从而影响整个航空网络的运输效率，严重时甚至造成航空网络大面积瘫痪，带来高昂经济损失.航空网络的鲁棒性是指在机场或航线失效的情况下，航空网络维持其整体运输功能的能力，是航空网络布局优化的重要依据.

近年来，复杂网络研究发展迅速，为现实生活中复杂系统的结构特性分析和鲁棒性分析提供了强有力的理论基础[2-6].在交通运输领域，利用复杂网络理论进行运输网络鲁棒性分析已成为研究热点，如城市道路网[7]，海洋货运网[8]，铁路网[9-10]等，国内外学者开始借助复杂网络思想研究航空运输网络鲁棒性[11-12].文献[13]运用复杂网络方法来研究印度机场网络的结构和健壮性.文献[14]应用复杂网络理论对全球航空运输网络的鲁棒性进行了研究，提出了一种关键机场的确定方法.文献[15]研究澳大利亚机场网络在不同故障场景下的弹性.在国内，文献[16]率先开始研究航空网络的抗毁性，发现网络可靠性由少数关键机场决定.文献[17]设计随机干扰和蓄意攻击两种仿真系统研究中国航空网络鲁棒性.文献[18]研究了40年来中国航空网络的鲁棒性，发现在随机攻击下80%的机场失效或在蓄意攻击下20%的机场失效可能导致中国航空运输网络瘫痪.但此类研究都将航空网络建模为无权网络[19]，只考虑节点间的连接情况，忽略了节点间联系的紧密程度，难以确切描述航空网络真实特性.文献[20]以周航班数作为权重，分析了机场失效对航空网络的影响，并讨论了区域性枢纽的竞争地位.文献[21]以地理距离和乘客人数为权重，研究在不同攻击策略下全球机场网络鲁棒性.文献[22]构建了加权航空运输网络，评估了8个国家国内航空运输网络的加权效率和机场失效下的网络鲁棒性，但均未考虑航线失效情况下的航空网络的鲁棒性.

本文作者以通航城市为节点，城市间航线为边，航线年航班量为权重，构建航空网络，在分析网络拓扑结构特性的基础上，以最大连通子图相对大小和加权网络效率为测度指标，重点研究在不同攻击策略下节点(机场)失效和边(航线)失效对网络鲁棒性的影响.

1 航空网络模型

本文建模所用数据来源于《2018年中国民航统计年鉴》，主要包括2017年国内所有航线及其运量数据.将航空网络抽象为图G=(V,E,W)，其中节点集合V={vi:i=1,2,…,n}为所有通航城市机场，对于拥有两个及以上机场的城市，将其机场相关航线及运量数据进行合并，为描述方便，仍将机场称为节点；边集合E={ei:i=1,2,…,m}为节点之间的所有连边，两个机场之间若存在航线则建立连边，将直飞航线与经停航线合并，例如经停航线 “重庆—西安—大连”分解为“重庆—西安”和“西安—大连”两条航线；边的权重集合W={wij:i,j=1,2,…,n}为每条航线的年航班数量.考虑到在长距离范围内，航空网络的航线连接是对称的，本文没有区分航线方向，即所构造航空网络为无向加权网络.剔除重复航线，所构建航空网络共包括224个节点，2 615条边，其拓扑结构如图1所示.

图1 中国航空网络拓扑结构Fig.1 China’s aviation network topology

2 航空网络拓扑结构特性分析

采用节点度与度分布、加权平均路径长度、聚类系数等指标从不同角度分析航空网络的拓扑结构特性.

2.1 节点度与度分布

节点度是反映网络中节点相互连接统计特性的重要指标，节点i的度ki是指与该节点相连的边数之和，计算方法如下

(1)

式中：若节点i和节点j之间有连边，则lij为1，否则为0；N为网络中节点总数.一般来讲，节点度值越大，该节点与其他节点连接的范围就越大，节点也就越重要.图1所示航空网络中度值排名前五的节点分别是北京、西安、上海、成都和重庆，都是我国重要的枢纽机场所在城市.

度分布指的是任意选取网络中一个节点其度值恰好等于k的概率，此概率记为P(k)，即网络中度值为k的节点数占整个网络节点总数的比例.图2所示为图1所示航空网络的节点度分布，从图2可看出，该网络节点度分布近似幂律分布.这符合多数机场航线很少，而少数大型枢纽机场则可直接连接至上百个其他机场这一客观事实.

图2 中国航空网络节点度分布Fig.2 China’s aviation network node degree distribution

2.2 加权平均路径长度

无权网络平均路径长度L定义为网络中任意两个节点之间最短路径长度dij的平均值，计算方法如下

(2)

式中：L直接反映网络的连通性，L值越小则网络连通性越好.

在加权网络中，计算两个节点之间最短路径长度时需要考虑权重.如图3(a)所示，节点A和节点B之间连边的权重是节点A和节点C之间权重的两倍，意味着A传播给B的流量会比A传播给C的流量更多.如果计算节点A和节点C之间的最短路径，虽然直接连接的权重为1，但是通过节点B的非直接连接权重更大，因此流量通过节点B传播比节点A，C之间直接传播更加迅速.计算加权网络最短路径长度时，首先需对权重进行归一化处理，归一化计算方法如下

(3)

式中：Wij为归一化后的权重值；wij为归一化前的权重值即节点i和节点j之间的边权；m为网络G的总边数.归一化前初始权重如图3(a)所示，归一化后权重如图3(b)所示.然后，采用给权重取倒数的方法，使强连接之间的权重小于弱连接之间的权重，如图3(c)所示.

图3 三个节点的加权网络Fig.3 Three-node weighted network

(4)

式中：c、d指节点i与节点j最短路径上经过的节点.

加权平均路径长度Lw计算方法如下

(5)

经计算，图1所示航空网络加权平均路径长度Lw=3.047 4，取值较小，能满足现阶段我国航空运输需求.

2.3 聚类系数

网络中某个节点的聚类系数是指该节点的邻接节点之间的实际连边数量占最大可能连边数量的比例，节点i的聚类系数Ci计算方法如下

(6)

式中：ki为节点i的度值；Ei为节点i的邻接节点之间实际相连的边数.整个网络聚类系数C是指网络中所有节点聚类系数的平均值，C∈[0，1]，C越大，则网络中节点之间联系越紧密.经计算，图1所示C=0.76，取值较大，表明该网络连接较为紧密，结合2.2节得出的我国航空网络加权平均路径长度较小，可得出我国航空网络具有小世界网络特性[23].

3 航空网络鲁棒性评价策略

为了系统分析航空网络鲁棒性，本文提出一种考虑节点失效和边失效的航空网络鲁棒性评价策略，包括航空网络鲁棒性攻击策略和航空网络鲁棒性测度.

3.1 航空网络鲁棒性攻击策略

可以把恶劣天气、突发事件等导致的机场关闭或航线服务中断看作是航空网络中节点或边受到攻击并失效.为此，分别针对节点失效和边失效两种失效模式，研究分析航空网络在随机攻击和蓄意攻击下的鲁棒性.设计航空网络鲁棒性攻击策略如图4所示.

图4 航空网络鲁棒性攻击策略Fig.4 Attack strategy for aviation network robustness

3.1.1 节点失效(机场关闭)

随机攻击是指从网络初始状态开始，每次随机删除网络中的一个节点，循环实验直至网络中没有剩余节点.

蓄意攻击是指从网络的初始状态开始，每次删除网络中重要度最高的节点，节点失效的同时，与该节点相连的边也失效，然后重新计算网络中剩余节点重要度，循环实验直到网络中没有剩余节点.本文主要采用点强度，加权节点介数和PageRank度量节点重要度，表1是在网络初始状态下，分别按照这三种节点重要度排序排名前十的机场.

表1 网络初始状态不同节点重要度排序Tab.1 Node importance ranking in the initial state of the network

节点i的点强度等于与该节点相连的所有边的权值之和，记为Si，计算方法如下

(7)

式中：Γi为节点i的邻点集；wij是节点i与其邻点集中节点j之间的边权.

节点i的介数是网络中经过节点i的最短路径占所有最短路径的比，记为B(i)，计算方法如下

(8)

式中：σst表示节点s和节点t之间的最短路径数；σst(i)表示节点s和节点t之间经过节点i的最短路径数，加权节点介数在计算最短路径数时路径长度要考虑权重.

PageRank是一个迭代算法，初始时，每个节点的PageRank值都设置为1/N，在每一轮的迭代中，每个节点都沿着边给邻居节点传递1/k的PageRank值，其中k是节点的度值，经过t+1轮迭代后，节点i的PageRank值可以表示为

(9)

式中：β是阻尼系数用来表示在PageRank迭代过程中一个节点沿着边跳转到下一个节点的概率.(1-β)表示不沿着边跳转，而是在所有节点中随机挑选下一个节点的概率. 实际实验证明β被设置成 0.85 时 PageRank 的计算结果最符合实际情况.

3.1.2 边失效(航线停飞)

随机攻击指从网络初始状态开始，每次随机删除网络中一条边，循环实验直至网络中没有剩余边.

蓄意攻击是指从网络的初始状态开始，每次删除网络中重要度最高的边，然后重新计算剩余网络中边的重要度，并删除重要度最高的边，循环实验直到网络中没有剩余边.本文采用边权和加权边介数来度量边的重要度，表2是在网络初始状态下，分别按照这两种边重要度排序排名前十的航线.

边权是指两个节点之间连边的权重大小.边介数反应的是边在整个网络中的地位和作用，边eij的介数定义为网络中所有最短路径中经过该边的路径数目占最短路径总数的比例，记为B(eij)，计算方法为

(10)

式中：σst表示节点s和t之间的最短路径数；σst(eij)表示节点s和节点t之间经过边eij的最短路径数，加权边介数在计算最短路径数时，路径长度要考虑权重.

表2 网络初始状态不同边重要度排序Tab.2 Edge importance ranking in the initial state of the network

3.2 航空网络鲁棒性测度

复杂网络的鲁棒性，是指网络在遭受不同程度破坏时抵抗破坏的能力.本文研究的航空网络鲁棒性，是指自然灾害、突发公共卫生事件、恐怖袭击等紧急事件引发航线中断或机场关闭时，航空网络维持其整体运输功能的能力，具体表现为在攻击发生时能否到达最终目的地，并在确保到达目的地的情况下，尽可能确保运输效率.考虑到攻击可能带来节点失效或边失效，从而改变网络的结构和运输效率.本文采用最大连通子图相对大小和加权网络效率两个测度指标来衡量航空网络的鲁棒性，定义如下：

1)最大连通子图相对大小.最大连通子图是指网络遭到攻击后分裂出的最大连通分量，是反映网络连通性的指标，最大连通子图相对大小S定义为网络受到攻击后的最大连通子图的节点数与原始网络总节点数之比，计算方法如下

(11)

式中：N′是网络遭受攻击后网络的最大连通子图的节点数目；N是原始网络的节点数目.S越小表示网络受到的破坏越大.

2)加权网络效率.网络效率是指网络遭到攻击后结构变化对节点间最短路径距离的影响.对于无权网络，最短路径指两个节点(i,j)间边数最少的一条路径，边数就是两个节点间的最短路径长度dij.网络中两个节点间若不存在路径则最短路径长度为无穷大，两个节点之间的效率用两个节点之间最短路径长度的倒数来表示，其倒数为0不会影响计算结果.整个网络效率定义为所有节点之间效率的平均值记为E，计算方法如下

(12)

(13)

4 航空网络鲁棒性分析

4.1 节点失效时的鲁棒性分析

图5给出了航空网络中节点分别受到随机攻击和蓄意攻击后，最大连通子图相对大小S的变化，其中横坐标f表示网络的损毁程度，即受攻击节点数占初始网络总节点数的比例.由于航空网络初始状态没有孤立节点，所以初始状态最大连通子图相对大小S为1，随着被攻击节点数的增加，网络中逐渐出现孤立节点，最大连通子图的规模也在不断减小.从图5可以看出，在随机攻击下，当f接近1时，网络的最大连通子图相对大小S才趋于0.而在点强度，加权节点介数，PageRank三种蓄意攻击方法下，当失效节点数约为30%时,S已经趋近于0，其中加权节点介数攻击的方法对网络的破坏程度最大，当失效节点数为25%时，S值降到0.03左右，最大连通子图的节点个数仅为6，网络中航线数量是原始网络的1.9%，此时网络已经瘫痪.

图5 最大连通子图相对大小与节点删除比例的关系Fig.5 Relationship between the relative size of the maximum connected subgraph and the ratio of node deletion

图6给出了加权网络效率大小与节点失效比例之间的关系.

图6 加权网络效率与节点删除比例的关系Fig.6 Relationship between weighted efficiency and the ratio of node deletion

在初始状态下，加权网络效率Ew为0.67.相比随机攻击，蓄意攻击情况下Ew的下降速度明显更快，在失效节点达到20%时Ew已趋近于0，而随机攻击下，失效节点接近100%时，Ew才趋于0.从图6也可以看出，基于加权节点介数的蓄意攻击方法对网络的破环程度相较于其他两种蓄意攻击方法更大，当失效节点数为10%时，Ew值降到0.11，且受影响的航班达90.6%，航空网络大规模瘫痪.3种节点蓄意攻击策略下前十位失效的机场如表3所示.

4.2 边失效时的鲁棒性分析

图7给出了最大连通子图的相对大小与边删除比例之间的关系.图中横坐标f表示网络的损毁程度，即受攻击边数占初始网络总边数的比例.从图7可以看出，网络初始状态最大连通子图相对大小为1，且受到攻击初期一直保持此状态，在随机攻击与边权重攻击导致删除的边数比例达到约10%、在加权边介数攻击导致删除的边数比例达到约5%时，最大连通子图的规模开始不断减小.同时可以看出加权边介数攻击对航空网络的破坏力较强.对比图5与图7可以看出，节点攻击对网络的破坏程度要大于边攻击对网络的破坏程度，按加权节点介数攻击节点时，当失效节点比例达到约30%时，最大连通子图的相对大小趋于0，网络基本瘫痪；按加权边介数攻击边时，失效边比例为30%时，S为0.83，网络仍保持较好连通性.这是因为在网络中删除一个节点时，与这个节点相连的所有边都将被破坏，而删除一条边，与其相关联的两个节点并不会被删除，只有当与某个节点相连的所有边都删除时，这个节点才会被删除.

表3 三种节点蓄意攻击策略下前十位失效的机场Tab.3 Top 10 failed airports under three kinds of targeted attack strategies

图8给出了加权网络效率与边删除比例的关系.从图8可以看出在随机攻击下，加权网络效率缓慢减小，当f趋近于1时，加权网络效率才趋于0.但基于边权和加权边介数的两种蓄意攻击方法会使网络效率迅速下降，尤其是加权边介数的攻击方法，当删除边的比例为40%时，网络效率就降为0.1.与图7相比可以看出，本文采用的两种蓄意攻击边的方法，在网络结构发生变化时，对网络连通性与网络效率的影响不同，网络效率下降速度明显快于网络连通性.表4给出了在两种边蓄意攻击策略下前十位失效的航线.

表4 两种边蓄意攻击策略下前十位失效的航线Tab.4 Top 10 failed airlines under two kinds of targeted attack strategies

表5 单个节点失效加权网络效率下降比例前20位的机场Tab.5 Top 20 airports in terms of decline proportion with a single node failure weighted efficiency

图7 最大连通子图的相对大小与 边删除比例的关系Fig.7 Relationship between the relative size of the maximum connected subgraph and the ratio of edge deletion

图8 加权网络效率与边删除比例的关系Fig.8 Relationship between weighted efficiency and the ratio of edge deletion

4.3 单个节点和单条边失效时的鲁棒性分析

4.1和4.2分析了在不同攻击策略下，随着节点和边失效比例的增大对航空网络鲁棒性的影响，本节研究单个节点和单条边失效对网络鲁棒性的影响.由于单个节点或边失效时，最大连通子图这一鲁棒性测度变化并不明显.

本文采用加权网络效率下降的比例来衡量单个节点或边失效对网络的鲁棒性的影响，这一测度是对航空网络运输效率的刻画，计算方法如下

(14)

式中：Ew0表示航空网络初始的加权网络效率；Ew表示单个节点或边失效后当前网络的加权网络效率值；ΔEw表示单个节点或边失效后加权网络效率下降的幅度.

表5和表6分别为单个节点和单条边失效时加权网络效率下降比例前20位的机场和航线，是影响网络运输效率的关键节点和边.

从表5中可以看出昆明和乌鲁木齐节点失效后网络的加权网络效率下降的比例均超过了0.1，是西南地区和西北地区对网络运输效率影响最大的机场，且在西南地区成都比重庆对网络鲁棒性影响更大.上海、北京、广州、武汉、哈尔滨分别是华东地区，华北地区，华南地区，华中地区，东北地区对航空网络运输效率影响最大的机场，具有区域枢纽地位.

表6 单条边失效加权网络效率下降比例前20位的航线Tab.6 Top 20 airlines in terms of decline proportion with a single edge failure weighted efficiency

从表6中可以看出单条边失效对于网络鲁棒性的影响要小于单个节点，这些航线从拓扑指标如加权边介数的角度分析并不重要，但其失效对网络的鲁棒性影响相对较大，同时排名前20的航线中大多位于西北地区和西南地区，从侧面说明了西北、西南地区网络鲁棒性较弱.

5 结论

将中国航空网络建模成无向加权复杂网络，在分析航空网络拓扑结构特性的基础上,研究分析了航空网络的鲁棒性：

1)大部分节点随机失效时，航空网络仍可以保持连接，具有较强的鲁棒性，但是当蓄意攻击网络节点时，失效节点达到20%～30%时就会导致网络瘫痪.少数加权介数较大的机场对航空网络的整体连通性起着重要作用，这些关键机场出现故障更容易导致航空网络系统的整体瘫痪.

2)节点受到攻击对网络的破坏程度大于边受到攻击对网络的破坏程度，且加权节点介数和加权边介数攻击对网络的破坏力较强.

3)通过对单个节点和单条边失效时的鲁棒性分析，识别航空网络中的关键节点和关键边，发现西北地区与西南地区网络鲁棒性较弱，应对关键节点和边采取有效防护措施，降低突发事件给航空网络带来的损失.