支線航空網絡節點的聚類與關鍵節點識別*

何 行 劉旺根 何 珊 趙振涵

（中國民用航空飛行學院 廣漢 618300）

1 引言

支線航空是全國航線網絡的重要組成部分［1］，對民航強國的建設有至關重要的作用，但支線航空也是長期困擾我國航空運輸業發展的一個話題。1988年和2000年分別提出小世界網絡和無標度網絡廣泛存在于現實世界，隨著復雜網絡特性的研究深入，節點重要度評價、節點聚類研究逐漸成為復雜網絡中的重要課題。

關鍵節點識別方法一般以復雜網絡本身屬性如度、介數、接近度、聚集系數等量化測度標準來評價網絡節點［2～4］。也有多指標融合評價，王鋒在文獻［5］中針對無權網絡，提出一種基于m 節鄰居節點的關鍵節點識別算法，綜合考慮了節點自身以及其m 階鄰接節點的度值以及介值重要度的貢獻程度。鄧紅星等［6］選用節點度和站點客流集散量等7個指標構建節點重要度評價體系，對哈爾濱市區道路網進行研究。ZHU Yanbo 等［7］以圖論為基礎對絲綢之路經濟帶鐵路網絡節點重要度進行研究，利用pajek 軟件仿真發現了其中3 個最關鍵節點。王超峰［8］認為節點重要度與機場本身交通經濟特性密切相關，并建立指標體系進行節點重要性評估。

聚類是機器學習領域中無監督學習的重要組成部分，聚類算法在工業界有重要的應用價值，在學術界也得到了廣泛的關注和研究［9］。常見的聚類分析方法有層次法、劃分法、基于網格法、基于密度法和基于模型法。本文采取DBSCAN聚類算法，DBSCAN 算法是一種經典的基于密度的聚類算法，最早是在《Science》期刊發表提出。DBSCAN 算法不需要預先指定聚類的簇數，能夠在含有噪聲的數據集中發現任意數量和形狀的簇［10］，具有可解釋強、可視化效果好、易于理解的優點。

目前的航空網絡性能研究都是基于復雜網絡拓撲結構展開的，對關鍵節點選取比較簡單，缺少完善的指標體系，且網絡性能的分析采用的指標比較單一。實際上，機場網絡節點的重要度還與機場及其所在地區屬性有關，綜合考慮多層指標使評估節點重要度變得合理化。

2 研究理論與依據

2.1 構建支線航空網絡模型

本文將年旅客吞吐量少于200 萬人次的機場定義為支線機場，而一端連接支線機場的航線定位為支線航線，所有支線航線組成支線航空網絡［11］。圖中共有節點數161 個，有2290 條邊，節點表示支線機場，連邊為兩個支線機場間有航線。利用Gephi 可視化軟件，繪制無向支線航空網絡圖，如圖1所示。

圖1 支線航空網絡圖（2020年數據）

2.2 機場節點重要度評估指標

機場關鍵節點的識別，對支線航空網絡的網絡性能分析十分重要。為建立完善的機場節點重要度指標體系，選取的指標應具有全面性、合理性，不僅要反應復雜網絡拓撲性質、還要與機場、機場所在地區屬性結合，故選取指標如表1。

表1 節點重要度指標體系

其中，V1節點度的計算公式：

i，j 表示節點，aij表示鄰接矩陣變量，ki表示度

點介數的計算公式

G 表示網絡，Dij(i)為經過節點i最短路徑的數量，Dkj便是節點k，j間最短路徑的數量。

2.3 指標數據來源

本文U1 指標已計算完畢，機場名采用四字代碼，數據來源于中國民用航空局預先飛行計劃管理系統，選擇2020年中國夏秋航季國內航班計劃表，具體包括161 個機場節點的2148 個航段數據。U2吞吐量指標數據來源于《從統計看民航》、設施可用性是對機場等設施綜合評估的結果。U3 指標從國家統計局官網獲得。綜上，支線航空網絡節點重要度指標部分數據匯總如表2。

表2 支線航空節點重要度指標

3 關鍵節點識別

3.1 熵權TOPSIS法

熵權TOPSIS 法是一種基于熵值法改進TOPSIS 法模型的賦權方法，能夠根據各指標值得變異程度所反映的信息量來確定權重［12］，并可通過評價對象和正、負理想解間的差異值來計算其與最優解的貼近度。

正向指標：

其中，i 表示年份，j 表示指標，i，j 均為非零的自然數。

第二步：指標歸一化處理，計算第i個指標在第j年的比重。

第三步：計算指標的信息熵ej：

第四步：計算各個指標的差異系數gj與指標權重wj：

第五步：構造加權規范化決策矩陣Vij，Vij=WjZij，Z=(Zij)m×n。

第六步：確定理想解和負理想解。決策矩陣V中元素Vij值越大表示方案越好。

理想解：

負理想解：

第七步：計算每個節點到理想解的距離Si+和到負理想解的距離Si-。

第八步：計算每個節點的相對接近度并排序，ci的值越大，表示節點越重要。

3.2 綜合評價結果

采用熵權TOPSIS 綜合評價法計算上述161 個節點，6 個二級指標的熵權分別是0.129323，0.294931，0.113405，0.255894，0.131915，0.156294。依據Ci 值大小進行排序，前三位分別是ZSLG、ZPDL、ZULZ 機場。選取前二十四名為關鍵節點，具體排序情況見表3。

表3 關鍵節點排序結果

4 節點聚類

4.1 DBSCAN算法

DBSCAN 是一種典型的以數據密度為基準劃分類的聚類方法的代表，可以在不需要設定初始值便可有效地自動發現目標簇個數，有效發現不同形狀的簇。給定一個樣本集是D＝（x1，x2，…，xm），參數（ε，Minpts）用來描述鄰域的樣本分布緊密程度。其中，ε 描述了某一樣本的鄰域距離閾值，Minpts 描述了某一樣本的距離為ε 的鄰域中樣本個數的閾值［13～14］。DBSCAN 算法的聚類過程可以表示為

輸入：E——半徑

MinPts——給定點在E 鄰域內成為核心對象的最小鄰域點數。

D——集合

輸出：目標類簇集合

方法：

1）判斷輸入點是否為核心對象；

2）找出核心對象的E 鄰域中的所有直接密度可達點；

3）Until 所有輸入點都判斷完畢。

4.2 基于DBSCAN算法的節點簇劃分

基于DBSCAN聚類的實現過程，設定關鍵參數Eps 和Minpts。從聚類數據樣本集X 中任意選取一點p，若該點的條件符合核心對象的判定，那么從該點密度可達的所有數據點成為一個聚類，而不屬于任何簇的數據點則被標記為噪聲點［15］。

圖2分別給出了不同Eps和Minpts組合時其聚合效果。通過對比，可以看到Minpts=10僅有一類，Minpts=8 聚類的精度較差僅有兩類，Minpts=5 時聚類噪聲點較多，Minpts=3聚類結果精度較高。通過觀察不同Minpts值的聚類結果，噪聲點的數目代表了精度的高低，因此，本文在DBSCAN 算法中選取的關鍵參數為Eps=0.15，Minpts=3。

圖2 DBSCAN簇分類結果

聚類結果如表4，算法將節點分為了4 個簇。第一簇中有8 個機場，分別是洛陽、大理、瀘州、常德、茅臺、舟山、赤峰、阜陽，與熵權TOPSIS 法計算出的排名基本一致，證明算法的準確性。

表4 最終聚類結果

5 結語

基于圖論和復雜網絡理論，以2020年夏秋航季國內航班正班計劃數據為基礎，構建支線航空網絡，從復雜網絡的拓撲特性、機場屬性和地區屬性3 個方面選取了6 個不同的指標，較為客觀地完成了機場重要度的評估，使用熵權-Topsis 法完成關鍵節點的識別，發現了連云港、大理、瀘州、宜賓等24個節點為重要機場，DBSCAN算法完成節點的聚類，分為4 種不同類別的機場，兩種方法的結果幾乎一致，由于疫情原因，支線機場之間差異性更小，分類結果符合現實情況。對關鍵節點進行保護，從而維護支線機場網絡體系的有效運行。