基于邊權重和集聚系數的航線重要性評估方法

丁建立 王建思

(中國民航大學計算機科學與技術學院 天津 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 結 語

本文運用復雜網絡理論，對中國航空運輸網絡進行分析。首先對網絡進行加權處理，分析節點度值、節點介數與機場吞吐量、航距長度的相關性，確定邊權重的加權方式；接著考慮節點對邊的支撐作用及節點間的集聚程度；最后基于邊權重和集聚系數提出一種新的邊重要性評估方法。該方法綜合考慮了邊真實權重、端節點對邊的影響作用、局部節點間的影響作用和時間復雜度，并通過基于邊介數、邊權重和邊介數及節點度值的評估方法對中國航空運輸網絡進行邊攻擊，采用邊連通率作為網絡魯棒性的衡量指標，考察這四種方法的攻擊效果。結果表明，相比于其他三種方法，本文方法的攻擊效果僅次于邊介數及節點度值評估方式，但是其時間復雜度降低很多，在突發事件的前提下對流量調配、航班管理等具有很好的實用價值。