支线航空网络节点的聚类与关键节点识别*

何 行 刘旺根 何 珊 赵振涵

（中国民用航空飞行学院 广汉 618300）

1 引言

支线航空是全国航线网络的重要组成部分［1］，对民航强国的建设有至关重要的作用，但支线航空也是长期困扰我国航空运输业发展的一个话题。1988年和2000年分别提出小世界网络和无标度网络广泛存在于现实世界，随着复杂网络特性的研究深入，节点重要度评价、节点聚类研究逐渐成为复杂网络中的重要课题。

关键节点识别方法一般以复杂网络本身属性如度、介数、接近度、聚集系数等量化测度标准来评价网络节点［2～4］。也有多指标融合评价，王锋在文献［5］中针对无权网络，提出一种基于m 节邻居节点的关键节点识别算法，综合考虑了节点自身以及其m 阶邻接节点的度值以及介值重要度的贡献程度。邓红星等［6］选用节点度和站点客流集散量等7个指标构建节点重要度评价体系，对哈尔滨市区道路网进行研究。ZHU Yanbo 等［7］以图论为基础对丝绸之路经济带铁路网络节点重要度进行研究，利用pajek 软件仿真发现了其中3 个最关键节点。王超峰［8］认为节点重要度与机场本身交通经济特性密切相关，并建立指标体系进行节点重要性评估。

聚类是机器学习领域中无监督学习的重要组成部分，聚类算法在工业界有重要的应用价值，在学术界也得到了广泛的关注和研究［9］。常见的聚类分析方法有层次法、划分法、基于网格法、基于密度法和基于模型法。本文采取DBSCAN聚类算法，DBSCAN 算法是一种经典的基于密度的聚类算法，最早是在《Science》期刊发表提出。DBSCAN 算法不需要预先指定聚类的簇数，能够在含有噪声的数据集中发现任意数量和形状的簇［10］，具有可解释强、可视化效果好、易于理解的优点。

目前的航空网络性能研究都是基于复杂网络拓扑结构展开的，对关键节点选取比较简单，缺少完善的指标体系，且网络性能的分析采用的指标比较单一。实际上，机场网络节点的重要度还与机场及其所在地区属性有关，综合考虑多层指标使评估节点重要度变得合理化。

2 研究理论与依据

2.1 构建支线航空网络模型

本文将年旅客吞吐量少于200 万人次的机场定义为支线机场，而一端连接支线机场的航线定位为支线航线，所有支线航线组成支线航空网络［11］。图中共有节点数161 个，有2290 条边，节点表示支线机场，连边为两个支线机场间有航线。利用Gephi 可视化软件，绘制无向支线航空网络图，如图1所示。

图1 支线航空网络图（2020年数据）

2.2 机场节点重要度评估指标

机场关键节点的识别，对支线航空网络的网络性能分析十分重要。为建立完善的机场节点重要度指标体系，选取的指标应具有全面性、合理性，不仅要反应复杂网络拓扑性质、还要与机场、机场所在地区属性结合，故选取指标如表1。

表1 节点重要度指标体系

其中，V1节点度的计算公式：

i，j 表示节点，aij表示邻接矩阵变量，ki表示度

点介数的计算公式

G 表示网络，Dij(i)为经过节点i最短路径的数量，Dkj便是节点k，j间最短路径的数量。

2.3 指标数据来源

本文U1 指标已计算完毕，机场名采用四字代码，数据来源于中国民用航空局预先飞行计划管理系统，选择2020年中国夏秋航季国内航班计划表，具体包括161 个机场节点的2148 个航段数据。U2吞吐量指标数据来源于《从统计看民航》、设施可用性是对机场等设施综合评估的结果。U3 指标从国家统计局官网获得。综上，支线航空网络节点重要度指标部分数据汇总如表2。

表2 支线航空节点重要度指标

3 关键节点识别

3.1 熵权TOPSIS法

熵权TOPSIS 法是一种基于熵值法改进TOPSIS 法模型的赋权方法，能够根据各指标值得变异程度所反映的信息量来确定权重［12］，并可通过评价对象和正、负理想解间的差异值来计算其与最优解的贴近度。

正向指标：

其中，i 表示年份，j 表示指标，i，j 均为非零的自然数。

第二步：指标归一化处理，计算第i个指标在第j年的比重。

第三步：计算指标的信息熵ej：

第四步：计算各个指标的差异系数gj与指标权重wj：

第五步：构造加权规范化决策矩阵Vij，Vij=WjZij，Z=(Zij)m×n。

第六步：确定理想解和负理想解。决策矩阵V中元素Vij值越大表示方案越好。

理想解：

负理想解：

第七步：计算每个节点到理想解的距离Si+和到负理想解的距离Si-。

第八步：计算每个节点的相对接近度并排序，ci的值越大，表示节点越重要。

3.2 综合评价结果

采用熵权TOPSIS 综合评价法计算上述161 个节点，6 个二级指标的熵权分别是0.129323，0.294931，0.113405，0.255894，0.131915，0.156294。依据Ci 值大小进行排序，前三位分别是ZSLG、ZPDL、ZULZ 机场。选取前二十四名为关键节点，具体排序情况见表3。

表3 关键节点排序结果

4 节点聚类

4.1 DBSCAN算法

DBSCAN 是一种典型的以数据密度为基准划分类的聚类方法的代表，可以在不需要设定初始值便可有效地自动发现目标簇个数，有效发现不同形状的簇。给定一个样本集是D＝（x1，x2，…，xm），参数（ε，Minpts）用来描述邻域的样本分布紧密程度。其中，ε 描述了某一样本的邻域距离阈值，Minpts 描述了某一样本的距离为ε 的邻域中样本个数的阈值［13～14］。DBSCAN 算法的聚类过程可以表示为

输入：E——半径

MinPts——给定点在E 邻域内成为核心对象的最小邻域点数。

D——集合

输出：目标类簇集合

方法：

1）判断输入点是否为核心对象；

2）找出核心对象的E 邻域中的所有直接密度可达点；

3）Until 所有输入点都判断完毕。

4.2 基于DBSCAN算法的节点簇划分

基于DBSCAN聚类的实现过程，设定关键参数Eps 和Minpts。从聚类数据样本集X 中任意选取一点p，若该点的条件符合核心对象的判定，那么从该点密度可达的所有数据点成为一个聚类，而不属于任何簇的数据点则被标记为噪声点［15］。

图2分别给出了不同Eps和Minpts组合时其聚合效果。通过对比，可以看到Minpts=10仅有一类，Minpts=8 聚类的精度较差仅有两类，Minpts=5 时聚类噪声点较多，Minpts=3聚类结果精度较高。通过观察不同Minpts值的聚类结果，噪声点的数目代表了精度的高低，因此，本文在DBSCAN 算法中选取的关键参数为Eps=0.15，Minpts=3。

图2 DBSCAN簇分类结果

聚类结果如表4，算法将节点分为了4 个簇。第一簇中有8 个机场，分别是洛阳、大理、泸州、常德、茅台、舟山、赤峰、阜阳，与熵权TOPSIS 法计算出的排名基本一致，证明算法的准确性。

表4 最终聚类结果

5 结语

基于图论和复杂网络理论，以2020年夏秋航季国内航班正班计划数据为基础，构建支线航空网络，从复杂网络的拓扑特性、机场属性和地区属性3 个方面选取了6 个不同的指标，较为客观地完成了机场重要度的评估，使用熵权-Topsis 法完成关键节点的识别，发现了连云港、大理、泸州、宜宾等24个节点为重要机场，DBSCAN算法完成节点的聚类，分为4 种不同类别的机场，两种方法的结果几乎一致，由于疫情原因，支线机场之间差异性更小，分类结果符合现实情况。对关键节点进行保护，从而维护支线机场网络体系的有效运行。