基于接近度与评价矩阵的关键机场节点识别*

涂从良，吴明功，温祥西

（空军工程大学空管领航学院，西安 710051）

基于接近度与评价矩阵的关键机场节点识别*

涂从良，吴明功，温祥西

（空军工程大学空管领航学院，西安 710051）

针对目前关键节点识别方法单一、难以适应航空网络的特点，提出了一种基于接近度与重要度评价矩阵的识别算法。利用改进的接近度算法反映节点在网络中的位置信息，考虑网络边权即航线流量，构建重要度评价矩阵，最后进行计算得到节点重要度排序结果。在建立我国航空网络模型的基础上通过实验得出：北、上、广以及位于网络几何中心且流量较大的西安等机场为关键节点。排序结果表明该算法能有效结合我国航空网络实际特点，准确地反映各个机场节点的重要性程度。

航空网络，关键节点，接近度，评价矩阵

0 引言

随着航空运输业的快速发展以及航空流量的增加，我国的航空网络已形成并不断扩张。航空网络作为交通命脉，与国家政治、经济、科技的发展有着紧密联系。而关键节点又在航空网络中扮演着重要的角色，如果关键机场节点发生拥塞、失效等情况，就很可能造成整个网络的瘫痪，从而严重影响社会稳定。因此，研究航空网络的关键节点识别具有重要的理论价值和现实意义。

航空网络是典型的复杂网络［1］，具有复杂网络的特征和性质。目前，对复杂网络关键节点识别的理论性研究已成为一个重要课题。以往的关键节点识别方法存在的不足主要有两点：一是侧重节点相互关系以及网络拓扑性质，忽略了网络边权的重要性。如文献［2］提出的最短路径破坏网络算法；文献［3］提出的通过对度数、介数、中心度等指标进行比较，再用博弈论分析节点重要性的方法；文献［4］提出的基于节点度、效率排序方法；文献［5］提出的节点收缩识别法。这些方法对不带权网络的效果较为理想，但在航空网络中，由于未考虑航线流量这一反映机场与航线地位作用的重要指标，所得结论往往会与实际不符。二是方法单一片面，通常只考虑节点的某一性质。如文献［6］提出的基于加权聚类系数的节点重要度排序方法；文献［7］提出的基于度中心性的节点关键性测度法；文献［8］提出的基于邻居节点度的网络节点识别方法。这些方法简单且效率高，但机场节点的重要性影响因素复杂多样，仅考虑个别性质往往难以取得准确的结论。基于以往方法的不足，运用改进的带权接近度算法［9］，并参考重要度评价矩阵［10］，提出一种新型的航空网络关键节点识别算法。接近度算法反映节点在网络中的位置信息，但难以区分距离相近的节点，因此，设置带权函数，增强对节点的辨识力；重要度评价矩阵体现了节点在网络运输中所起的作用以及相邻节点的重要度贡献，但未涉及航线流量即边权，因此对其作出改进，将节点边权作为评价指标。该算法弥补了传统方法的缺陷，既考虑到节点的位置信息，又能够结合航线流量考虑节点对网络的影响，对于全面准确识别关键节点具有一定可行性。

1 基本理论

假设存在一个无向无自环的联通复杂网络G=（V，L），其中，V={v1，v2，…，vn}为网络节点集合，E={e1，e2，…，em}为网络中边的集合。用A=（aij）n×n表示G的边权矩阵，用wij表示节点vi和节点vj之间边eij的权值，当节点vi和节点vj存在边eij时，aij=wij，否则aij=0。

最短路径是指从节点v到v′存在路径 P=（v1，v2，…，vn）（当 v1=v，vn=v′时）使得最小。从一个机场到指定机场需要中转最少次数的路径称为航空网络的最短路径，这个路径上的边ei的数量为最短距离。

节点接近度是指节点v对局部社区C的接近程度。机场节点接近度反映了机场在某一区域航空网络中的相对位置，以及机场对整个航空网络的影响。

2 关键节点识别模型构建

2.1 航空网络模型假定

通过网页爬取得到全国航班数据，将两两之间有航班的机场连线，得到中国航空网络示意图，如图1所示。

图1 中国航空网络图（港、澳、台除外）

考虑到航空数据的特性和达到简化计算过程的目的，对实际航空系统作如下假定：

①拓扑模型中的节点vi表示全国所有具有运输能力的通用机场，确定为集合 V={v1，v2，…，vn}，其数量为N=|V|。②边ej表示机场与机场之间的运输关系即航空线路。若两机场存在航线，则认为有边相连，否则无边。两个机场之间最多存在一条边相连，且无向。集合 E={e1，e2，…，eM}为边的集合，其数量为M=|E|。③假定航线的拓扑特性相同，即不考虑传输效率和传输线特性的不同，将航线流量作为网络中的边权。

2.2 带权重的接近度计算

航空网络节点的位置与其重要程度有着紧密的联系，节点越趋向于网络中心，它是关键节点的可能性就越大；节点越趋向网络边缘，它的重要性程度就越低。接近度可以衡量航空网络中从指定节点到达任意节点的难易程度，即反映节点的位置及其与剩余节点的距离，从而对航空网络节点进行关键性评估。传统的接近度可由式（1）计算：

CLi表示节点i与其他节点距离和的倒数，N表示网络中机场数量，dij表示机场i到机场j的最少中转次数。

图2 某一区域航空网络两种方法识别效果对比

然而传统的接近度算法不能针对不同网络特性进行相应的调整，只能不加区别地将某一节点与剩余节点的最短距离简单相加。而我国航空网络节点间的最短距离dij非常相近，最大值均不超过3，因此，这种接近度算法的识别效果并不明显。

针对我国航空网络的特点，提出用带权的接近度算法来突出节点之间的路径距离对识别结果的影响。于是，在这里为最短路径设置一个权重函数f（x），改进的接近度计算公式如下：

其中，f（dij）为对数函数，当dij在较小范围内变化时，f（dij）变化较大；当dij增大到一定程度时，f（dij）变化会越来越小。这样做是为了增加相邻航空网络节点对其接近度的影响，减小距离远的节点的影响。

2.3 评价矩阵确立

在识别航空网络关键节点的过程中，除了考虑机场节点位置的重要性，还要考虑途径机场节点的航线流量，即边权。重要度评价矩阵能充分结合机场节点位置和航班流量，反映实际航空网络中机场相对其他机场的重要度，以及机场对整个交通运行的影响程度。在重要度评价矩阵中，用度来构成节点间的重要度关联，用边权和接近度作为评价参数。

在上一节的航空网络模型中，节点数量为N=|V|，设机场节点vi的度为Di。其中，a为航空网络的邻接矩阵。按照自身重要度的Di/k2为比例，vi对其每一个相邻节点输出重要度。计算所有节点v1，v2，…，vn对其相邻节点的输出重要度比例值，于是得到相邻节点重要度输出矩阵，记为HIC：

矩阵中，δij为贡献分配参数，若两个节点相连则取值为1，否则取值为0；对角线上的元素为1，意味着节点对节点自身的贡献输出比例为1。k为节点平均度，

为了能够体现机场节点在航线网络运输过程中所起的作用，结合航班流量，计算每个机场节点的权 Si，即：

其中Ni是节点i的邻居节点集，wij是与节点i直接相连边的权重。权值越大，说明该机场节点与周围机场联系越紧密。

融合节点的接近度值，并用节点的重要度贡献值来代替HIC的重要度贡献比例值，就可以得到节点重要度评价矩阵HE：

式中，HEij表示节点j对节点i的重要度贡献值。可以看出，一个机场节点对其相邻机场的重要度贡献值与节点接近度、度和途经航线的流量有关。节点的接近度值越高、度值越高、航线流量越大，则它对相邻节点的重要度贡献越大。

2.4 重要度计算

机场节点重要度计算从两方面进行，一方面是接近度，另一方面是边权。接近度作为识别航空网络节点的一种方法，能够判定机场位置对其重要性程度的影响。这里采用对数函数进行加权，放大了邻近节点的影响，对实际航空网络更具有针对性。边权的设置考虑了航线流量，比以往方法更能贴近实际。为了融合这两方面的优势，使节点识别算法既准确又高效，定义节点i的重要度Ci：

式中，Ci表示所有与机场i相邻的机场对其重要度贡献的求和，即文中要计算的最终排序重要度值。

2.5 识别算法步骤

下面给出评估节点重要度的算法流程：

输入：复杂网络邻接矩阵A=（aij）n×n，边权wi输出：节点i的重要度Ci以及排序如下页图3流程图所示，算法的几个主要步骤为：1）用Floyd算法［11］计算所有节点对之间的最短距离矩阵Dis=［dij］；2）计算每个节点的接近度（初始值为0）；3）计算节点关键性贡献矩阵HIC；4）确定关键性评价矩阵HE；5）计算每个节点的重要度。

3 仿真实验

3.1 算法验证

为了验证算法的有效性，这里采用随机生成网络，对边进行赋权，作为关键节点识别算例，下页图4为网络拓扑图。运用文章提出的识别算法，得到重要度结果，并与传统方法作比较，如表1。

图3 关键节点识别算法流程图

图4 随机生成加权网络拓扑

从3种方法的排序结果可以看出，本算法得到的区分效果明显优于另外两种方法。以节点2、节点3为例，节点在网络中地位相近，但边权相差较大，用接近度算法和重要度评价矩阵算法得到的结果相似度很高，而本算法能很好地体现边权差异，得到的结果表明2号节点的重要度明显高于3号节点。以节点3、节点12为例，经过两节点的流量相近，但12号节点更接近网络中心，本算法得到的结果反映了这种差异，而另外两种方法效果则不明显。

表1 网络节点重要度及排序

3.2 算法应用

在实验中，对2016年5月全国199个通航机场一周内飞行班次进行统计。如表2，得到关于机场与机场之间航班数矩阵M=（aij）199×199，这里只取前6个城市。当机场i与机场j之间航班数不等于0时，aij取值为1，否则取0，从而得到关于中国航空网络的邻接矩阵A=（aij）n×n。

根据算法模型，输入邻接矩阵A=（aij）n×n，根据佛洛依德算法得到机场节点之间的最短距离矩阵Dis=［dij］，根据式（6）得到各个节点的重要度 Ci以及排序如下页表3。

根据关键节点识别算法得到的各个城市机场节点，得到以下结论：

表2 飞行班次统计（周）

①北京、上海、广州的重要度Ci分别为2.07556，2.025 213，1.340 661，位列前三，与现实符合，验证了算法的准确性。②西安排在了第4，它是中国地理位置的中心，是贯通东西的交通枢纽，相比用节点度排序时西安排在第6，算法得到的结果更具合理性，表明算法充分考虑了节点的位置信息。③紧接着的还有成都、昆明、重庆、深圳等城市，这些城市都是区域的中心，说明算法对这些网络局部影响较大的节点具有较强的识别能力。④排在最后几位的安康、阿拉善右旗等城市，大多地处几何边缘地带，且航空流量小，再次说明算法能够准确判断它们的

表3 节点重要度及排序

位置信息和边权信息。

4 结论

通过改进接近度算法与重要度评价矩阵对我国航空网络进行了关键节点识别。仿真实验证明，提出的算法对不同节点的识别区分度比较明显，改进了传统方法的不足，能够结合航线流量和机场位置较全面地反映各个机场节点的重要性，对于重点机场节点目标保障具有重要意义。下一步的研究重点是国内外的军民航机场关键节点识别。

［1］郑金连，狄增加.复杂网络研究与复杂现象［J］.系统辩证学学报，2005，13（4）：8-13.

［2］CORLEY H W，SHA D Y.Most vital links and nodes in weighted networks［J］.Operation Research Letters，1982，1（4）：157-160.

［3］GOMEZB D，ENRIQUE G A.Centrality and power in social networks：a game theoretic approach［J］.Mathematical Social Sciences，2003，46（1）：27-54.

［4］HE N，LI D Y，GAN W Y，et al.Mining vital nodes in complex networks［J］.Computer Science，2007，34（12）：1-5.

［5］谭跃进，吴俊，邓宏钟.复杂网络中节点重要度评估的节点收缩方法［J］.系统工程理论与实践，2006，26（11）：79-83.

［6］谢凤宏，张大为，黄丹，等.基于加权复杂网络的文本关键 词 提 取 ［J］. 系 统 科 学 与 数 学 ，2010，30（11）：1592-1596.

［7］CHEN D B，LYU L，SHANG M S.Identifying influential nodes in complex networks［J］.Physica A，2012，391（4）：1777-1787.

［8］王建伟，荣莉莉，郭天柱.一种基于局部特征的网络节点重要性度量方法［J］. 大连理工大学学报，2010，50（5）：822-826.

［9］方平，李芝棠，涂浩，等.复杂网络局部社区挖掘的节点接近度算法 ［J］. 计算机工程与应用，2013，49（17）：38-42.

［10］傅子昊，孙磊，林振智，等.基于节点重要度评价矩阵的网络重构双层优化策略［J］.电力自动化设备，2016，36（5）：37-42.

［11］苏竞秀，龙陈锋.Floyd算法与RAD算法性能分析［J］.计算机应用与软件，2015，32（2）：116-119.

［12］司晓静.复杂网络中节点重要性排序的研究［D］.西安：西安电子科技大学，2012.

［13］周旋，张凤鸣，李克武.利用重要度评价矩阵确定复杂网络关键节点［J］.物理学报，2012，61（5）：11-16.

Identification of Key Airport Nodes Based on Closeness Sorting Algorithm and Evaluation Matrix

TU Cong-liang，WU Ming-gong，WEN Xiang-xi
（School of Air Traffic Control and Navigation，Air Force Engineering University，Xi’an 710051，China）

A key airport recognition algorithm is proposed according to the characteristics of China’s aviation network.Due to the incomprehensiveness and neglect of traffic flow of previous methods，the proposed algorithm combines importance evaluation matrix and closeness sorting algorithm.On the basis of the air network model，the distance weight function is set up and the closeness sorting algorithm is used to reflect the position of the airport.Then the closeness sorting algorithm and evaluation matrix are integrated，and the evaluation matrix is constructed considering edge weight which is air traffic flow in reality，meantime，the importance degree of each airport is calculated.As the results show，this algorithm is capable of employing air traffic flow as well as other properties of China’s aviation network，and reflects the importance of each airport accurately.

aviation network，key nodes，closeness degree，evaluation matrix

1002-0640（2017）10-0172-05

V37；TP393

A

10.3969/j.issn.1002-0640.2017.10.036

2016-08-05

2016-09-07

国家空管科研基金资助项目（GKG201410001）

涂从良（1991- ），男，浙江湖州人，硕士。研究方向：空域规划与安全管理。