基于復雜網絡的中國民航網絡魯棒性分析

謝本凱，李 琴，黃龔迪，林睿浚，李五雙

（1.鄭州航空工業管理學院 管理工程學院，河南 鄭州 450046；2.鄭州航空工業管理學院 信息管理學院，河南 鄭州 450046；3.航空經濟發展河南省協同創新中心，河南 鄭州 450000）

1 引言

民航網絡是實現航空交通運輸的基礎條件，它的穩定性和規范化是國家在航空領域發展水平的一個直觀體現，其與其它類型的交通運輸網絡有較大不同，無論是在科技水平、空間跨度還是推動經濟發展方面都更加亮眼突出。我國民航業處于成長時期，民航網絡在工作效率和容錯度等方面還不足以滿足社會發展的需要，有明顯的可提升空間。由于各種人為因素和自然因素，無法避免和預測的不穩定因素都可能對我國民航網絡帶來沖擊和考驗。怎么使我國民航網絡改善優化、提高效率，從而大大提升我國民航競爭力是一個值得探討的方向。

20 世紀中期隨機圖理論被提出，為復雜網絡研究打開了大門。20世紀末Watts[1]和Barabasi[2]分別提出了被視為為復雜網絡研究掀開新篇章的小世界網絡模型和無標度網絡模型。隨后，關于復雜網絡的剖析也開始漸漸深入，與此同時越來越多的學者將該理論應用于對現實網絡的研究中。Oriol Lordan[3]等對全球民航網絡的統計參數進行了研究，并分析了其魯棒性，結果發現運用介數中心性自適應策略可以精準找出重要機場；Wei[4]等利用荷蘭中壓電力網的數據，研究了不同信息網拓撲和兩類攻擊方式對電力CPS 連鎖故障的影響，得出小世界網絡的信息網拓撲能使該網絡魯棒性更好；Lara-Cabrera[5]等利用復雜網絡的拓撲性質分析CIG網絡，研究了大規模結構、增長機制和其他特征之間的協作模式。徐偉舉[6]等人分析了在動態和靜態攻擊兩種模式下美國航空網絡、SW 網絡和BA 網絡的抗毀性；魏震波[7]等總結歸納了在電網分析中應用到的一些研究成果，并針對研究方法和成果的質疑進行了較全面的分析；田慶飛[8]基于復雜網絡理論和交通擁堵分析，對城市公交網絡生成與優化的相關算法與方法進行了研究。而本文從隨機攻擊和蓄意攻擊兩個方面，采用平均路徑長度、介數等參數分析了中國民航網絡的整體魯棒性。

2 理論概述

2.1 圖論基礎

民航網絡可以被描述為一個二元組G=（V,E）,其中V={v1,v2,…,vn}是機場的節點集，E={e1,e2,…,em}是航線的邊集，vi代表節點，ej代表邊。用|V|表示V中的節點個數，|E|表示E的邊數。在本文中，它被定義為無向無權網絡，也就是說它的節點（va,vb）和（vb,va）表示同一條邊，并且每條邊不賦予權值。

2.2 平均路徑長度

它可以描述民航網絡中的平均分離程度。在所有連通節點va和vb的路徑中，節點最少的那一條被稱為兩點間的最短路徑，而最短路徑的邊數被稱為節點va與vb之間的最短距離，它是指網絡中所有最短距離里的最大數。而所有節點對的平均值就是平均距離L，一般計算公式為：

2.3 聚集系數

它是用來度量網絡中節點聚集情況的參數，表現了網絡的簇擁狀態。通常可以用這一系數來描述網絡局部的結構性質。記有ka個節點與va直接連接，則在無向網絡中ka個節點最多可能有ka(ka-1)/2 條邊，而真實存在的邊數記為Ma,可將節點va的聚集系數定義為：

本文研究的我國民航網絡，機場的簇擁情況就是節點的聚集系數。若機場的聚集系數大，說明它與其周圍所連接的機場所構成的網絡比較密集。

2.4 度與度的分布

度在復雜網絡中是用來描述節點特性的基礎參數，節點Va的相鄰邊數目就是它的度。度值的大小可以說明節點在網絡中的重要程度。引用鄰接矩陣C去定義它，那么C的某一行或某一列非零元素個數就是節點的度，用公式表現如下：

其中Cab表示矩陣C中非零元素。大多數真實網絡節點度符合一定的概率分布，度的分布也是可以用來描述復雜網絡統計特征的重要參數。在本文中P(k)就是用來描述中國民航網絡中航線是k的機場占總機場數的比率，同時本文利用累計度分布表示度的分布狀況。

2.5 連通子圖和連通度

連通子圖是指在網絡中的一個子圖內，任意兩個節點間都最少存在一條連通的邊。在一個復雜網絡中，可能有許多相對獨立的連通子圖存在。而當無論在該子圖中加入任何另外的節點都會影響這個子圖的連通性時，這個子圖被稱為最大連通子圖，也稱為連通分支。連通圖的連通程度就是連通度，它分為點連通度和邊連通度，一般來說連通度越好，這個網絡圖也就越穩定。

2.6 小世界網絡和無標度網絡

小世界網絡是指在一個結構很大的網絡中，節點之間的連接相對密切的情況，它的統計特點在于聚集系數大，但平均距離較小；在復雜網絡中的節點度分布如果符合冪律分布，就被稱為無標度網絡。

3 中國民航網絡建模與統計特性分析

3.1 建立模型

本文以中國民航網絡中的機場作為節點，并將機場之間的航線作為邊進行建模。以2017年民航機場吞吐量排名的報告中我國現存機場為基準，共216個機場節點，經統計共有2 363條無向邊。

由于中國民航網絡的節點復雜性、結構復雜性和運行復雜性等會導致各種不確定因素產生，本文對實際民航網絡做出如下設定：

（1）模型中中國民航網絡的邊就是民航的運行線路，并且所有邊都是無向邊；

（2）研究對象僅限于機場節點和機場之間的民航運輸線路，不考慮其他的相關對象；

（3）民航航線的拓撲特性均相同，即不考慮航空效率是否不同，也不考慮機場功能參數的不同，也就是說在進行魯棒性分析時網絡中的所有節點和均是無權的；

（4）對于擁有兩個或者超過兩個機場的城市均視為一個節點，即將機場合并使圖相應簡化。

3.2 統計特性分析

機場節點度K表示的是與它有航線的機場的數目。經計算得出中國民航網絡中的總度數為4 290，那么總的平均度就約為19.86，也就是說平均每一個機場與其他節點直接連接的航線約有20條。對數據進行統計分析可以得出圖1的度分布曲線圖。

圖1 度分布圖

中國民航網絡的平均路徑長度為2.41，這說明每兩個城市的機場之間通過約2 次的轉機就可以相互到達，而明顯的是該網絡的聚類系數較大，表現出強聚集性。由這兩個特點可知其滿足小世界特性，而在度分布圖可以直觀的觀察到曲線中的最高點屬于度數較小的節點，曲線的最低點屬于度數較大的節點，說明該網絡中有許多邊數較少的節點和少量邊數眾多的集散節點，這明顯是無標度網絡的特征。綜合而言，它具備小世界特性，但更多地體現無標度特性。表1是對近些年來相關文獻中中國民航網絡的特征參數值變化情況進行的統計。

表1 中國民航網絡統計參數特征比較

從表中數據對比可知，我國民航機場數不斷增加，從2005年至今已經擴建了將近100個機場；機場的大量增加使得網絡中的航線也不斷擴充，每個節點的度值增大，所以網絡的平均度也逐漸增大；而平均路徑長度在2012年前均不斷減小，但2018年卻大幅度增加，究其原因可能是增加機場時航線設定不夠規范、合理。

4 中國民航網絡魯棒性分析

4.1 中國民航網絡魯棒性

網絡魯棒性一般指其節點或邊被破壞的時候，網絡能繼續工作的能力，也叫做容錯能力、抗毀性。網絡的魯棒性也與其規模的大小有關，若網絡的規模越大，那么它可以替代的邊就越多，但如果規模過大，它發生意外和故障的幾率也比一般的網絡大得多。

本文中國民航網絡的魯棒性為在該網絡正常運轉或者受到兩類攻擊時，具有一定的抵抗能力，這種能力的強弱程度稱為魯棒程度。當遭受不在承受能力范圍內的意外攻擊時，網絡便無法保持原狀。

4.2 干擾措施

分析中國民航網絡的魯棒性時，本文基于移出網絡中節點從而引發故障的情況，對網絡整體進行分析。當節點突然遭受襲擊時，整個網絡會發生一定的變化。對于節點的攻擊分為隨機攻擊和蓄意攻擊兩種，隨機攻擊的發生可能是由于一些意外如天氣原因等，這類攻擊一般可以自我修復或重新連接以抵抗外部干擾；而蓄意攻擊的情況，一般會有很強的目的性，使沒有準備好的節點受到嚴重破壞，無法正常工作，深度影響網絡功能并大大降低了網絡維持自我安全的能力，恢復工作也會進行的很困難。本文為了更全面的分析中國民航網絡，將從隨機和蓄意兩方面去考慮，以提高容錯能力。

4.3 評估指標

本文選取平均路徑長度、最大連通度與介數作為評估指標，對中國民航網絡的魯棒性進行分析。

（1）中國民航網絡平均路徑長度L。它是指網絡中任兩個不同機場節點之間的最短連接距離的平均值。用n 代表網絡的節點數，dab表示節點a 與節點b之間的距離，則：

（2）最大連通度Gmax。這里指的是中國民航網絡在受到干擾以后，它所有依然連接且還能正常運轉的節點的網絡中，所含最多節點數的集團中節點數占有其他剩余節點的比例：

（3）介數B。它是用來反映中國民航網絡全局性的指標。在網絡中有一些節點雖然度較小，但卻是某兩個集團的中間連接點，那么它也同樣很重要，用介數便可以定義這樣的節點。本文在進行蓄意攻擊時，會選取介數值大的節點依次進行攻擊，再進行特征參數分析。

4.4 仿真流程

針對中國民航網絡的拓撲結構和其本身的復雜性，本節總結出了研究該網絡魯棒性的主要步驟，如圖2所示。

圖2 魯棒性分析仿真流程圖

5 基于復雜網絡的中國民航網絡魯棒性仿真分析

5.1 仿真實驗

在實驗中模擬隨機攻擊時，首先進行隨機節點選取，依次將故障點數設為節點總數的5%、10%、15%，并每次進行5 次實驗取參數平均值以得到結果；而在模擬蓄意攻擊時，先計算得出每個點的介數值，再按介數值由高到低排序，并從數值高的開始同樣依次移出節點總數的5%、10%、15%。特別說明的是，本文利用數字表示每一個城市的機場，機場間的航線用如A—B的形式表示，模擬節點遭受攻擊時便會將該節點所在的航線全部刪除。

中國民航網絡模型中節點總數為216，那么由216×5%、216×10%和216×15%可得出攻擊的節點數為10 個、21 個和32 個。在仿真實驗的隨機攻擊中，移除10 個節點平均有兩個孤立節點，移除21 個節點和32 個節點均平均有3 個孤立節點；而蓄意攻擊中，移除10 個節點后有12 個孤立節點出現，移除21個節點后有18個孤立節點出現，移除32個節點后有32個孤立節點出現。具體如圖3-圖5所示。

圖3 平均路徑長度變化趨勢

5.2 仿真結果分析

在未進行兩種攻擊前，中國民航網絡的平均路徑長度為2.412，最大連通度為1，介數值為0.15。而在進行仿真模擬攻擊后，每個數值都發生了一定的變化。顯而易見的是，蓄意攻擊后無論是哪一種參數增大或減小的趨勢相較于隨機攻擊都更加劇烈。

（1）平均路徑長度L。它是可以用來描述一個復雜網絡中節點間連接密切程度情況的統計參數。若平均路徑長度數值小，則說明節點之間關系密切，從某一節點到其他節點所用的時間更少，網絡的整體連接性較好；若平均路徑長度數值較大，則說明節點若想與某一非鄰邊節點有聯系要經過更多的邊和節點，在這期間意外情況很可能發生，這在中國民航網絡中表現為從某機場出發要去某地的話周轉次數將變多，所要消耗的時間也更長。由上一節的仿真結果可以分析出：

圖4 最大連通度變化趨勢

圖5 介數變化趨勢

在隨機攻擊模式下，盡管移出的節點數不斷增加，該網絡的平均路徑長度的波動幅度卻并不大，對于整個網絡來說幾乎沒有什么影響；而在蓄意攻擊模式下，中國民航網絡的平均路徑長度隨著移除節點數變多，數值不斷變大。由此可見中國民航網絡在遭遇蓄意攻擊時，若網絡節點不斷減少，系統內節點間的聯系會不斷的減弱，網絡會顯得更加脆弱，所以該指標參數反映了網絡魯棒性的降低。不僅如此，由統計曲線可以看出，在蓄意攻擊模式下平均路徑長度增大的速度相比之下也較快。也就是說，當故意移除重要性大的節點時，網絡中受影響的節點會不斷增多，網絡內的故障會像病毒一樣傳染開來。

（2）最大連通度。這一統計參數可以用來反映當網絡受到攻擊后，該網絡中依舊能正常工作的集團里包含的最多節點數。當網絡的最大連通度為1時，表示網絡處于正常狀態。當最大連接度不斷降低時，說明網絡在受到破壞后規模在不斷縮小，使得它無法將整個網絡的所有節點都建立起連接，節點之間的溝通力在下降，系統也處于魯棒性差的狀態。由上一節關于最大連通度的仿真結果可以分析出：

在隨機攻擊的模式下，盡管移出的節點在不斷增多，網絡的最大連通度卻變化不大，基本處于比較穩定的狀態，當該網絡中某幾個節點發生意外時，對整個網絡的最大連通度幾乎沒有影響；在蓄意攻擊的模式下，隨著移除節點的增多，網絡中沒有連接的單個節點的數目也在不斷增大，網絡的最大連通度越來越小，這說明網絡在面臨蓄意攻擊時極大可能會產生分裂。該參數的變化曲線與平均路徑長度呈現相似的趨勢。

兩種情況對比來看，因為隨機攻擊中移出的多是介數偏小的節點，保留了相對重要的節點，所以對于整個網絡的性能影響并不明顯，依然保持較好的魯棒性。而帶有針對性的蓄意攻擊則會移出介數偏大的節點，隨之而來的與其有連接的節點都會受到干擾甚至破壞，這也導致了網絡中單個節點的出現，使整個網絡魯棒性變差。

（3）介數。在設定蓄意攻擊時，便是依次移除介數值大的節點，再對整體進行分析，研究介數對于研究整個復雜網絡的魯棒性來說是必不可少的一步。在網絡中，其他的統計參數會隨著介數高的節點的消失發生相對而言很大的變化。在仿真實驗中無論是哪種攻擊，在移除節點后整體網絡的介數都會產生一定變化，不過顯然蓄意攻擊情況下變化更劇烈些。在故意移除較多的介數數值高的節點時，整體介數值也變大了許多。

盡管有眾多研究復雜網絡魯棒性的參數和方法，依然無法將真實網絡的實際情況完全表現和擬設出來。許多實際的網絡在運轉的同時也在不斷地變化著，并且可能產生干擾的因素也是數不勝數，每一個因素都會帶來無法預知的后果。所以本文僅是構建出了簡單的中國民航網絡用于魯棒性的演化模型，并對其進行兩種干擾模式下的理論數據分析，協助產生更規范化的民航網絡。

5.3 綜合分析

經過上述分析，中國民航網絡在隨機攻擊后各項評價指標均變化不大，但在蓄意攻擊后平均路徑長度迅速增加，最大連通度大幅度下降，并且整體介數值也發生了較大變化。也就是說，面對隨機攻擊時中國民航網絡表現出明顯的魯棒性，而當蓄意攻擊介數值較大的節點時，網絡的魯棒性較差。

6 結論

本文選用中國民航網絡為基礎模型，以復雜網絡理論為基礎對其進行魯棒性分析。通過建立網絡模型，分析了其平均路徑長度和度分布等統計特性，得出其具備小世界特性、但更多地體現無標度特性的結論。在確定兩種干擾措施和三個評估指標后，進行仿真實驗。實驗中隨機攻擊時依次隨機選取一定量的節點移除，蓄意攻擊時按介數值從大到小排序并依次移除一定量節點，最后利用統計參數分析中國民航網絡魯棒性。結果表明，隨機攻擊對網絡的魯棒性沒有太大影響，但蓄意攻擊某些介數大的節點時網絡的平均路徑長度增大，最大連通度變小，魯棒性明顯變差。

在實際運轉的過程中，需要重點保障核心機場的正常運行，防止蓄意破壞的發生影響網絡全局。本文實驗分析所得出的結果，可以為中國民航網絡的標準化和規范化提供參考，促進民航業進一步的發展。