航空網絡層次結構對航班延誤擴散的影響

The Impact of Aviation Network Hierarchy on Flight Delay Spread

HOU Zelin，" YAO Hongguang" （School of Air Transport， Shanghai University of Engineering Science， Shanghai 201600， China）

摘" 要：航班準點率低，航班延誤班次多是我國民航業的現狀，其中航班延誤的擴散嚴重制約了航空運輸業的發展。文章借助模擬航空網絡和k-core方法分析航空網絡的社團層次結構，通過仿真發現，在延誤擴散過程中，初始延誤節點的度值越大，所造成的延誤擴散的影響也越大；且延誤擴散影響最大的是在核心層，核心層節點在網絡中與其他節點聯系緊密，度值大，故延誤擴散的影響最嚴重；中間層和邊緣層的節點大多通過與核心層節點連接造成大范圍的延誤擴散。

關鍵詞：航空網絡；延誤擴散；社團結構；k-core

中圖分類號：F560文獻標志碼：A

DOI：10.13714/j.cnki.1002-3100.2023.19.019

Abstract： The low flight punctuality rate and many delayed flights are the current situation of China's civil aviation. Flight delays seriously restrict the development of air transport industry. In this paper， the community structure of aviation network is analyzed by means of simulated aviation network and Newman fast algorithm. Through simulation， it is found that in the process of delay diffusion， the greater the degree of initial delay node， the greater the impact， and most of the affected nodes are closely related to each other， that is， the delay diffusion is more likely to occur between nodes within the community.

Key words： aviation network; delay spread; community structure; k-core

0" 引" 言

民航業是我國國民經濟的重要基礎產業，是綜合交通運輸體系不可或缺的部分，其發達程度體現了國家的綜合實力和現代化水平。然而，隨著我國民航業的快速發展，航空延誤也接踵而至。造成航班延誤的因素有很多，但航班延誤擴散占據一大部分，延誤擴散往往會波及更多機場和航班，也就造成延誤總時長越大。

當一個航班或機場受到擾動，這個擾動就會迅速波及到運輸網絡的其他組成部分[1-2]。Ahmadbeygi等提出可以采取增加航班在機場的周轉時間的方式來減少延誤向下游機場的傳遞[2]。Bruno Campanelli等對比美國航空運輸網絡與歐洲航空運輸網絡分析，由于航班時刻表問題或外界干擾導致的延誤傳播，發現對比空中交通流量管理（Air Traffic Flow Management，ATFM）時隙優先級系統，先到先服務（First Come First Served，FCFS）的調度機制會產生更大的交通擁塞[3]。Welman等計算了美國51個機場的延誤乘子，并且估計了機場容量增大時系統延誤的降低[4]。很少有學者研究航空網絡社團結構對航班延誤擴散的研究，在社團方面眾多學者都有研究，Newman[5]提出快速模塊度優化FN算法，Blondel等人[6]提出了采用貪婪方法進行局部優化的層凝聚方法Louvain算法，Raghavan等人[7]將標簽傳播思想[8]應用于社團發現任務，提出基于標簽傳播的社團發現算法。

從網絡層次結構研究航空網絡航班延誤擴散，可以發現航空網絡的層次結構以及層次中節點的分布狀況，通過仿真分析，可以有效防治航班延誤以及延誤擴散的發生。

1" 模擬航空網絡的建立

本文所研究的中國航空網絡的數據來源于攜程網（http：//www.ctrip.com）和“飛常準”網站（http：//www.variflight.com/），包括港、澳、臺地區，共有241個城市、4 074架次直達航班。

本文所研究的航空網絡是將同一個城市的不同機場合并為一個并用城市名字進行命名。因此，本文把統計的241個城市機場作為中國航空網絡節點，城市對之間的存在航線作為邊，構建一個無向無權的中國航空網絡模型G=V，E，其中V是網絡中點的集合，E是網絡中邊的集合。如果城市對之間存在聯系，則城市對節點之間存在航線連接，否則不存在連接，即如果兩個節點之間存在連接，則e=1；如果沒有連接存在則為0。由此可以得到城市對節點之間的航班數據的鄰接矩陣，用一個241*241的鄰接矩陣A來表示。

因為真實的航空網絡數據繁雜，進行延誤擴散仿真時間長，故根據真實航空網絡用Pajek軟件進行模擬，最終得到的模擬航空網絡如圖1所示。

從圖1中可知模擬航空網絡的連接情況，模擬網絡中有41個節點，節點之間共有125條航線。根據鄰接矩陣可以知道航線的方向，據此可以生成125個航班進行后續的仿真研究。

2" 模擬網絡的社團發現

2.1" k-core層次分析算法

針對于網絡的社團發現有很多種，但對于航空網絡的復雜性以及適用于本文的航班延誤擴散的社團發現首選是基于度值的社團結構發現。針對于度值的社團網絡發現有很多種，如K-派系、K-派系社團、k-core等。其中k-core能夠發現網絡中的節點核度，能夠直接基于度值了解網絡中每個節點對于其他節點的連接性。再通過K核分解對模擬航空網絡進行社團層次劃分。這在研究航班延誤擴散的過程中，能夠直接發現社團層次對航班延誤擴散的影響。

k-core算法發現模擬航空網絡的社團層次具體如下：

在一個網絡中k-core指的是要反復刪除那些度值小于K的節點之后，所剩余的節點構成的子圖[9]。或者可以說，子圖中的每個節點的度值都不小于K。

節點的核數表示包含這個節點的最深的核，即系欸但那存在與K核中，但是在K+1核中被剔除，則這個節點的核數為K。核數的最大值就是整個網絡的最大核數，也叫最高核數[10]。核數通常可以反映節點的連通性，在進行研究時可能出現節點度很大，但是核數很低，這說明節點的連通性低，需要進行K核分解剔除這些節點，從而探索網絡中的核心層。

K核分解的過程是從外到內延伸擴展進行的，最小的核在最外面，最大的核在最內層。通過K核分解，逐層分解，揭示網絡中的層次結構。其中在K核中被刪除的節點成為K-1層。在網絡中反復刪除度值為1 的節點，那么刪除的節點就是所謂的0-層；然后，再把子圖中度值為2的全部節點反復都刪除掉，這時網絡中的所有節點的度值都大于2，那些刪除掉的節點就是1-層；依此類推，一直到網絡中的節點不可以在刪除，此時，剩余節點所構成的子圖就是網絡的最高層[11]。

2.2" 模擬航空網絡的層次網絡發現

將上文中模擬航空網絡的0～1鄰接矩陣B輸入到UCINET軟件中進行k-core分析，以便可以計算模擬航空網絡的機場核心，計算結果表明，模擬航空網絡的最大核度為5。且隨著核度的增加，網絡中各層的節點和邊緣節點的消失如表1所示。

根據表1還可以得到，最高核5-核中的13個節點就是核心層。而在1-核剔除節點變成2-核中共剔除12個節點，在2-核剔除節點變3-核中只剔除了3個節點，且所移除的邊所占相近，因此，可以把這15個節點作為邊緣層。中間層為4-核和5-核中所剔除的13個節點。整理成如表2所示。

根據表2可以看出，在核心層中節點之間的連接最多，且中間層和邊緣層中節點之間的連邊數遠比核心層網絡中的連邊數少；而且還可以看出，中間層、邊緣層內部節點之間連邊數之所以少，是因為中間層、邊緣層的節點大多跟核心層的節點之間進行連接，通過中轉到達其他節點，也就是說，中間層、邊緣層內部之間的節點聯系少，主要通過和核心層聯系，從而達到其他節點。

依據劃分好的網絡層次中的節點數量和每個層次中的連邊數量，可以整理出每個層次的鄰接矩陣，把鄰接矩陣依次導入UCINET軟件中，轉換成可直接讀取的數據，進行數據可視化，得到結果如圖2所示：

在圖2中能夠看出，核心層、中間層、邊緣層三個不同層次內部節點之間的連接情況。其中核心層內部節點之間的連接最多，中間層次之，邊緣層內部節點之間連接最少，節點之間幾乎不存在聯系。說明在模擬航空網絡中核心層中的節點聯系最為緊密，中間層次之；而且中間層、邊緣層的連接情況少，說明中間層、邊緣層的節點較多的與核心層的節點之間有連接，可以說核心層占據整個模擬航空網絡的中心地位。

3" 延誤擴散仿真分析

3.1" 航班信息的設定

在實際生活中，初始航班延誤是通過各類介質在包括自身機場在內的節點中影響其他航班，從而發生航班延誤擴散。在關于航空網絡結構對延誤擴散造成怎樣的影響的研究中，本文通過延誤擴散的機場總數、擴散涉及的航班數量及擴散造成的延誤總時長這三個指標來衡量其影響程度。所以本文首先要確定各節點機場的航班信息、初始延誤信息以及機場服務能力信息等。

（1）航班時刻表

航班時刻表中包括序號、航班代碼、始發機場、始發時間、目的機場、降落時間、飛行時間等信息，其中始發機場、始發時間是飛機起飛是否受其他延誤航班影響判斷的關鍵因素，若二者同時在延誤航班的影響范圍內，則該航班很有可能受到影響，使延誤擴散；同理，目的機場與降落時間則是判斷該航班是否在降落時受延誤影響的重要條件，若受影響也就意味著該航班無法在原定時刻降落在目的機場，則必須通過推遲起飛等方式處理，從而發生延誤擴散。因此，航班時刻表是進行航班延誤擴散影響研究的基礎信息。其具體形式如表3所示。

（2）航班初始延誤時刻表

初始延誤時刻表中包含的信息除了上述航班時刻表中的信息，還包含延誤時間、影響延誤時間始和影響延誤時間末等信息。其中初始延誤航班的影響時間始末是該表中的關鍵信息，通過該影響區間判斷航班時刻表中是否有航班會受到初始延誤影響。具體的航班初始延誤時刻表包含內容和形式如表4所示。

（3）機場服務能力

機場服務能力指的是機場中能提供飛機起飛和降落的能力，即在一定時間段內機場能夠供給飛機正常起飛和降落的最大能力。具體表格信息如表5所示。

在上述的三個信息表已知的情況下，通過初始延誤表可以確定航班影響的機場和影響時間區間，再通過航班時刻表來查看在這一時間區間內可能受影響的航班，根據受影響機場的服務能力，確認延誤擴散航班，最終輸出延誤航班數量、延誤機場數量和延誤總時間。

3.2" 仿真系統的建立

對仿真系統進行描述：

（1）仿真開始時，其中的延誤總時長T=0；延誤航班數量H=0；延誤機場數量A=0。根據“延誤時刻表”確定航班初始延誤信息。

（2）查看航班時刻表，判斷延誤航班對其他航班的影響是否大于15min。輸出影響時間大于或等于15分鐘的航班數量N；查找機場服務能力表，判斷并確定受影響的航班：即N小于等于起飛能力時，不受影響；N大于起飛能力時，受影響，且受影響航班為N減去起飛能力。將受影響航班編入延誤表，更新信息。

（3）判斷航班降落影響：確定航班降落影響時間區間T，T。判斷在該時間范圍內航班時刻表中是否存在目的機場與初始延誤航班相同的航班，并輸出符合條件的航班數量值為N。查找機場服務能力表，比較并確定受影響的其他航班。當N小于等于機場降落能力時，機場其他航班不受影響；當N大于機場降落能力時，機場其他航班受影響，此時，受影響的航班數量

=N-機場降落能力。將受影響航班編入延誤表，更新信息。將受延誤擴散影響的航班編入厭惡表，刪除處理掉的延誤航班；輸出T、H、J。

（4）重復步驟（1）、（2）、（3），一直到延誤表處理完畢。

3.3" 仿真結果

根據上文基于K-核分析模擬航空網絡中得出的網絡層次，對核心層網絡進行航班延誤擴散仿真計算和結果分析。針對核心層網絡，在模擬航空網絡中找出核心層中的13個節點和59條邊；在航班時刻表中找到核心層網絡所包含的航班，設置初始延誤航班信息，進行延誤擴散分析。

假設初始航班的延誤均因為天氣、軍事活動等條件引起的，則必會引起航班延誤在網絡中進行傳播擴散。把初始延誤航班的延誤時間設置為70分鐘，初始航班延誤表如表6所示。

在航班初始延誤表中，知道初始延誤航班的代碼、延誤時間、起飛以及降落時，假設同一機場的起飛服務能力和降落服務能力均為1，各航班根據航班順序進行起飛和降落，且飛機不通過加減速來改變飛行時間；根據選擇的初始延誤航班設置延誤時間（70min），在表6中給出影響時間的開始和影響時間末均為降落機場的影響時間；實際計算中還有起飛機場的影響時間。采用延誤擴散邏輯框架圖所示的步驟進行延誤擴散，且根據擴散情況持續更新航班時刻表，計算出延誤擴散的總時長、受影響的節點機場以及受影響的航班數量，其中受影響的一個航班可以影響兩個機場節點，不把同一個受影響的機場節點總結為一個進行統計（如：初始延誤航班為MU4567，由V1飛向V3，受影響的航班有兩個，這兩個航班分別由V5飛向V3和V8飛向V3，這時節點為4，不把V3總結為一個機場節點進行統計）。將航班延誤擴散結果整理如表7所示。

中間層和邊緣層的仿真結果如表8、表9所示：

將各個層級中的節點引起的延誤擴散仿真結果作圖，因為篇幅原因，本文只給出平均延誤擴散總時長以及影響的節點數量的圖，具體如圖3所示。

從圖3可以得出，在核心層、中間層、邊緣層相同的情況下，不同的節點作為初始延誤節點，其所造成的影響也不相同，一般來說，相同層級中的節點的度值越大，其所對應的核度也越大，在層級中連接的節點也越多，故作為初始延誤節點進行的仿真結果也就比其他節點造成的影響大。對比核心層、中間層和邊緣層節點作為初始延誤節點時，核心層節點造成的延誤擴散要比中間層、邊緣層造成的影響大；在中間層、邊緣層節點造成的延誤擴散幾乎可以忽略不計，但在核心層因為節點度值大，幾乎都會影響到其他節點。

4" 結" 論

通過構建中國航空網絡的模擬模型，運用k-core方法進行網絡層次分析，從而進一步通過仿真研究航班延誤在網絡中的擴散，最終得到如下結論：

（1）在核心層、中間層、邊緣層相同的情況下，不同的節點作為初始延誤節點，其所造成的影響也不相同。總體來說，初始延誤節點的度值越大，其延誤擴散的影響越嚴重。

（2）延誤擴散影響最大的是在核心層，核心層節點在網絡中與其他節點聯系緊密，度值大，故延誤擴散的影響最嚴重；中間層和邊緣層的節點大多通過與核心層節點連接造成大范圍的延誤擴散。

參考文獻：

[1]" BEATTY R， HSU R， BERRY L. Preliminary evaluation of flight delay propagation through an airline schedule[J]. Air Traffic Control Quarterly， 1998，7（4）：259-270.

[2]" AHMADBEYGI S， COHN A， GUAN Y， et al. Analysis of the potential for delay propagation in passenger airline networks[J]. Journal of Air Transport Management， 2008，14（5）：221-236.

[3]" CAMPANELLI B， FLEURQUIN P， ARRANZ A， et al. Comparing the modeling of delay propagation in the US and European air traffic networks[J]. Journal of Air Transport Management， 2016，56：12-18.

[4]" WELMAN S， WILLIAMS A， HECHTMAN D， et al. Calculating delay propagation multipliers for cost-benefit analysis sponsor： The federal aviation administration[Z]. 2010.

[5]" NEWMAN M E J. Fast algorithm for detecting community structure in network[J]. Physical E， 2003，69（6）：066133.

[6]" BLONDEL V D， GUILLAUME J L， LAMBIOTTE R， et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mecha-nics： Theory and Experiment， 2008，2008（10）：10008.

[7]" RAGHAVAN U N， ALBERT R， KUMARA S R， et al." Near linear time algo-rithm to detect community structures in large

-scale networks[J]. Physical Review E， 2007，76（3）：036106.

[8]" ZHU XIAOJIN， GHAHRAMANI Z. Learning from labels and unlabeled data with label propagation， CMU-CALD-02-107[R]. Pittsburgh， PA： Car-negie Mellon University， 2002.

[9]" Z-M REN， J-G LIU， F SHAO， et al. Analysis of the spreading influence of the nodes with minimum K-shell value in complex networks[J]. Acta Physica Sinica， 2013，62（10）：108902.

[10]" M ZHANG， S GE， Y JIA， et al. Analysis of cohesive characteristics in scientific collaboration networks based on k-core[J]. Systems Engineering-Teory amp; Practice， 2020，40：1821-1831.

[11]" L HUANG， Y-D ZHAO， L MEI. Research on multi-sided market competition of social media personal data resource-an empirical analysis based onk-core network[J]. Soft Science， 2019，33：1-7.