基于改进连边删除评估法的关键航路段集合识别方法*

毕可心，温祥西，叶泽龙，刘瑜平，王 天

（1.空军工程大学空管领航学院，西安 710051；2.国家空管防相撞技术重点实验室，西安 710051；3.解放军95178 部队，南宁 530031；4.解放军93220 部队，哈尔滨 150046）

0 引言

复杂网络是对复杂系统进行抽象和具体的主要工具，连边代表复杂网络节点之间的联系和相互作用，但这些相互作用对网络整体的影响往往是不同的。想要寻求复杂系统的本质，需要把握住这些系统中重要的联系，即对于网络中的关键连边，需要通过一定的方法和手段进行识别。国内外学者在进行这方面的研究过程中主要形成了两种具有代表性的方法，基于边介数的评估方法和连边删除评估法。前者是从复杂网络的拓扑结构上，对网络连边的重要性进行评价，连边的介数越高，其在网络中的中心程度越高，关键性也越强；后者则是以连边自身对网络性能的影响来评价其对于网络整体的重要性，计算移除连边后引起的网络性能变化，变化幅度越大，连边在网络中的重要性就越高。后者的评估方式对实际网络而言更有意义。

文献［4］将连边删除评估法用于进行通信网络中重要链路的识别和保护；文献［5］将其用于研究城市群复合交通网络脆弱性，文献［6］提出了一种单条航路失效，利用级联失效理论确定关键航路的方法，通过对关键线路的加强防护，可以进一步降低城市交通和空中交通网络的脆弱性，减小交通大范围瘫痪的风险。文献［7］依据连边删除评估法，提出了基于最小连通支配集的复杂网络关键节点与连边集合识别方法，可以同时对复杂网络的关键节点和连边进行识别；文献［8］用连边删除评估法进行网络鲁棒性的评估；文献［9］将连边删除评估法用于网络中社团的区分。以上方法虽然通过连边删除法识别出了网络中的关键连边，但其普遍没能避免传统连边删除评估方法在识别关键连边集合时，识别结果静态，整体重要性减弱的问题。

综上，本文针对传统的连边删除评估法只能识别出单条连边的重要性，对关键连边集合的识别不够准确的问题，以航路网络为例，采用“不放回”的方式删除连边集合，通过多属性决策方法综合评估网络性能变化幅度，确定改航规划中的关键航路段集合，并与传统的连边删除评估法进行对比。

1 改进连边删除评估法

1.1 复杂网络模型

复杂网络模型，通常由节点、连边、权重等要素构成，其结构可表示为：={，，}。其中，表示整个网络，表示网络中节点的集合，表示连边的集合，表示权重的集合。

在航路网络中，网络的节点集={，，…，v}代表民航的机场、导航台等；网络中的边集={，，…，e}表示机场之间的通行关系，若两机场之间存在固定的航班，则认为其对应节点之间存在连边；={，，…，w}代表网络中的边权。

1.2 连边删除评估法

连边删除评估法是用于识别航路网络中关键航路段的基本算法。它通过评价特定连边在移除之后对网络性能造成的影响，得到此连边在网络中的重要度d。移除连边后网络性能下降幅度越大，则连边重要度越高。

传统连边删除评估法采用的是“放回式”的思想，每次只剔除一条连边后分析剩余连边网络性能变化，再将其放回原网络中，以此建立连边的关键性排序。定义重要度矩阵D（d），d为删去与的连边后，网络性能的变化值。d为连边的重要度，R为初始网络初始性能。

但由于识别一组关键的航路段集合，并不是一个简单的静态过程。传统连边删除评估法忽略了网络的动态变化过程，所得到的关键连边只是相对于网络的全拓扑结构这一状态而言的，因此，该方法在用于对航路网路影响重大的航路段集合进行评估时，所得结果并不是最优的。

1.3 改进流程

本文采用“不放回”的思路对连边删除评估法进行改进。假设航路网络中有条连边，需要识别出条关键航路段，其具体步骤如图1 所示。

图1 改进连边删除评估法步骤

Step 1：删除航路段，基于多属性决策方法对航路网络性能评估，计算得到网络性能变化值；

Step 2：将航路段放回网络，+1，逐次计算出全部航路段对应的网络性能变化值集合{}；

Step 3：按照关闭航路后引起航路网络性能的变化程度对航路重要度进行排序，得到航路重要度序列{，，，…，e}。值越大，航路e在重要度序列中的排名越靠前；

Step 4：剔除航路重要度序列{，，，…，e}中此时排序为第1 的航路段，得到新的网络G。

Step 5：输入G，=+1，=-1 等新的参数，跳转回到Step1，重复Step1～Step4 的操作，直至，满足终止条件，得到被删除的关键航路段集合E。

2 网络性能评估

2.1 多属性决策分析

本文用多属性决策评价方法对网络性能进行评估。网络性能评估的对象是删除一组航路后的航路网络，可以将其看做一种方案，而航路网络的性能评估指标最大连通子图尺寸SS、网络效率等则可以视为方案的属性。如此，可将网络性能评估问题转化为多属性决策问题。

如此，可定义航路网络G中的第个指标为G（S）（1，2，…，；1，2，3，4，5），构成决策矩阵X：

之后，对矩阵指标进行标准化处理：

利用TOPSIS 方法，通过矩阵Y 可以确定正理想方案，为各可行方案中各指标值最大者，即剔除航路段集合后，航路网络性能值变化最小的方案：

之后，计算任一方案G到正理想方案的距离：

D越大，方案G到正理想方案的距离越远，也就说明移除航路段集合后的网络G综合性能下降越多，即这一航路段集合关键性越强。

2.2 指标及其权重

为了对网络性能进行更好地评估，本文选取5个性能评估指标，分别从连通性、稳定性、负载能力、网络聚集程度对网络性能进行评价。

1）最大连通子图尺寸。航路网络是用于提供客运、货运服务的运输网络，网络中的节点以航路段进行连接，节点只有与其他节点相互可达时，才能在网络中发挥其作用。因此，最大连通子图尺寸是一个评价网络连通性和运输能力的重要指标，尺寸是最大连通子图中节点的个数，越大，网络连通性越好。

如图2 所示，网络中共有20 个节点，其中节点3，4，11，16 为孤立点，因此，这个网络不是完全连通的，其最大连通子图尺寸为16 个节点。

图2 最大连通子图示意图

2）网络平均最短路径的倒数。平均最短路径的定义是为网络中任意两点之间最短路径之和占网络中可能存在的最多边数的比重。取其倒数来描述网络的脆弱性和抗毁能力，其计算如公式（8）：

在复杂网络中，越大，平均最短路径越短，说明网络中的节点相互可达的中转次数就越少，这意味着航班流量在机场、导航台等节点运行更加畅快，网络连通性更好，网络风险值也更小，中转成本越低，业务往来更加快捷。

如图3 中所示，经计算平均最短路径为2.977 0，值为0.335 9。其中，节点3 节点15 的最短路径最长，其路径为“3-4-5-13-28-24-15”。

图3 平均最短路径示意图

3）网络平均聚类系数。单独一个节点的聚类系数是用来描述节点之间聚集成团的程度，整个网络的平均聚类系数则可以描述全局的聚集程度。单个节点的加权集群系数的计算如式（9）所示：

4）网络鲁棒性。本文以网络点权分布的均匀程度作为网络的鲁棒性，其计算如式（10）所示：

5）网络负载能力。本文以航路网络中各边权值之和为的值。航路网络的边权值一般取流量或者航路段距离。流量边权直观地用流量衡量了负载能力。而距离边权同样也可以反映负载能力，为了保证飞行安全，同条航路上的飞行器通常留有一定飞行间隔，在管制技术水平相同的条件下，可以认为一条航路段上的飞行容量与航路段的长度成正比。因此，在基于距离边权的航路网络中，值取网络中所有航路段上的航路距离之和，其计算如式（11）所示：

为了综合评估网络的性能，需要对以上5 个指标进行加权处理。本文使用层次分析法（The Analytic Hierarchy Process，AHP）计算指标的权重。网络负载能力在网络整体性能中最重要，最大连通子图尺寸次之，和的重要性相当，鲁棒性的重要程度最弱。综上，5 个指标的重要度排序为。通过AHP 计算，其权重向量如下：

3 实验分析

通过对昆明管制区的机场、导航台、航路信息进行搜集与处理，本文建立了62 个节点、80 条边的昆明航路网络，其网络结构如图4 所示。以该网络为对象，进行关键航路集合的识别。

图4 昆明管制区航路网络示意图

首先使用传统“放回式”方法对关键航路进行识别，依次移除各条航路，计算其移除后引起的网络性能变化值，可得到航路重要度排序表如下页表1 所示。

表1 传统识别方法得到的航路重要度排序

在移除不同数量的航路段时，通过本文提出的改进连边删除评估法，移除相应的关键航路集合，引起的航路网络性能变化如下页图5 中红色曲线所示。同时，按照传统连边删除评估法得到航路重要度排序表，在求取不同航路段数量的关键航路时，按重要度剔除相应数量的航路段，其引起的航路网络性能变化如图5 中蓝色曲线所示。

从图5 中可以看出，改进的连边删除评估法识别出的航路段集合关键性更高，对网络性能的影响更为显著。这是由于航路网络结构的特殊性造成的，在关键航路段数目为1 时，两种方法得到的最关键航路段相同，均为航路段“MEPAN-耿马VOR（GMA）”，剔除后航路网络性能由初始的0.812 0 下降为0.774 6，在识别单条航路关键性时，两种方法的优越性一致。但随着关键航路数目的增加，关键航路集合识别方法的优越性表现明显，移除10 条航路段时，航路网络的性能就已经下降到了0.289 8，而传统连边删除评估法的网络性能依旧维持在0.620 7，差距明显。这进一步说明了传统算法对关键航路的识别是静态的，它所识别出的是单条航路段自身对整个网络的影响程度，以此得到的关键性排序实际是静态的，随着所寻找的航路段数目的增加，一些自身重要度不强的航路段在这一动态过程中体现出了更为关键的作用。在剔除一定数量的子网络中，航路段只有存在于的最大连通子图之内才能发挥作用，孤立的航路段对航路网络而言没有意义。综上，本文提出的关键航路识别算法能够识别出对网络性能发挥起到关键性作用的航路网络集合，与传统连边删除评估法相比，能够反映网络结构变化的动态过程，识别出更为关键的航路段集合。

图5 两种方法的航路网络总性能变化

其他具体网络性能指标随着关键航路段识别数目的变化如图6 所示。

图6 5 项网路性能指标变化

从图6 中可以看出，和值下降趋势与总性能的趋势相近似，在剔除1 条关键航路段后，这2项指标都基本下降了60%以上。值不断上升，是由于随着网络最小连通子图尺寸的不断减小，剔除了孤立的节点以后，仅计算最大连通子图的稳定性和鲁棒性，反而上升，此时值仅用于评估网络健康程度。随着网络规模的减小，值也逐渐下降；而随着剔除的航路段数目增加，网络趋于消解，孤立点越来越点，聚集程度也逐渐下降。这5 项指标的变化符合预期。

利用改进的连边删除评估法对昆明管制区航路网络数目为11、18 的关键航路段集合进行识别，识别结果如图7 所示。

图7 昆明航路网络中的关键航路段集合示意图

如图6（a）所示，剔除这11 条航路后，航路网络的总性能下降为0.250 1，剩余网络的平均最短路径为2.989 5，即任意节点之间相互到达平均需要中转1.989 5 次；=0.261 3，剩余网络的航路段总距离为4 330 km；网络平均聚类系数为0.124 7，聚集程度与原网络变化不大；最大联通子图尺寸为20 个，网络连通性大幅下降；网络鲁棒性上升为0.038 4，这是网络结构缩小的缘故，使得剩余网络反而更为稳定。分析不同数目下的关键航路段集合发现，改进连边删除评估法得到的关键航路段集合之间没有明显的继承关系，在识别11 条关键航路段时识别出了边“43-24”，但在识别18 条时则没有这条边。

4 结论

本文提出了一种改进的连边删除评估法，该方法采用“不放回”的方式剔除网络中的连边，通过多属性决策方法对剔除连边后的网络进行综合性能评估，根据性能的下降幅度可以准确识别出网络中不同规模的关键连边集合。最后，以对昆明管制区航路网络为实验平台，进行实验分析，结果显示，改进后的连边删除评估法对关键航路段集合的识别效果更好，可以在识别过程中反映航路网络结构变化的动态过程，迅速发掘出潜在的关键航路段。