航空公司超網絡的拓撲結構與魯棒性分析

術永昊，郭進利

（上海理工大學 管理學院，上海 200093）

0 引 言

截止到2020 年，中國境內運輸機場（不含香港、澳門和臺灣地區）共有241 個，其中定期航班通航機場240 個［1］。這些機場包含許多航空公司，其中東航2020 年旅客運輸量實現7 458 萬人次［2］；南航運輸9 700 萬人次，全年航班正常率連續五年在三大國有航司中排名第一［3］；廈門航空運輸2 141 萬人次，是全球唯一保持34 年持續盈利的航司［4］。隨著中國航空公司數量的不斷增加，沖突也在加深，航空公司所面臨的突發事件所帶來的一系列反應對航空公司超網絡的損毀程度，嚴重影響航空運輸的高效性和經濟性。因此本文對航司超網的拓撲結構與魯棒性進行分析，并提出相應的優化網絡建議。

1 文獻綜述

在大多數拓撲結構中，航空網絡可以由一組節點（機場或航點）和鏈接（航班線路或航線段）組成，其中鏈接表示兩個節點之間的交互。在文獻中，許多作者廣泛使用復雜網絡理論應用于相關領域的研究，得出對航空網絡靜態和動態方面的影響。Song and Yeo 采用復雜網絡方法，研究了全球1 060個機場的航空運輸網絡，采用若干中心性指標來識別具有高中心性指標的機場，并分析國家層面的航空網絡連接結構［5］；Lin and Ban 從中心性分布和結構屬性兩個方面分析了1990～2010 年美國航空網絡的時間演化，研究發現關鍵結構特征形成于航空網絡發展的早期階段，經濟和地緣政治因素是決定航空網絡發展的主要因素［6］；Kim 和Yoon 研究了亞洲東北部航線網絡，將航空網絡描述為航線段網絡，通過網絡魯棒性分析，發現航空網絡在一組高中心性的關鍵節點上比隨機故障更容易受到攻擊，加強了區域協調以減輕各種風險的必要性［7］；吳佳益通過對比歷年中國航空網絡模型，運用多層復雜網絡理論建立以航司為節點的中國航空多層網絡，并分析其結構特征與演化規律［8］。

通過上述分析發現，當前關于航空方面的研究文獻大多數是基于復雜網絡方面的觀點，但復雜網絡在描述協同關系方面有一定的局限性，而在超網絡中每條超邊可以包含多個節點，并且超邊又可以表示節點之間的的共同作用。例如：索琪總結了基于超圖的超網絡的相關概念以及靜態拓撲指標［9］；陸睿敏將公交站點視為超邊，線路視為節點，構建了公交超網絡，并分析其網絡特性，最后通過分析網絡的抗毀性得出隨機攻擊的穩定性要強于蓄意攻擊［10］；胡楓等人以蛋白質為節點，復合物為超邊構建了超網絡，分析網絡的結構特征，識別出關鍵蛋白質，并對其數據進行了驗證［11］；王志平等人通過利用超網絡，將輿論中的關鍵詞作為節點，關鍵詞構成的話題作為超邊，構建了輿論演化動態的超網絡模型，得出節點超度符合冪律分布這一特征的結論［12］。

本文將航空公司作為節點，運輸機場作為超邊，可以更好地體現各航空公司在機場中的分布情況，分析組成的航空公司超網絡的拓撲特性與穩定性，針對網絡的抗毀性提出合理的優化建議。

2 超網絡的相關概念

網絡中的節點類型越來越多樣，之間的相互作用也越來越復雜，而超網絡的提出給出了一種對于高階相互作用最普遍、最不受約束的一種表達。超網絡一般分為兩種，基于網絡的超網絡，基于超圖的超網絡。前者關注現實網絡多層、多級、多維網絡流的復雜特性，適合解決多層次網絡的建模問題；后者以超圖理論為基礎，超圖中每條超邊包含多個節點，節點之間的相互聯系可以通過超圖清晰的表達。本文選擇基于超圖的超網絡構建模型，研究機場中各航司的拓撲結構及其穩定性。

2.1 超圖的概念

超圖是由節點集V＝｛v1，v2，…，vn｝和超邊集E＝｛E1，E2，…，Em｝ 組成，其中ei≠Φ（i＝1，2，…，m）［13］。超圖H＝｛E1，E2，…，Em｝，同時還滿足：Ei?Ej?i＝j。如果某一條超邊Ep（p＝1，2，…，m）同時包含節點vi和vj，即這兩個節點歸屬于同一條超邊，則稱vi和vj（i，j＝1，2，…，n）是鄰接的，稱Ep與vi（或vj）相關聯。若Ep∩Eq≠Φ，即兩條超邊的交集不為空，則稱超邊Ep與Eq（p，q＝1，2，…，m）鄰接。

超圖的示例如圖1 所示。節點集V＝｛v1，v2，v3，v4，v5，v6，v7，v8｝，超邊集E＝｛E1，E2，E3，E4｝，其中，E1＝｛v1，v2，v5，v6｝，E2＝｛v2，v3，v6｝，E3＝｛v4，v5，v6｝，E4＝｛v7，v8｝。圖1 中E1、E2、E3、E4所包含的節點數不全相同，即為非均勻超圖。如果每條超邊中的節點數相同，則稱為均勻超圖或一致超圖。

在超圖中也可以用關聯矩陣來描述節點與超邊的關系。如果節點vi與超邊Ej相關聯，則第i行和第j列中的項為1，否則為0［14］。于是，得到圖1 的關聯矩陣Im×n，其中每一行代表一個節點vn，列代表每一條超邊Em，如圖2 所示。

圖1 非均勻超圖Fig.1 Non uniform hypergraph

圖2 關聯矩陣Fig.2 Incidence matrix

2.2 超網絡的概念

假設Ω＝｛（V，E）│（V，E）是有限超圖｝，G是從T＝［0，＋∞）到Ω的映射，對于任意給定的t≥0，G（t）＝（V（t），E（t））是一個有限的超圖，指標t通常被認為是時間。超網絡｛G（t）│t∈T｝是指超圖的集合，從超網絡的定義可以看出：超網絡是超圖概念的推廣，超網絡更多的是用來描述網絡的動態特征［15］。

2.3 拓撲參數的定義

（1）節點度：超網絡中，超邊包含該節點，則視超邊連接了這個節點。同一條超邊的節點視為相互連接，包含相同節點的兩條超邊視為相互鄰接。節點度指與節點vi鄰接的其它節點數量，記為di［16］。在圖1 中，d1＝3，d2＝4，d3＝2，d4＝2，d5＝4，d6＝5，d7＝1，d8＝1。

（2）節點超度：節點超度定義為包含節點vi的超邊個數，記為dH（vi）［17］。在圖1 中，dH（v1）＝1，dH（v2）＝2，dH（v3）＝1，dH（v4）＝1，dH（v5）＝2，dH（v6）＝3，dH（v7）＝1，dH（v8）＝1。在圖1 的關聯矩陣中，第n行元素之和也可以計算出節點超度。

（3）超邊度、超邊超度：超邊度是指超邊所鄰接的其它超邊個數，即與該超邊存在公共節點的超邊數，記為dhd（Ei）。超邊超度是指超邊所包含的節點個數，記為ds（Ej），在圖1 的關聯矩陣中，第m列元素之和也可以計算出超邊超度。

（4）聚類系數：聚類系數反映了節點的鄰域密度［18］。節點i與ki個節點通過超邊直接相連，ki個節點間實際存在的超邊數為Ni，這ki個節點間可能存在的最大超邊數為ki（ki－1）∕2，那么節點i的聚類系數Ci為：

（5）平均路徑長度：網絡中從一個節點（超邊）到達另一個節點（超邊）所需距離可體現網絡的效率或能力。超網絡中兩超邊的距離是指超邊之間最少的連接數，定義超網絡平均距離長度為任意兩條超邊距離的平均值［19］。

3 航空公司超網絡模型構建與拓撲特性分析

3.1 航空公司超網絡模型

本研究的數據來自中國民航局（http：／ ／www.caac.gov.cn／）以及各航空公司官網。選取2020 年民航機場生產統計公報中吞吐量前二十的民航機場：廣州白云、成都雙流、深圳寶安、重慶江北、北京首都、昆明長水、上海虹橋、西安咸陽、上海浦東、杭州蕭山國際機場等作為超邊，以機場中運營的國內東方航空、國際航空、深圳航空、山東航空、吉祥航空等44 家航空公司作為節點，構建航空公司超網絡模型示意圖，如圖3 所示。

圖3 航空公司超網絡模型示意圖Fig.3 Diagram of airlines hypernetwork model

3.2 超網絡拓撲特性分析

3.2.1 度分布

度分布P（di）表示在節點度值分布空間內，節點度為di的節點數量占所有節點數量的比例分布情況。航空公司超網絡包含44 家航空公司，超網絡的度值分布如圖4 所示，平均度＜di ＞為36.341，說明每家航司大約與36 家航司存在聯系，平均度值較大，說明大多數航司通過機場相互連接，航空公司間的緊密程度較高。度值最小為15，度值最大為43。航司超網絡中度值較大的國際航空、東方航空、深圳航空、海南航空、山東航空等相連的航司較多，因此在網絡中起到關鍵中心的作用。

圖4 航空公司超網絡節點度值分布Fig.4 Degree distribution of airline hypernetwork nodes

3.2.2 超度分布

超度分布P（dH）表示在點超度值分布空間內，點超度為dH的節點數量占所有節點數量的比例分布情況。超網絡的超度分布如圖5 所示，平均超度＜dH ＞為10.205，說明每家航司被10 座機場包含，超度值越大，說明該節點在超網絡中具有關鍵作用，也是網絡中脆弱性節點，需要加強對航司的運營保護，保證整個網絡的安全。

圖5 航空公司超網絡節點超度值分布Fig.5 Hyperdegree distribution of airline hypernetwork nodes

衡量網絡中航司的重要性時，需要同時考慮節點的點度與超度，因此本文做散點圖來進行分析，如圖6 所示。當網絡中某個節點的點度和超度較大，那么該節點在網絡中較為重要，圖6 中位于右上角的節點：東方航空、國際航空為網絡中最關鍵的節點。

圖6 超網絡點度與點超度的散點圖Fig.6 Scatter graphs of degree and hyperdegree

3.2.3 超邊超度

超邊超度ds（Ej）在超網絡中指每座機場所包含的航司數量，在航空公司超網絡中超邊超度的分布情況如圖7 所示。超邊超度較大的機場，如：長沙黃花、海口美蘭、昆明長水等是中國航空公司超網絡中較為重要的機場。

圖7 超網絡超邊超度分布Fig.7 Hyperedge hyperdegree distribution of hypernetwork

3.2.4 平均路徑長度和聚類系數

本文節點數和超邊數分別代表航空公司和民用運輸機場的數量。如果兩家航空公司同時出現在一個超邊中，這時認為這兩家航空公司是有連邊的。使用Gephi 軟件，將超網絡轉化為普通的復雜網絡，形成航空公司超網絡的投影網絡，如圖8 所示，計算得出網絡的平均路徑長度為1.177 和聚類系數為0.904。

圖8 航空公司超網絡的投影網絡Fig.8 Projection network of airline hypernetwork

3.2.5 航司網絡的特性

由于航空公司超網絡的平均路徑長度與聚類系數接近于1，說明網絡的航司與航司之間傳播迅速，節點分布較為密集，大多數節點可以經過少量的邊到達另外某個節點。這意味著航空公司超網絡所對應的投影網絡極為稠密，連通程度高，節點近似全連接，在這種網絡上傳播的速度極快，節點與節點之間可以通過某幾個節點相互到達，因此該航司超網絡具有小世界特性。

另外一種特性則是網絡中的冪律分布，其顯著特征是大部分節點的節點度值較小，少部分節點度值較大，也就意味著絕大多數的事件重要性都很小，只有極少數的事件重要性很大，而冪律分布又稱無標度分布。根據網絡中的數據分析航空公司超網絡的節點的雙對數度分布如圖9 所示，得到擬合冪函數，式（2）：

圖9 雙對數坐標下節點度累計分布圖Fig.9 Cumulative distribution of node degree in double logarithmic coordinates

同時得到圖10 的節點超度的累計概率分布圖，擬合冪函數，式（3）：

圖10 雙對數坐標下節點超度累計分布圖Fig.10 Cumulative distribution of node hyperdegree in double logarithmic coordinates

由式（2）可知，節點度累計概率分布的指數為－3.280 1，小于0，并不服從冪律分布的定義，并且在式（3）節點超度的累計概率分布函數中指數為－0.637，同樣小于0，因此認為航空公司超網絡的拓撲結構不具備無標度特性。

通過分析航空公司超網絡的拓撲結構指標，認為航空公司超網絡具有明顯的小世界特性，網絡本身節點通過較少的轉換就能連通，網絡聚集程度高，連通效率高。

4 航空公司超網絡魯棒性分析

通過分析航空公司超網絡的基本拓撲性質，進而了解航空公司在各座機場的分布。現實民用運輸機場的穩定性及抗毀能力不僅會受到航空公司的影響，同樣也會受到外界環境對網絡的影響，如航空器故障、危險物品污染、挾持、爆炸物威脅等。因此本文從網絡的魯棒性指標出發，分析不同情況下航空公司超網絡的穩定性。

4.1 魯棒性指標

網絡魯棒性直觀地來說是指網絡在受到外部不確定干擾或者內部不穩定因素時，能夠保持其功能正常工作的能力［20］。在航空公司超網絡中，魯棒性體現在民用運輸機場在遭遇突發事件時保持其穩定的能力，通常采用的衡量指標包括聚類系數、全局網絡效率、最大連通子圖和平均最短路徑等。全局網絡效率用來衡量網絡的有效性，聚類系數通常用來衡量具有相同鄰居節點之間的連通性，所有的系數都在0－1 之間，其值高說明聚類系數高，網絡的連通性強。因此本文選取全局網絡效率和聚類系數作為航空公司超網絡的魯棒性指標進行分析。

聚類系數公式如式（1），節點聚類系數的變化幅度大小可以衡量網絡的魯棒性。全局網絡效率的公式如式（4）：

其中，N表示超網絡中航空公司的數量，dij表示節點與節點間的距離（最短路徑）。

由于本文為非加權超網絡，因此節點與節點間的最短距離為兩節點間的最少超邊數量。

4.2 攻擊策略

本文對于航空公司網絡的魯棒性分析，主要體現在隨機攻擊和蓄意攻擊兩種攻擊策略對網絡效率與聚類系數的變化情況，同時對網絡的魯棒性進行評價優化。具體來講，航空公司超網絡可能會面臨如危險物品污染、臨時取消航班、改簽等隨機攻擊，或者發生爆炸物威脅、挾持等蓄意攻擊事件，分析其穩定性，并提出優化意見。

4.3 魯棒性分析

4.3.1 隨機攻擊

將超網絡中每家航空公司進行隨機排序，依次選擇4 個節點進行刪除，計算網絡的網絡效率與聚類系數的指標。為了保證實驗的準確性，該實驗重復隨機進行50 次，取50 次實驗中的平均值作為最后結果。

4.3.2 蓄意攻擊

為了分析基于蓄意攻擊策略的航空公司超網絡的魯棒性，首先將超網絡中節點的度和超度從大到小排序，依次攻擊，再用同樣的方法計算網絡的魯棒性指標。本文分析隨機攻擊與蓄意攻擊對航空公司超網絡的網絡效率與聚類系數所產生的影響，仿真計算這兩種策略下網絡的聚類系數與網絡效率的變化曲線，如圖11 和圖12 所示。

圖11 隨機攻擊與蓄意攻擊聚類系數對比Fig.11 Comparison of clustering coefficient between random attack and deliberate attack

圖12 隨機攻擊與蓄意攻擊網絡效率對比Fig.12 Comparison of network efficiency between random attack and deliberate attack

當某家航空公司或者機場受到攻擊時，網絡中節點和超邊數量的減少，節點的鄰居節點之間互連的概率同樣也會減少，導致航空公司超網絡的聚類系數降低。又由于網絡的連接程度降低，兩家航空公司無法進行中轉或改簽服務，最終導致網絡的全局效率降低。

在圖11 中，當節點失效數逐漸增加時，基于節點超度攻擊的網絡聚類系數下降最快，節點度攻擊次之，說明以某機場為攻擊對象進而攻擊其它機場，導致網絡的聚類系數下降快于點度攻擊，點度攻擊通過攻擊航空公司來破壞網絡，因為本身網絡是小世界網絡，其中一家航空公司被攻擊，與之相互有連接關系的航空公司之間沒有影響，因此，點度攻擊對聚類系數的影響要小于點超度攻擊，而隨機攻擊下降最慢。網絡被隨機攻擊36 個節點后，開始呈現斷崖式下降，當網絡的所有節點全部失效后，網絡的聚類系數為0；而點超度攻擊在節點失效數為24 時開始下降，直到失效28 個節點時，網絡的聚類系數為0。因此對于網絡的聚類系數而言，隨機攻擊的魯棒性要強于蓄意攻擊。

在圖12 中，網絡的點度攻擊和點超度攻擊對全局效率的影響相差不大，基于隨機攻擊的魯棒性要優于蓄意攻擊，隨機攻擊36 個節點網絡的全局效率呈斷崖式下降，當達到40 個失效數時，網絡已達到崩潰狀態。而蓄意攻擊在節點失效數達到28 時，網絡的全局效率為0，網絡完全失去作用。

最后，由于圖11 中網絡的全局效率與聚類系數變化情況在隨機攻擊與蓄意攻擊對網絡抗毀程度方面的分析基本一致，說明了上述分析結果更加可信。

5 結束語

本文運用超網絡理論構建了航空公司超網絡模型，分析模型的拓撲結構與特性，以及超網絡模型的魯棒性。得出下述結論：

（1）航空公司超網絡中節點有較短的平均路徑與較大的聚類系數，具有明顯的小世界網絡特性，但并不是無標度網絡。網絡中各航空公司之間連接程度與聚集程度高；

（2）超網絡中東方航空、國際航空等航空公司具有較大的節點點度與點超度，說明這些節點對超網絡起著至關重要的作用；

（3）通過分析航空公司超網絡的魯棒性，超網絡在遇到隨機攻擊時具有較好的穩定性，對于網絡的聚類系數而言，點超度攻擊對網絡的破壞性要大于點度攻擊，而對于網絡的全局效率來說，點超度攻擊與點度攻擊對網絡的破壞性基本一致。

針對上述結論給出以下建議：

（1）目前中國的機場數量嚴重不足，是制約中國航空業發展的關鍵因素之一，對于航空公司數量較多的機場，如果條件允許，可以擴建機場規模，部分城市也可以考慮修建第二機場；

（2）對于超網絡超邊超度較大的城市，如：昆明、成都等。這些城市的旅游資源豐富，但受制于交通限制，旅游業的發展也較為滯后，如昆明長水國際機場所擁有的航空公司數量最多，但本地的交通并不發達，加大投入建設交通基礎設施，也可以給這座城市帶來新的生機；

（3）不斷加強機場的安全管理，提高航空設備的可靠性。對于節點度或節點超度較大的航空公司，需要加強員工的整體素質以及安全意識，在遇到突發事故或緊急事件時，需要保持沉著冷靜的態度做出準確判斷。