Identification Method for Key Nodes in En-Route Network
-
摘要:
有效辨识关键节点对增强网络韧性、提高运行能力具有重要意义,为提高航路网络关键节点识别的准确性,提出基于TOPSIS (technique for order preference by similarity to an ideal solution)-灰色关联分析法的综合评价方法和航路网络节点分级方法. 首先,从复杂网络统计特性、交通流量特性、脆弱性3个方面构建航路网络关键节点评价指标体系;通过引入相对熵改进逼近理想值排序法,并结合灰色关联分析法综合评价航路点重要程度,采用基于K-means聚类方法有效划分航路节点等级;最后,以民航空管实际运行数据为实例,开展关键节点识别. 研究表明:相较于单一指标,所建航路网络节点评价指标体系获得的评价结果更加全面;改进TOPSIS-灰色关联分析方法相较于传统TOPSIS法评价结果更加准确;所提识别方法发现了我国华东地区典型繁忙航路网络中有29个关键节点,其在网络结构及交通流量方面具有关键作用.
Abstract:Accurate identification of key nodes is of great significance for enhancing network resilience and improving operational capabilities. In order to improve the identification accuracy of key nodes in the en-route network, a comprehensive evaluation method based on the technique for order preference by similarity to an ideal solution (TOPSIS)-grey correlation analysis method and a node classification method for the en-route network were proposed. Firstly, an evaluation index system of key nodes in the en-route network was constructed from three perspectives: complex network characteristics, traffic volume, and vulnerability. Then, the relative entropy was introduced to improve the TOPSIS method, and the importance of en-route waypoints was comprehensively evaluated by combining this method with the grey correlation analysis method. The K-means clustering method was used to effectively divide the levels of en-route waypoints. Finally, key node identification was carried out based on the actual operation data of civil air traffic management. It finds that the results obtained by the constructed evaluation index system of key nodes in the en-route network are more comprehensive than the evaluation results of a single index. The improved TOPSIS-grey correlation analysis is more accurate than the traditional TOPSIS method. The proposed identification method finds that there are 29 key nodes in the typical busy en-route network in Eastern China, which play a key role in the network structure and traffic volume.
-
Key words:
- complex networks /
- TOPSIS /
- relative entropy /
- grey relational degree /
- K-means clustering
-
航路网络作为一种典型的复杂网络,由航段和航路点构成,其作用等效于复杂网络中的边和节点. 其中,航路点特征不同,对航路网络的影响力也不同;对航路网络影响程度更大、范围更广的航路点,则重要程度更大,可视为关键节点. 若此类关键节点发生拥堵,其本身所具有的通行能力便会降低,甚至丧失,并波及周围航路点,造成航路网络级联失效,影响航路网络的整体运行效率. 通过排序分析航路网络中各航路点的影响程度,识别关键节点,是复杂网络理论应用于航路网络领域的研究重点. 识别并加强航路网络中关键节点的保护,重点管理“薄弱环节”,防止个别关键节点崩溃,避免航路网络整体运行效率损失,以增强航路网络韧性,并为航路资源优化分配提供参考依据.
针对航路网络关键节点的识别问题,现有研究主要聚焦于两方面. 一种是基于“中心性”特征识别关键节点,主要通过构建不同测算方式下的航路点中心性特征指标,量化排序并提取其中的关键节点. 初期以基于网络局部属性的度中心性、基于网络全局属性的特征向量中心性/接近中心性/介数中心性、基于网络位置属性的K-shell中心性和基于随机游走的PageRank中心性[1-9]等传统指标测算为主. 在此基础上持续改进,基于K-shell的核心度中心性指标(coreness centrality)[10]、基于节点及其邻居节点中心性的邻域中心性指标[11]、基于Katz中心性的旅行中心性指标[12]等指标测算方法相继提出. 然而,此类指标测算方式大都基于航路网络的局部信息,在关键节点识别过程中也以单一指标为主. 因此,又有研究面向航路网络运行全局,综合航路点自身属性及其在航路网络中的全局中心性指标,提出全局结构模型(global structure model, GSM),但计算较复杂. 为简化求解,在GSM基础上融合度与最短路径长度等指标,重新定义了航路点的全局影响(global influence),提出局部和全局中心性 (local and global centrality) 衡量算法,降低了计算复杂度,并提高了识别关键节点的准确度[13-14]. 另一种是基于“破坏性”特征识别关键节点,主要通过分析删除航路点后的网络性能指标变化来提取其中的关键节点. 通常将网络效率、平均聚类系数、最大连通子图等[15-21]性能指标与前述的度、介数等中心性指标相结合,量化排序后依次删除对应的航路点,进而实现对航路网络的隔断[22-23]. 同时,也可采用改进后的指标进行排序删除和隔断分析,如基于网络结构的子图效率[24]、加权航空运输网络效率指标[25]、基于节点移除的网络拉普拉斯能量变化率指标[26]等. 但上述研究仍以局部航路网络结构为主,当删除航路点形成互不连通的分支时,评价指标较难准确反映各分支的差异,也较难精细表征航路网络的实际运行状态. 针对该问题,有研究结合复杂网络的拓扑结构和攻击成本,提出一种基于逼近理想解排序法(technique for order preference by similarity to an ideal solution,TOPSIS)的节点重要程度综合评价方法[27],其更适用于航路网络节点的实际评价.
综上可以看出,在航空领域的关键节点识别方面,多采用K-shell、中心性等拓扑结构指标或节点删除的方法,但角度较为单一,未全方位将节点的属性纳入考量范围,无法较为准确地识别出关键节点. 此外,关键节点识别的指标体系仍不够全面,缺少对航路点容量及流量信息的结合,同时鲜有研究综合考虑航路点中心性和破坏性指标. 总结已有研究成果,本文综合“中心性”特征(复杂网络特性指标),“破坏性”特征(脆弱性指标),以及节点实际运行情况(交通流量特性指标)等建立航路网络关键节点的评价指标体系,基于此评价指标体系提出基于TOPSIS-灰色关联分析法的综合评价方法和航路网络节点分级方法,以更全面准确地对航路点进行评价. 结合华东区域航路网络运行数据开展实例分析,试验结果表明,所提指标和方法能够有效识别航路网络关键节点,为后续管控航路薄弱环节与合理配置资源提供一种科学的论证方法参考.
1. 航路网络关键节点评价指标体系
航路网络中的航路点较多,可能出现多个航路点单一指标测算结果相同,进而难以区分其重要程度. 因此,为使评估结果更加全面,分别从复杂网络特性、交通流量特性、脆弱性3个角度提取航路点特征,构建评价指标,以评估航路点在航路网络中的重要程度.
航路网络属于一种复杂网络,现实中的复杂网络通常使用图论方式的进行描述,可表示为G=(V,E),其中:V={v1,v2,⋯,vN}为网络中所包含节点的集合,N为节点数量;E={e1,e2,⋯,eM}为网络中所包含连边的集合,M为网络中连边数量. 网络中节点的连接关系可以通过邻接矩阵A进行存储,A=(ai,l),若节点vi与vl之间存在连边,则ai,l=1,反之ai,l=0.
如图1所示,为包含7个节点的网络,其邻接矩阵如式(1)所示.
{\boldsymbol{A}} = \left[ {\begin{array}{*{20}{c}} 0& 1& 1& 1& 0& 0& 0\\ 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 0& 0& 0& 0& 1\\ 1& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 1& 1& 0& 0& 0& 0 \end{array}} \right]. (1) 1.1 复杂网络特性指标
1) 度
航路点度值是对航路点连接属性最为关键的描述,通常与航路点的重要程度呈正相关. 如果航路点 {v_i} 与 {k_i} 个航路点直接相连,则存在 {k_i} 条航段,那么该航路点的度就为 {k_i} ,如式(2)所示.
k_i=\sum\limits_{l=1}^Na_{i,l},\quad i\ne l. (2) 2) 介数
在同一航路网络中,2个不相邻航路点之间进行连通必须要经过连接这2个航路点路径上的中间点. 介数主要是衡量航路网络中2个节点通过最短路径连通时经过某节点的可能性,航路点的介数越大,意味着途经该点的最短路径越多,承担的连通信息总量越多,则该航路点在网络中更重要,航路点介数B_i 可表示为
B_i=\sum\limits_{l,k}^{ }\frac{l_{l,k,i}}{l_{l,k}},\quad i\ne l\ne k, (3) 式中: l_{l,k} 为航路点{v_l}和航路点{v_k}之间最短路径的条数,{l_{l,k,i}}为航路点{v_l}和航路点{v_k}之间经过航路点v_i的最短路径条数.
3) 接近中心性
接近中心性侧重于从信息传递所需的距离(即航路点在航路网络中的位置)来衡量航路点的重要程度. 航路点距离其他航路点越近,该航路点就能与其他航路点进行更高效率的信息交互,其重要程度就越高,因此,接近中心性与该航路点到航路网络中心位置的距离呈负相关关系,表示为航路点{v_i}到其他航路点的平均最短距离的倒数. 接近中心性C_{{\rm{C}}_i} 的计算式为
C_{{\rm{C}}_i}=\frac{N-1}{\displaystyle\sum\limits_{l=1}^{N-1}d_{i,l}},\quad i\ne l, (4) 式中: d_{i,l} 为航路点{v_i}到航路点{v_l}的最短路径所包含的边数.
C_{{\rm{C}}_i} 越大,航路点i越靠近网络中心,则该航路点越重要.
4) 特征向量中心性
特征向量中心性侧重于邻居航路点的重要程度对该航路点的影响. 该指标为网络邻接矩阵最大特征值对应的特征向量,强调航路点重要程度与邻居航路点的重要程度呈线性关系,从而建立一个线性方程组. 解得此方程组的最大特征值,并求得其对应的特征向量中的各分量值,就可得到航路点的特征向量中心性. 假设 \lambda 为航路网络邻接矩阵A的最大特征值,其对应的最大特征向量 {\boldsymbol{x}} = {\left[ {{x_1}\;{x_2}\; \cdots \;{x_N}} \right]^{\rm T}} ,则有
\lambda {x_i} = \sum\limits_{l = 1}^N {{a_{i,l}}{x_l}}. (5) 航路点 {v_i} 的特征向量中心性E_{{\rm{C}}_i}表示为
E_{{\rm{C}}_i}=\frac{1}{\lambda}\sum\limits_{j=1}^Na_{i,l}x_l. (6) 可以看出,特征向量中心性的大小与其邻居航路点有关,邻居航路点的数量越多,则越重要,该航路点的特征向量中心性越大.
1.2 交通流量特性指标
航路网络承载着航班流的运行,相关运行指标是其运行特征的重要表征形式,主要关注航路点所经流量总体状况与高峰时段状况. 在此,选取民航空管系统惯常使用的小时平均流量、高峰小时流量和高峰时长指标.
1) 小时平均流量\overline P_i
航路点流量的总体概括性指标,统计各航路点小时流量,得到各航路点的小时平均流量,即
\overline P_i = \frac{{\displaystyle\sum\limits_{t = 1}^{24} {{p_{i,t}}} }}{{24}}, (7) 式中: {p_{i,t}} 为航路点 {v_i} 在时刻t的流量.
2) 高峰小时流量{P_{\max ,i}}
各航路点各小时的流量都不相同,存在较高的小时流量. 取一天里流量最高的小时流量作为航路点 {v_i} 的高峰小时流量,即
{P_{\max ,i}} = \max \;{p_{i,t}}. (8) 3) 高峰时长{T_{{\rm{peak}},i}}
航路网络中部分航路点较长时段处于流量高位,高峰时长为航路点{v_i}的小时流量大于流量阈值 \sqrt {\overline P_i {P_{\max ,i}}} 的时长,即
{T_{{\rm{peak}},i}} = \sum {f(t)}, (9) f(t) = \left\{ \begin{gathered} 1,\;\;{p_{i,t}} \geqslant \sqrt[{}]{{\overline P_i {P_{\max ,i}}}}, \\ 0,\;\;{p_{i,t}} < \sqrt[{}]{{\overline P_i {P_{\max ,i}}}}. \\ \end{gathered} \right. (10) 1.3 脆弱性指标
上述指标可在不破坏航路网络结构的前提下分析各航路点在网络中的重要性. 此外,还可基于航路点删除的破坏性识别,对其重要程度进行评价. 在此选取最大子图损失率、网络效率损失率以及节点效率损失率3个指标.
1) 最大子图损失率{S_i}
采用航路点{v_i}删除后网络的S_i 衡量航路点{v_i}的重要程度指标, {S_i} 越大,意味着航路点vi在网络中的重要程度越高,可表示为
{S_i} = \frac{{N - {N_i}}}{N}, (11) 式中: {N_i} 为航路点 {v_i} 删除后最大连通子图中的航路点总数.
2) 网络效率损失率
网络效率用于衡量航路网络结构的变化对最短距离的影响,反映网络的通行能力和连通性能,可表示为航路点之间最短距离倒数和的平均数,即
E=\frac{1}{N(N-1)}\sum\limits_{i\ne l}^{ }\frac{1}{d_{i,l}}, (12) 式中:E为网络初始效率.
若航路点之间不存在连边,则 d_{i,j}=\infty , 1/d_{i,j}=0 ,因此 E 的取值范围为 [0,1] ,符合通常认为的航路点间距离越近,信息就越容易传播,其传输效率也就越高.
采用航路点 {v_i} 删除后的网络效率损失率衡量航路点 {v_i} 的重要程度,可以表示为
E_{{\rm{r}},i} = \frac{{E - {E_i}}}{E}, (13) 式中: {E_i} 为删除航路点 {v_i} 及其连边后剩余的网络效率; E_{{\rm{r}},i} 为航路点 {v_i} 的重要程度值,指标越大,对应航路点越重要.
3) 运行效率损失率
运行效率损失率反映在级联失效过程中一个航路点移除对网络运行效率的影响. 定义一个 N \times 1 的矩阵D,其中的元素为各航路点此时的运行效率. 当航路点的负载小于其容量时,航路点正常运行,此时的效率为1. 航路点的负载大于其临界容量时,航路点无法工作,此时效率为0. 航路点处于过载状态时,随着负载的增加,运行效率也逐渐降低. 航路点效率可表示为
{\eta _{l,t}} = \left\{ \begin{gathered} 1,\quad{L_{l,t}} < {C_l}, \\ \frac{{(1 + \delta L_{0,l}/ L ){C_l} - {L_{l,t}}}}{{(\delta L_{0,l}/ L ){C_l}}}, \\ \quad {C_l} \leqslant {L_{l,t}} < (1 + \delta L_{0,l}/ L ){C_l}, \\ 0,\quad(1 + \delta L_{0,l}/ L ){C_l} \leqslant {L_{l,t}}, \\ \end{gathered} \right. (14) L = \frac{1}{N}\sum\limits_{l = 1}^N {L_{0,l}}, (15) 式中:{L_{l,t}}为航路点 {v_l} 在时刻t的实时负载, L_{0,l} 为航路点 v_l 的初始负载,L为平均初始负载, {C_l} 为航路点 v_l 的容量, \delta 为过载系数, \eta_{l,t} 为航路点 {v_l} 在时刻t的效率.
通过效率损失率 {V_i} 评价脆弱性,表示级联结束后整个网络中因航路点{v_i}的移除所造成的航路点效率损失率,如式(16)所示.
{V_i} = \frac{{N - \displaystyle\sum\limits {{\eta _l}} }}{N}, (16) 式中: {\eta _l} 为网络最大连通子图 \mathit{\Phi} 中航路点 v_l 的效率.
2. 航路网络关键节点识别方法
对一个复杂系统进行评价,综合评价法是一种有效且全面的方法. 常见的综合评价法有模糊综合评价法、TOPSIS法、层次分析法、多元统计分析法、灰色系统评价法等. TOPSIS法用于比较评价对象与正负理想解之间的距离远近,并进行评估排序,但仅考虑了单一的距离因素,没有考虑方案之间各指标因素曲线形状的变化态势. 灰色关联分析法能通过少量信息对评价对象的指标变化及与正负理想解之间的区别进行较好的描述,并且不需要明确各指标的概率分布及相互之间的关联关系. 熵权法根据指标数据本身所蕴含的信息量来确定指标权重,熵值越小,指标所能提供的有序信息越多,其权重相应越大. 本文综合考虑距离和曲线的变化态势,并引入熵权法,构造一种基于TOPSIS-灰色关联分析的综合评价方法,得到各航路点的重要程度综合量化结果,并通过聚类方式划分航路点重要程度等级,进而更加直观地得到航路网络中的重要航路点,以便对其进行管理.
2.1 基于TOPSIS-灰色关联分析的关键节点重要程度评价方法
基于TOPSIS-灰色关联分析的航路网络节点重要程度评价流程如图2所示.
步骤1 构建初始决策矩阵. 假设航路网络中包含有N个航路点,各航路点有m个评价指标,构造初始决策矩阵{\boldsymbol{X}}.
{\boldsymbol{X}} = \left[ {\begin{array}{*{20}{c}} {{x_{11}}}&{{x_{12}}}& \cdots &{{x_{1m}}} \\ {{x_{21}}}&{{x_{22}}}& \cdots &{{x_{2m}}} \\ \vdots & \vdots & & \vdots \\ {{x_{N1}}}&{{x_{N2}}}& \cdots &{{x_{Nm}}} \end{array}} \right], (17) 式中: {x_{ij}} 为第i个航路点vi的第j个评价指标的原始数值.
步骤2 规范化决策矩阵. 为避免关键节点评价指标的量纲、量级各异形成误差,对{\boldsymbol{X}}进行规范化处理. 效益性指标为数值越大越好的指标,成本型指标为数值越小越好的指标. 首先对各指标进行区分,判断其为效益型还是成本型.
效益型指标的规范化计算式为
{{\textit{z}}}_{ij}=\frac{{x}_{ij}-{x}_{\mathrm{min},j}}{{x}_{\mathrm{max},j}-{x}_{\mathrm{min},j}}\text{,}\quad j=1,2,\cdots ,m, (18) 成本型指标的规范化计算式为
\text{z}_{ij}=\frac{x_{\mathrm{max},j}-x_{ij}}{x_{\mathrm{max},j}-x_{\mathrm{min},j}}, (19) 式中:{{\textit{z}}_{ij}}为标准化后所得各航路点的指标规范化数值, x_{\max,j } = \max \{ \left. {{x_{ij}}} \right|1 \leqslant i \leqslant N\} , x_{\min,j } = \min \{ \left. {{x_{ij}}} \right|1 \leqslant i \leqslant N\} .
在规范化之后,这2类指标都是数值越大,效益越好,且取值范围为[0,1].
步骤3 计算加权规范化矩阵. 根据各项指标对评价结果的贡献程度不同,使用熵权法计算得到权重矩阵 {\boldsymbol{w}} = {[{w_1}\;\;{w_2}\;\; \cdots \;\;{w_j}\;\; \cdots \;\;{w_m}]^{\rm T}} . 其中,各指标数据的信息熵ej为
e_j=-\frac{1}{\ln N}\sum\limits_{i=1}^N p_{ij}\ln\ p_{ij}, (20) 式中:{p_{ij}}为航路点vi对应第j个指标在同类指标中的比重,如式(21).
{p_{ij}} = \frac{{{{\textit{z}}_{ij}} + 0.1}}{{\displaystyle\sum\limits_{i = 1}^N {({{\textit{z}}_{ij}} + 0.1)} }}. (21) 则第 j 个指标的权重为
{w_j} = \frac{{1 - {e_j}}}{{m - \displaystyle\sum\limits_{j = 1}^m {(1 - {e_j})} }}. (22) 将规范化矩阵的第j列与其对应的权重 {w_j} 相乘得到加权归一化矩阵 F = {({f_{ij}})} = {({w_j}{{\textit{z}}_{ij}})} .
步骤4 确定矩阵 F 的正理想解 {U^ + } (式(23))和负理想解 {U^ - } (式(24)).
{U^ + } = \{ u_1^ + ,u_2^ + , \cdots ,u_j^ + , \cdots ,u_m^ + \}, (23) {U^ - } = \{ u_1^ - ,u_2^ - , \cdots ,u_j^ - , \cdots ,u_m^ - \}, (24) 式中: {u}_{j}^{ + }=\underset{i}{\mathrm{max}}{f}_{ij},{u}_{j}^{-}=\underset{i}{\mathrm{min}}{f}_{ij} .
步骤5 计算航路点v_i与正、负理想解之间的相对熵 S_i^ + (式(25))和 S_i^ - (式(26)).
S_i^ + = \sum\limits_{j = 1}^m {\left\{ {u_j^ + \ln \frac{{u_j^ + }}{{{f_{ij}}}} + (1 - u_j^ + )\ln \frac{{1 - u_j^ + }}{{1 - {f_{ij}}}}} \right\}} , (25) S_i^ - = \sum\limits_{j = 1}^m {\left\{ {u_j^ - \ln \frac{{u_j^ - }}{{{f_{ij}}}} + (1 - u_j^ - )\ln \frac{{1 - u_j^ - }}{{1 - {f_{ij}}}}} \right\}}. (26) 步骤6 计算航路点v_i的每个指标与正、负理想解的灰色关联系数 r_{ij}^ + (式(27))和 r_{ij}^ - (式(28)).
r_{ij}^ + = \frac{{\mathop {\min }\limits_m \mathop {\min }\limits_N \left| {u_j^ + - {f_{ij}}} \right| + \xi \mathop {\max }\limits_m \mathop {\max }\limits_N \left| {u_j^ + - {f_{ij}}} \right|}}{{\left| {u_j^ + - {f_{ij}}} \right| + \xi \mathop {\max }\limits_m \mathop {\max }\limits_N \left| {u_j^ + - {f_{ij}}} \right|}}, (27) r_{ij}^ - = \frac{{\mathop {\min }\limits_m \mathop {\min }\limits_N \left| {u_j^ - - {f_{ij}}} \right| + \xi \mathop {\max }\limits_m \mathop {\max }\limits_N \left| {u_j^ - - {f_{ij}}} \right|}}{{\left| {u_j^ - - {f_{ij}}} \right| + \xi \mathop {\max }\limits_m \mathop {\max }\limits_N \left| {u_j^ - - {f_{ij}}} \right|}}, (28) 式中: \xi 为分辨系数, 0 \leqslant \xi \leqslant 1 ,一般取0.5.
将m个指标的灰色关联系数进行累加平均,得到航路点 v_i 与正、负理想解的灰色关联度 R_i^ + (式(29))与 R_i^ - (式(30)).
R_i^ + = \frac{1}{m}\sum\limits_{j = 1}^m {r_{ij}^ + }, (29) R_i^ - = \frac{1}{m}\sum\limits_{j = 1}^m {r_{ij}^ - }. (30) 步骤7 计算航路点v_i与正、负理想解的接近度,如式(31)、(32).
N_i^ + = {\varphi _1}S_i^ - + {\varphi _2}R_i^ +, (31) N_i^ - = {\varphi _1}S_i^ + + {\varphi _2}R_i^ -, (32) 式中: {\varphi _1} 、 {\varphi _2} 分别为决策者对距离和曲线形状的侧重程度,满足 {\varphi _1} + {\varphi _2} = 1 ,一般 {\varphi _1}{\text{ = }}{\varphi _2} = 0.5 ; N_i^ + 、 N_i^ - 分别为航路点v_ i 与正、负理想解的接近程度.
步骤8 计算航路点 v_i 的综合接近度Gi (式(33)).
{G_i} = \frac{{N_i^ + }}{{N_i^ + + N_i^ - }}. (33) 步骤9 根据综合接近度的大小对各航路点的重要程度进行排序.
2.2 基于K-means聚类的航路网络节点分级方法
从空管实际运行出发,期望给管制员或空域管理者在做决策时提供更加直观的实施依据,以及航路点的重要程度评价结果分布,并进行等级划分. 此处,采用基于K-means的聚类方法. 在划分航路点等级时,通过欧氏距离作为衡量指标如式(34)所示.
{d_{iq}} = \sqrt {\sum\limits_{j = 1}^m {{{({X_{ij}} - {C_{qj}})}^2}} }, (34) 式中: {d_{iq}} 为第i个航路点到第 q 个聚类中心的欧氏距离; {X_{ij}} 为第i个航路点的第j个属性; {C_{qj}} 为第 q 个聚类中心的第j个属性.
在进行聚类之前,首先采用组内误差平方和(SSW)指标来确定最佳类别数,e_{\mathrm{SSW}} 表示为各个分组内的组内误差平方和,即
e_{{\mathrm{SSW}}} = \sum\limits_a^{} {\sum\limits_b^{} {{{({X_{{\mathrm{Y}},ab}} - \overline X_a )}^2}} }, (35) 式中:{X_{{\mathrm{Y}},ab}} 为输入分组a的第b个航路点数据样本,\overline X_a 为分组a的航路点样本均值.
当组内误差越小时,聚类效果越好.
3. 算例分析
采用民航华东地区航路网络2019年4月实际运行数据. 对数据进行分析可知,华东地区有302个航路点有航空器经过,剩余41个航路点未有航空器经过,即流量为0. 对每个航路点的流量进行统计,得到整月的平均小时流量,如图3所示. 可以看出,各航路点各时段的流量有所不同,且波动较大.
根据第2节中所构建的评价指标体系,首先计算出华东地区343个航路点(含流量为0的点)的特性指标,即各航路点的原始决策矩阵. 所选指标均为效益型指标,因此,采用式(18)对决策矩阵{\boldsymbol{X}}进行规范化,得到相应的规范化矩阵,部分结果如表1所示,表中第1行为评价指标,其中,Z1,4表示第1个角度(复杂网络特性)的第4个评价指标,即特征向量中心性,其余释义类似.
表 1 华东地区航路点评价指标规范化数值Table 1. Normalized values of evaluation indexes for en-route waypoints in Eastern China航路点序号 Z1,1 Z1,2 Z1,3 Z1,4 Z2,1 Z2,2 Z2,3 Z3,1 Z3,2 Z3,3 1 0.222 0.095 0.610 0.095 0.533 0.354 0.447 0 0.097 0.897 2 0.111 0.018 0.794 0.077 0.000 0.000 0.000 0 0.068 0.831 3 0.444 0.130 0.871 0.130 0.733 0.459 0.505 0 0.134 0.789 4 0.111 0.391 0.691 0.012 0.667 0.078 0.107 0 0.130 0.838 5 0.111 0.114 0.765 0.032 0.333 0.131 0.184 0 0.089 0.835 6 0.111 0.055 0.251 0.005 0.533 0.158 0.175 0.500 0.242 0.869 7 0.111 0.027 0.847 0.086 0.733 0.231 0.243 0 0.085 0.850 8 0.556 0.604 0.924 0.153 0.600 0.208 0.252 0 0.407 0.892 9 0.111 0.103 0.613 0.007 0.200 0.024 0.058 0 0.129 0.811 10 0.111 0.031 0.285 0.000 0.267 0.010 0.029 0 0.061 0.840 再通过熵权法计算各指标权重,如图4所示. 可以看出,特征向量中心性指标权重最大,取值为0.154;运行效率损失率指标权重最小,取值为0.023;且3个角度的指标总权重分别为0.445、0.320、0.235,说明仅从数据本身来说,航路网络本身的结构特性占主导地位,其余2个角度作为其补充,从而评判航路点的重要程度. 同时,根据所得结果,权重较大的是特征向量中心性和介数这2个复杂网络特性指标,其次是高峰小时流量和最大子图损失率等交通流量特性指标和脆弱性指标. 根据已有研究[28-29]和实际网络运行情况可以得知,影响节点特性的关键在于网络本身,所以更为关键的是复杂网络指标,这与计算结果是一致的,即运用熵权法计算所得各指标的权重是合理的.
对华东地区航路点重要程度进行评价,得到各航路点的评价结果 {G_i} ,结果如图5所示. 从整体来看,华东地区航路点的综合接近度分布较为均匀,大多集中在0.2~0.4,仅有少量航路点 {G_i} 较大. 其中, {G_i} >0.5的航路点仅有19个,说明华东地区大多数航路点的差别性不大,少数节点较为重要,在网络结构及交通流量方面都起着较为关键的作用.
为更好地分析本文所提方法的优劣,采用传统TOPSIS法对所建立的航路网络进行分析,将2种方法进行对比,各自结果取前20名,比较结果如表2所示. 表中,传统方法为复杂网络的基本指标(平均路径长度、簇系数、度分布、介数)进行评价的结果. 从表2中可以看出:首先,本文方法和TOPSIS方法位于前2名的2个节点是一致的,同时重要度前5名的航路点集合也是相同的,说明本文方法是符合事实规律的;其次,第3名(节点JTN) 和第4名(节点ELNEX)2个节点在排名上有所区别. 根据网络结构及流量数据可知,节点JTN的10个属性值大小在各自单独排名中有2个第1名,1个第9名,节点ELNEX的10个属性值在各自属性排名中有1个第1名,2个第8名,2个第9名,且结合图4的各指标权重值可以明显看出节点JTN要比节点ELNEX更重要,所以本文方法将节点JTN排在第3位,更贴近实际情况.
表 2 航路网络排名前20的评价结果Table 2. Evaluation results of top 20 points in en-route network排名 本文方法 TOPSIS 传统方法 值 航路点 值 航路点 值 航路点 1 0.703 TOL 0.867 TOL 0.697 TOL 2 0.685 HFE 0.759 HFE 0.687 DST 3 0.639 JTN 0.729 ELNEX 0.641 DO 4 0.620 ELNEX 0.726 P215 0.617 SHZ 5 0.603 P215 0.724 JTN 0.612 OF 6 0.602 SHR 0.699 DST 0.603 HFE 7 0.601 DST 0.692 SHR 0.593 JTN 8 0.588 DO 0.612 KAKIS 0.536 SUPAR 9 0.563 BK 0.608 BK 0.519 BK 10 0.561 AND 0.605 AND 0.500 P215 11 0.559 SHZ 0.552 SHZ 0.495 ELNEX 12 0.551 KAKIS 0.541 NINAS 0.488 BZ 13 0.533 NINAS 0.533 LASAN 0.472 LYG 14 0.531 LASAN 0.533 DO 0.449 SHR 15 0.511 UGAGO 0.526 UGAGO 0.433 PK 16 0.508 BZ 0.509 SASAN 0.431 YCH 17 0.504 P263 0.509 XUVGI 0.429 RUPUD 18 0.503 PINOT 0.499 OF 0.424 UGAGO 19 0.502 JDZ 0.498 MADUK 0.424 OSIKI 20 0.493 SASAN 0.497 PINOT 0.412 NOBEM 并且,表2中TOPSIS方法得到的计算结果第13位和第14位以及第16位和第17位分别相同. 而本文方法得到的综合接近度结果均不相同,但TOPSIS方法得到的结果中有68个结果均有重复值,无法准确对相同节点的重要程度进行区分,说明本方法相比于TOPSIS方法来说更准确.
同时,传统复杂网络的基本指标相比,使用本文所提方法不仅考虑到网络本身结构对航路点的影响,同时也充分考虑到在实际运行过程中,航路点的流量负载情况及对周围节点的影响情况. 比如使用传统复杂网络基本指标进行评价时,航路点DO和SHZ排名比较靠前,但结合流量统计情况来看,这2个航路点分别位于第13位和第16位,所以综合网络结构指标与运行指标,运用本文建立的指标体系所得到的评价结果相对更合理.
根据上述重要程度量化值,对华东地区航路点分级. 基于K-means方法得到eSSW,如图6所示. 可以看出,eSSW随聚类数增加而不断减小,开始时减速较快,在聚类数为3时已减小到54.27,此后缓慢减小. 说明,聚类数为3后,聚类效果不再显著提升. 因此,将航路点等级分为3类,分别为关键、次关键和一般. 将其绘制在航路网络图中,如图7所示.
从图7中可以发现,关键航路点总体规模较少,仅有29个,且包含 {G_i} 排名前20的航路点,主要分布在航路网络布局较为密集的区域. 此类关键航路点,在结构方面对航路网络的影响性较大、或具有较高的流量、或脆弱性较强,亦或是3个方面的指标均较高. 当其受到干扰无法正常运行时,航路网络整体运行受影响较大,威胁到网络的稳定性,容易造成连锁反应进而引发大范围航路节点失效. 因此,需要加强对于这些关键航路点的防护,可以从日常维护、管制人员培训等方面入手,降低其发生故障或事故的概率. 当其无可避免地受到干扰时,可以通过加强航路时空资源的分配,着重保障这些节点的正常运行. 而对于次要航路点以及一般航路点,其在运行中发挥的作用较为一般,大多分布在航路网络较为疏松的位置,其关注度可相对较低.
4. 结 论
1) 综合考虑航路网络的拓扑结构及复杂特性等因素,从复杂网络特性、交通流量特性、脆弱性3个角度选取较全面的指标构建节点重要程度评估指标体系. 采用基于相对熵的改进TOPSIS和灰色关联度的综合评估方法得到各航路点的重要程度综合量化结果,并通过基于K-means的聚类方法划分航路点重要程度等级,最终对航路网络关键节点加以识别. 相较于单一指标和传统TOPSIS法,本文方法评价结果更加全面准确,也更加符合空管工作对航路网络实际运行管控需要.
2) 对我国华东航路网络实例分析结果发现,关键航路点主要分布在航路布局较为密集的区域,航路网络的结构特性在航路运行中占主导作用. 因此,在实际管理过程中,不仅需要在实时运行过程中对这些关键节点给予更多关注,也应该在航路布局时尽可能优化使空域使用更加合理,降低发生个别关键航路点失效造成的连锁反应或大面积网络崩溃的可能性.
-
表 1 华东地区航路点评价指标规范化数值
Table 1. Normalized values of evaluation indexes for en-route waypoints in Eastern China
航路点序号 Z1,1 Z1,2 Z1,3 Z1,4 Z2,1 Z2,2 Z2,3 Z3,1 Z3,2 Z3,3 1 0.222 0.095 0.610 0.095 0.533 0.354 0.447 0 0.097 0.897 2 0.111 0.018 0.794 0.077 0.000 0.000 0.000 0 0.068 0.831 3 0.444 0.130 0.871 0.130 0.733 0.459 0.505 0 0.134 0.789 4 0.111 0.391 0.691 0.012 0.667 0.078 0.107 0 0.130 0.838 5 0.111 0.114 0.765 0.032 0.333 0.131 0.184 0 0.089 0.835 6 0.111 0.055 0.251 0.005 0.533 0.158 0.175 0.500 0.242 0.869 7 0.111 0.027 0.847 0.086 0.733 0.231 0.243 0 0.085 0.850 8 0.556 0.604 0.924 0.153 0.600 0.208 0.252 0 0.407 0.892 9 0.111 0.103 0.613 0.007 0.200 0.024 0.058 0 0.129 0.811 10 0.111 0.031 0.285 0.000 0.267 0.010 0.029 0 0.061 0.840 表 2 航路网络排名前20的评价结果
Table 2. Evaluation results of top 20 points in en-route network
排名 本文方法 TOPSIS 传统方法 值 航路点 值 航路点 值 航路点 1 0.703 TOL 0.867 TOL 0.697 TOL 2 0.685 HFE 0.759 HFE 0.687 DST 3 0.639 JTN 0.729 ELNEX 0.641 DO 4 0.620 ELNEX 0.726 P215 0.617 SHZ 5 0.603 P215 0.724 JTN 0.612 OF 6 0.602 SHR 0.699 DST 0.603 HFE 7 0.601 DST 0.692 SHR 0.593 JTN 8 0.588 DO 0.612 KAKIS 0.536 SUPAR 9 0.563 BK 0.608 BK 0.519 BK 10 0.561 AND 0.605 AND 0.500 P215 11 0.559 SHZ 0.552 SHZ 0.495 ELNEX 12 0.551 KAKIS 0.541 NINAS 0.488 BZ 13 0.533 NINAS 0.533 LASAN 0.472 LYG 14 0.531 LASAN 0.533 DO 0.449 SHR 15 0.511 UGAGO 0.526 UGAGO 0.433 PK 16 0.508 BZ 0.509 SASAN 0.431 YCH 17 0.504 P263 0.509 XUVGI 0.429 RUPUD 18 0.503 PINOT 0.499 OF 0.424 UGAGO 19 0.502 JDZ 0.498 MADUK 0.424 OSIKI 20 0.493 SASAN 0.497 PINOT 0.412 NOBEM -
[1] NEWMAN M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256. doi: 10.1137/S003614450342480 [2] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6: 888-893. doi: 10.1038/nphys1746 [3] CHEN D B, LÜ L Y, SHANG M S, et al. Identifying influential nodes in complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2012, 391(4): 1777-1787. doi: 10.1016/j.physa.2011.09.017 [4] 闫玲玲,陈增强,张青. 基于度和聚类系数的中国航空网络重要性节点分析[J]. 智能系统学报,2016,11(5): 586-593.YAN Lingling, CHEN Zengqiang, ZHANG Qing. Analysis of key nodes in China s aviation network based on the degree centrality indicator and clustering coefficient[J]. CAAI Transactions on Intelligent Systems, 2016, 11(5): 586-593. [5] WANG H Y, SONG Z Q, WEN R Y, et al. Study on evolution characteristics of air traffic situation complexity based on complex network theory[J]. Aerospace Science and Technology, 2016, 58: 518-528. doi: 10.1016/j.ast.2016.09.016 [6] BELKOURA S, COOK A, PEÑA J M, et al. On the multi-dimensionality and sampling of air transport networks[J]. Transportation Research Part E: Logistics and Transportation Review, 2016, 94: 95-109. doi: 10.1016/j.tre.2016.07.013 [7] WANG H Y, XU X H, ZHAO Y F. Empirical analysis of aircraft clusters in air traffic situation networks[J]. Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, 2017, 231(9): 1718-1731. doi: 10.1177/0954410016660870 [8] 任新惠,杨丽. 中国航空货运网络脆弱性分析[J]. 安全与环境学报,2020,20(3): 840-848.REN Xinhui, YANG Li. Vulnerability analysis of China air cargo transportation network[J]. Journal of Safety and Environment, 2020, 20(3): 840-848. [9] 徐开俊,肖成坤,杨泳,等. 基于复杂网络理论的中国城市航空网络有向加权分析[J]. 科学技术与工程,2021,21(36): 15669-15673.XU Kaijun, XIAO Chengkun, YANG Yong, et al. Directed weighted analysis of Chinese urban aviation network based on complex network theory. Science Technology and Engineering[J], 2021, 21(36): 15669-15673. [10] BAE J, KIM S. Identifying and ranking influential spreaders in complex networks by neighborhood coreness[J]. Physica A: Statistical Mechanics and Its Applications, 2014, 395: 549-559. doi: 10.1016/j.physa.2013.10.047 [11] LIU Y, TANG M, ZHOU T, et al. Identify influential spreaders in complex networks, the role of neighborhood[J]. Physica A: Statistical Mechanics and Its Applications, 2016, 452: 289-298. doi: 10.1016/j.physa.2016.02.028 [12] ZAOLI S, MAZZARISI P, LILLO F. Trip Centrality: walking on a temporal multiplex with non-instantaneous link travel time[J]. Scientific Reports, 2019, 9: 10570.1-10570.11. [13] ULLAH A, WANG B, SHENG J F, et al. Identification of nodes influence based on global structure model in complex networks[J]. Scientific Reports, 2021, 11: 6173.1-6173.11. [14] ULLAH A, WANG B, SHENG J F, et al. Identifying vital nodes from local and global perspectives in complex networks[J]. Expert Systems with Applications, 2021, 186: 115778.1-115778.10. [15] GUIMERÀ R, MOSSA S, TURTSCHI A, et al. The worldwide air transportation network: anomalous centrality, community structure, and cities’ global roles[J]. Proceedings of the National Academy of Sciences of the United States of America, 2005, 102(22): 7794-7799. [16] 段东立,战仁军. 基于相继故障信息的网络节点重要度演化机理分析[J]. 物理学报,2014,63(6): 385-393.DUAN Dongli, ZHAN Renjun. Evolution mechanism of no de imp ortance based on the information ab out cascading failures in complex networks[J]. Acta Physica Sinica, 2014, 63(6): 385-393. [17] MORONE F, MAKSE H A. Influence maximization in complex networks through optimal percolation[J]. Nature, 2015, 524: 65-68. doi: 10.1038/nature14604 [18] 程光权,陆永中,张明星,等. 复杂网络节点重要度评估及网络脆弱性分析[J]. 国防科技大学学报,2017,39(1): 120-127.CHENG Guangquan, LU Yongzhong, ZHANG Mingxing, et al. Node importance evaluation and network vulnerability analysis on complex network[J]. Journal of National University of Defense Technology, 2017, 39(1): 120-127. [19] DU W B, ZHANG M Y, ZHANG Y, et al. Delay causality network in air transport systems[J]. Transportation Research Part E: Logistics and Transportation Review, 2018, 118: 466-476. doi: 10.1016/j.tre.2018.08.014 [20] WANG Z K, WEN X X, WU M G. Identification of key nodes in aircraft state network based on complex network theory[J]. IEEE Access, 2019, 7: 60957-60967. doi: 10.1109/ACCESS.2019.2915508 [21] 冯霞,贾宏璨. 考虑节点失效和边失效的航空网络鲁棒性[J]. 北京交通大学学报,2021,45(5): 84-92.FENG Xia, JIA Hongcan. Aviation network robustness considering node failure and edge failure[J]. Journal of Beijing Jiaotong University, 2021, 45(5): 84-92. [22] LORDAN O, SALLAN J M, SIMO P, et al. Robustness of the air transport network[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 68: 155-163. doi: 10.1016/j.tre.2014.05.011 [23] CHEN Y, WANG J E, JIN F J. Robustness of China’s air transport network from 1975 to 2017[J]. Physica A: Statistical Mechanics and Its Applications, 2020, 539: 122876.1-122876.12. [24] LI W, CAI X. Statistical analysis of airport network of China[J]. Phys Rev E Stat Nonlin Soft Matter Phys, 2004, 69(4): 046106.1-046106.11. [25] ZHOU Y M, WANG J W, HUANG G Q. Efficiency and robustness of weighted air transport networks[J]. Transportation Research Part E: Logistics and Transportation Review, 2019, 122: 14-26. doi: 10.1016/j.tre.2018.11.008 [26] QI X Q, FULLER E, WU Q, et al. Laplacian centrality: a new centrality measure for weighted networks[J]. Information Sciences, 2012, 194: 240-253. doi: 10.1016/j.ins.2011.12.027 [27] WANG N, GAO Y, HE J T, et al. Robustness evaluation of the air cargo network considering node importance and attack cost[J]. Reliability Engineering & System Safety, 2022, 217: 108026.1-108026.15. [28] 陈静,孙林夫. 复杂网络中节点重要度评估[J]. 西南交通大学学报,2009,44(3): 426-429. doi: 10.3969/j.issn.0258-2724.2009.03.021CHEN Jing, SUN Linfu. Evaluation of node importance in complex networks[J]. Journal of Southwest Jiaotong University, 2009, 44(3): 426-429. doi: 10.3969/j.issn.0258-2724.2009.03.021 [29] 张喜平,李永树,刘刚,等. 节点重要度贡献的复杂网络节点重要度评估方法[J]. 复杂系统与复杂性科学,2014,11(3): 26-32,49.ZHANG Xiping, LI Yongshu, LIU Gang, et al. Evaluation method of importance for nodes in complex networks based on importance contribution[J]. Complex Systems and Complexity Science, 2014, 11(3): 26-32,49. -