基于边权重和集聚系数的航线重要性评估方法

丁建立 王建思

(中国民航大学计算机科学与技术学院 天津 300300)

0 引 言

近年来，随着社会经济节奏不断加快，航空运输业正在迅猛发展，空中交通流量在日益增加。与此同时，因某些偶然或突发事件导致的空中交通拥堵和延误问题也更加频繁地出现。空中交通延误不仅造成了严重的经济损失，严重影响旅客的行程规划和出行心情，同时对航空公司、管制员和驾驶员也带来了更大负担，还可能带来一些事故隐患。因此在突发事件发生的前提下，航空运输网络如何保持鲁棒性，使突发事件带来的损失和影响降到最低，成为人们越来越关注的问题。

航空运输网络中，重要航线对整个通航网络的连通性和可靠性有着重要的影响。准确地评估和度量航线重要性对突发事件下的流量调配具有很大的功能性。受突发事件的影响，机场和航线的容量均受到限制，意味着将有一些航班无法正常起飞和降落，严重时机场可能会陷入瘫痪，机场间航线均不可用，引发网络中其他通航城市之间的运输中断，带来难以估计的损失。所以准确评估航空运输网络中的重要航线，在进行流量调配时考虑航线的重要程度，对重要航线上的航班进行优先考虑和调度，可以有效地减少损失，将突发事件造成的影响降到最低。本文针对我国目前空中交通状况，将航空运输网络看作一个整体性的复杂网络，对网络中的机场节点加权处理并考虑相关性，选取合适的指标对边赋予权值，通过复杂网络中的边权重和集聚系数等概念和指标，提出了一种新的航线重要性评估方法。之后根据复杂网络中边连通率作为评价指标，采取不同的攻击方式分析航空运输网络的鲁棒性，验证了该评估方式的有效性，为航空网络规划和处理突发事件时的航行调度提供理论依据。

1 相关研究

航空运输网络是一个动态的复杂网络，可以从复杂网络理论的角度进行分析。目前对航空网络复杂性的研究，已经有很大进展。文献[1-2]根据复杂网络的理论，分别对欧洲航空运输网络和美国航空运输网络进行了研究，发现了航空运输网络具有小世界特性，节点机场的度分布服从双段幂律分布。目前我国学者大多进行中国航空运输网络的实证研究和抗毁性分析。实证研究主要通过复杂网络中的不同指标，研究我国航空运输网络具有复杂网络的一般特征和自有特性，同时分析不同指标对航空运输网络不同的影响。抗毁性分析是对中国航空运输网络进行不同种类的攻击，通过复杂网络抗毁性测度指标如最大连通子图、网络效率等，研究中国航空网络的抗毁性，为本文航线重要性评估的验证提供了思路。Zhang等[3]运用复杂网络理论，对中国机场网络进行研究和分析，发现中国机场网络的自有特征；Cai等[4]研究中国航空网络，发现了中国航空网络具有度分布呈指数、聚类程度较低、最短路径长度较大等特征；姚红光等[5]通过仿真实验对中国航空网络的抗毁度进行分析，发现中国航空网络在面对不同攻击和干扰时鲁棒性是不同的；陆靖桥等[6]通过连通子图作为测度指标对复杂网络的鲁棒性进行研究，发现基于度和介数的蓄意攻击策略效果最好。

同时，大多数学者对复杂网络中的节点重要性进行了大量研究，对节点重要性排序也有很多不同的方法，但是针对复杂网络中的边重要性评估研究不多。Girvan等[7]在介数指标的基础上，提出了边介数(edge-betweenness)的概念，作为反映网络中边重要程度的最基本指标；李树彬等[8]通过研究一些运输网络的拓扑结构，发现密度最大的路段都是网络中介数较大的边，这样的路段更易发生交通拥堵。但是仅通过介数刻画边的重要程度具有很大的片面性，不同网络结构中分析并不准确。邱原等[9]对不同网络拓扑结构进行研究，综合边介数和节点对边的影响，提出了一种作战网络关键边的评估方式，这种方式具有较高准确性，但是计算复杂度太大；Holme等[10]指出复杂网络中边介数与两个端节点的度值乘积是有一定关联的，并得到了一种边加权方式来刻画边的重要程度。但是边权重根据加权方式的不同，评估出的重要性结果是不同的，同时根据不同网络的实际情况，对边加权的方式也是多种多样的；崔文岩等[11]提出了一种节点度和介数相关的边权重计算方式，使得边对故障的额外负载承载能力更强，但这种加权方式仅限于某些网络；任卓明等[12]通过节点的相邻节点数量及节点间的紧密度，提出了一种节点重要性评价方法；唐诗琦等[13]考虑节点的全局结构，同时对节点局部特征及邻节点特征进行提取，提出了一种重要节点的发现算法。这些方法对评估边的重要性都具有一定的启示意义。

本文针对我国目前空中交通现况，提出了一种航线重要性评估方法，主要贡献如下：(1) 确定网络中边权重的加权方式，对航空运输网络加权处理；(2) 通过边权重、节点度值和集聚系数提出一种新的航线重要性评估方法；(3) 选取复杂网络中的边连通率作为评价指标，采取不同的攻击方式，验证了该评估方法的有效性，从而为航空运输网络航班规划和处理突发事件时的航行调度提供理论依据和指导。

2 方法设计

2.1 航空运输网络中的概念

复杂网络中，节点的度指的是与节点连接的边的数量，节点i的度可记为：

(1)

式中:aij为节点i与节点j之间连接边的数量。航空运输网络中，机场即为网络中的节点，机场节点的度指的是与此机场连接的通航航线的数量。度值的大小直观地反映了机场的通达性和规模大小，与机场的重要程度有很大的关系。

两节点的最短路径中，必须经过某个节点的路径数目占所有最短路径数目的百分比即为该节点的介数。任意节点v的介数值定义如下：

(2)

式中:∂ij为节点i到j的最短路径数目；∂ij(v)为节点i到j的最短路径中经过节点v的最短路径数目。航空运输网络中，两城市间的最短通航航线必须经由某个机场或某条航线的航线数量占总最短通航航线的比例，即为此机场节点或此航线的介数。介数可以反映机场节点和航线在运输网络中的中枢性。

网络中一个度为ki的节点vi的集聚系数[14]定义为：

(3)

式中：ki是节点vi的邻节点的个数；Ei是ki个邻节点之间存在的边数。集聚系数指的是实际存在的边数与ki个节点存在的最大边数的比值，表示网络中某节点的邻节点之间相互连接的程度，反映了网络的集聚化程度。航空运输网络中，节点的集聚系数体现了机场节点间的聚类情况，可以反映相邻机场间的紧密程度。

2.2 航空运输网络中边重要性评估方法

2.2.1边介数刻画与作用

边介数反映了边在整个网络中的重要程度，可以衡量边在网络中的影响程度和作用大小。边介数计算公式如下：

(4)

式中：Bθ为边θ的边介数；L(g,k)为节点g、k之间最短路径的数量；L(g,k,θ)为节点g、k之间经过边θ的最短路径的数量。

但是在不同的网络拓扑结构中都会存在一个问题，边介数数值相同但是边的重要程度是不同的，这是由网络的结构决定的。同时计算介数时间复杂度高，在航空运输网络中无法满足实时性的要求。

2.2.2边权重赋值与衡量

复杂网络将包含的元素映射为一个节点集，通过连边来表示元素间的相互作用关系，这样就将一个复杂系统映射成一个仅包含节点和连边的无权网络。但这样的无权网络无法反映节点间相互作用的强度，必须考虑赋予边相应的权值。边加权方式可根据相关物理量或相互作用的某种属性进行加权，一般通过两节点的统计指标如节点度值、节点介数、特征向量等指标对边赋予权值，同时边权重也可以作为衡量边重要程度的一个指标，公式如下：

wij=wji=αi·αj

(5)

式中:αi、αj是节点i,j的统计指标，这个指标可根据不同相互作用的关系而进行不同的变化，但是i、j节点选取的统计指标是确定值。通过边权重评估边重要性具有片面性，因为根据指标选取的不同，得出的评价结果也是有差异的，可能不满足实际应用，在某些情况下表现的差异极大。

2.2.3边介数与节点度值的评估

综合边介数、节点度值和节点介数指标，同时考虑边两端节点对边同等的支撑作用，以及边自身属性，提出了一种边重要性评估的方法，公式如下：

(6)

式中：Iij表示边eij的重要性度量值；Bij表示边eij的边介数；ki、kj分别表示节点i、j的度；Bi、Bj分别代表节点i、j的节点介数。这种评估方法考虑了节点对边的支撑和影响作用，准确性较其他方法更高，但需要计算节点介数值和边介数值，成本代价太大，并不适用于航空运输网络。

2.3 航线重要性评估过程

评估航空运输网络中航线重要性的基本思想是在航空运输网络中采用合适的方式给边赋予权值，作为衡量边重要性的指标；同时通过其他指标刻画两端节点对边的影响作用，从而确定航空运输网络中的重要航线。

航空运输网络中，因为运量和航距长度的不同，无法通过无权网络来表示，所以使用加权的方式加以描述。权重可以表示网络中节点和边相互作用的强度，根据不同情况可选择不同的加权方式。为每条边赋予边权可以反映强度大小，也可以通过权重描述边的重要程度。目前主要的边加权方式是通过节点的度值、介数等指标，根据不同需求和实际情况对这些指标进行不同的变化和处理。下面从机场吞吐量、总航距长度的角度考虑，通过点权分析机场节点的度值、介数对机场节点强度的影响，从而确定航空运输网络中边的加权方式。

2.3.1机场节点度值对机场节点强度的影响

机场节点的指标主要是节点度分布和节点介数值。节点的度值是节点重要性最直观的体现。通过点权对机场节点强度进行描述，分析吞吐量点强度与机场节点度值的关系。将航线上的客运量作为边权，机场点权即为所有航线上的总客运量，即机场吞吐量，点权定义为：

(7)

图1 航空运输网络机场吞吐量与机场节点度值的相关性

以航线长度对边加权，那么机场节点强度即为机场总航距的长度。分析节点度值与机场总航距长度的关系。节点i机场的距离点强度定义为：

(8)

图2 航空运输网络机场总航距长度与机场节点度值的相关性

2.3.2机场节点介数对机场节点强度的影响

图3 航空运输网络机场吞吐量与机场节点介数的相关性

图4 航空运输网络总航距长度与机场节点介数的相关性

2.3.3航空运输网络航线加权方式

在航空运输网络中，机场节点度分布与机场总运量、航距总长度高度正相关。度是复杂网络中的最基本参量，具有简单直观、计算复杂度低的特点。同时复杂网络中，边介数与两端点的度值乘积是正相关的关系。所以通过节点度值对边赋予权重，有如下公式：

wij=wji=(kikj)αα>0

(9)

式中：ki、kj分别表示节点i,j的度；α(α>0)是一个可调系数，用于描述边权重与节点度之间的相互关系，以及网络边的异质程度。

分析α取值是否影响网络中以边权重为指标的边重要性排序。当α=1时，此时是一个线性关系，这个线性关系是正相关的；当1>α>0或α>1时，虽然边权重与度乘积成非线性关系，但无论α(α>0)取何值时，以此公式度量边的重要性并不影响重要性排序结果[13]。为了降低时间复杂度且便于计算，可取α=1，即wij=wji=kikj，时间复杂度为O(n2)。

分析通过节点度值对边加权的方式是否符合实际权重。文献[16]对几种典型网络进行分析，给出了几种加权方式下的边权重与真实权重(边承载的流量负荷)的相关系数，如表1所示。

表1 现实网络权重与BiBj、kikj和Bij加权方式下权重的相关系数

表1中：USAir97为美国航线连接网；USAirport500是选取500个美国商业机场构成的一个复杂网络；Lesmis是世界名著《悲惨世界》的人物关系网；Bkham是某社团里的人物关系网。可以看出，以上几种网络的真实权重与边介数几乎没有任何相关性，但是与基于度值加权下的边权重关联度较大，这也验证了上文中赋予边权重的方法的可用性。

2.3.4基于边权重与集聚系数的航线重要性评估方法

通过节点度指标对边加权进行重要性分析仅使用了边两端的节点度值作为评估指标，当节点中心性不满足时，这种度量方式有很大的片面性，也忽略了节点对边的支撑作用。所以还需考虑刻画节点重要性的其他指标。

集聚系数可以准确反映网络中节点结集成团的程度，可作为衡量边两端的节点(即邻节点)之间的紧密程度。通过节点度值与集聚系数两项指标，评估节点重要性方式如下：

Ei=ki·α-C(i)α>1

(10)

式中：ki为节点vi的度；α为可调参数；C(i)为节点i的集聚系数。此种方式充分考虑了节点的直接影响力和节点邻居之间连接的紧密程度，可以准确评价网络中节点的重要性。同时，节点集聚系数体现了以此节点为中心的连通子图的范围和影响，可作为两端节点对边的支撑作用来考虑，为节点间的边重要性分析提供了一种思路。

基于上述研究，考虑航空运输网络的自有特性，以及节点度值与集聚系数对边重要性的影响，提出了一种新的评估网络关键边eij重要程度的评价指标，数学模型如下：

(11)

式中：k为平均度数；α是可调参数，实际取值可通过仿真实验得到；c(i)、c(j)为节点i、j的聚类系数；θ用来刻画边的异质度，但不随取值改变优先级顺序，为方便计算可取值为1。由于节点的集聚系数c(i)可能为0，故构造的函数为减函数，并通过仿真实验得到α的最优解。

2.4 航空运输网络鲁棒性衡量指标

当网络受到攻击后，衡量网络的鲁棒性根据出发点的不同，指标也是多种多样的[16]。航空运输网络中评估航线重要程度，需要根据网络的真实情况选取指标进行衡量。文献[17]在研究网络的鲁棒性时，将点连通率S(v)作为评价指标。点连通率指的是攻击前和攻击后，网络中的最大连通子图所含节点的比值。因此本文评估网络中的关键边时，采用了边连通率S(e)作为指标。网络中重要的边遭到攻击后，最大连通子图中的连边数会更少，边连通率会下降得很快；但是网络中重要程度较低的边遭到攻击后，边连通率并不会发生太大的变化。边连通率S(e)定义如下：

(12)

3 实 验

3.1 中国航空运输网络航线重要性评估对比

本文研究的中国航空运输网络节点机场、航线的统计均以民航资源网提供的2018年夏秋季机场航班时刻为准。对于拥有两个机场的城市则将数据加总统计，且当同一城市的两个机场均有通往另一城市的航线时，航线数量仅统计一次；数据中仅统计我国大陆地区的机场和航线。下面用上文提到的几种边重要性评价指标对航线重要程度进行排序，结果见表2。

表2 排名前10的中国航空运输网络重要航线

3.2 边攻击模式分析对比

为了验证本文方法的合理性和可用性，删除相应比例的连边来观察网络拓扑结构的变化，之后根据边连通率的下降程度来评价效果的好坏。分别采用本文评估方法和基于边介数、边权重、边介数与节点度值三个指标的评估方法进行边攻击对比分析，根据评估指标的数值，按照从大到小的顺序依次删除连边。F为每次进行攻击的连边数与所有连边数的比值，边连通率S(e)为航空运输网络鲁棒性的衡量指标。

经过调试得出，当评价指标选择本文方法时，对于指标Eij，α的取值区间为[6.78,10.13]，此时评价指标获取的结果最好。不同攻击策略下，边连通率S(e)的变化如图5所示。

图5 移除边比例和边连通率的关系

可以看出，随机攻击与蓄意攻击相比效果较差，说明中国航空运输网络面对随机攻击时具有较好的鲁棒性。在蓄意攻击的仿真实验中，基于边介数及节点度值指标攻击的效果最好，呈陡峭直线型下降趋势。这表明上述指标针对中国航空运输网络边重要性的评估最为准确，可以更好地刻画网络中边的重要程度。本文方法指标的攻击效果仅次于边介数及节点度值指标且差距不大，攻击效果也成陡峭直线型下降。但是边介数的时间复杂度为O(n3)，本文方法指标的时间复杂度为O(n2)，在针对突发事件下的流量调配和航班管理时本文方法能够更快一步，减少损失和影响。

4 结 语

本文运用复杂网络理论，对中国航空运输网络进行分析。首先对网络进行加权处理，分析节点度值、节点介数与机场吞吐量、航距长度的相关性，确定边权重的加权方式；接着考虑节点对边的支撑作用及节点间的集聚程度；最后基于边权重和集聚系数提出一种新的边重要性评估方法。该方法综合考虑了边真实权重、端节点对边的影响作用、局部节点间的影响作用和时间复杂度，并通过基于边介数、边权重和边介数及节点度值的评估方法对中国航空运输网络进行边攻击，采用边连通率作为网络鲁棒性的衡量指标，考察这四种方法的攻击效果。结果表明，相比于其他三种方法，本文方法的攻击效果仅次于边介数及节点度值评估方式，但是其时间复杂度降低很多，在突发事件的前提下对流量调配、航班管理等具有很好的实用价值。