改進Louvain 算法的多層航線網(wǎng)絡(luò)社區(qū)劃分

蔣 云，楊文東

（南京航空航天大學(xué)民航學(xué)院，南京 211106）

近年來，基于復(fù)雜網(wǎng)絡(luò)理論的網(wǎng)絡(luò)分析技術(shù)已較為成熟，網(wǎng)絡(luò)社區(qū)劃分逐漸成為網(wǎng)絡(luò)領(lǐng)域新的研究熱點.網(wǎng)絡(luò)社區(qū)劃分廣泛地存在于現(xiàn)實生活中，旨在利用網(wǎng)絡(luò)節(jié)點的拓?fù)湫畔⑼诰蚓W(wǎng)絡(luò)的不同社區(qū).研究網(wǎng)絡(luò)社區(qū)化分，對于網(wǎng)絡(luò)的功能分析、結(jié)構(gòu)分析和行為預(yù)測具有重要理論意義［1］.

對于社區(qū)劃分的研究可追溯到1970 年，Kernighan 等［2］提出了一種基于圖分割的KL 算法，它是一種利用貪婪算法將復(fù)雜網(wǎng)絡(luò)社區(qū)內(nèi)連邊數(shù)與社區(qū)間連邊數(shù)差值最小化的二分法.為了改進圖分割算法僅能分出兩個社區(qū)的不足，Girvan 等［3］提出了一種基于層次聚類的分裂算法——GN 算法，通過判斷邊的介數(shù)中心性并迭代去除圖的邊來劃分圖中的多個社區(qū)；Ma 等［4］提出了基于結(jié)構(gòu)聚類的LED 算法，將節(jié)點的結(jié)構(gòu)相似度視為權(quán)重，從而可以對重疊社區(qū)進行劃分.考慮到靜態(tài)網(wǎng)絡(luò)算法具有一定的局限性，Lancichinetti 等［5］提出了基于動態(tài)網(wǎng)絡(luò)的社區(qū)劃分算法，通過在不同時間段的圖結(jié)構(gòu)中尋找相似性，從而實現(xiàn)社區(qū)劃分；Messaoudi 等［6］提出了多目標(biāo)蝙蝠算法，該算法利用均值漂移技術(shù)解決參數(shù)收斂問題，利用蝙蝠算法來優(yōu)化動態(tài)網(wǎng)絡(luò)中的社區(qū)劃分結(jié)果.

上述關(guān)于網(wǎng)絡(luò)社區(qū)劃分算法的研究較為豐富，但大部分算法僅適用于節(jié)點數(shù)量較少的小規(guī)模網(wǎng)絡(luò)，并且存在運算復(fù)雜度過高的問題［7］.與眾多社區(qū)劃分算法相比，Louvain 算法是一種適用于大型網(wǎng)絡(luò)、運算高效快速的模塊度優(yōu)化算法［8］.Louvain 算法最早由Blondel 等［9］于2008 年提出，該算法是一種基于快速貪婪算法的凝聚算法，通過不斷更新模塊度增量從而實現(xiàn)整個社區(qū)網(wǎng)絡(luò)的模塊度最大化；Traag 等［10］在此基礎(chǔ)上提出了用計算一個隨機相鄰節(jié)點模塊度增量代替遍歷所有相鄰節(jié)點的方法，提高了Louvain 算法的運算效率；馮成強等［11］提出了基于相似度投票的改進Louvain 算法，解決了Louvain 算法底層社區(qū)劃分耗時較多的問題.

除了算法研究，不少學(xué)者對社區(qū)劃分應(yīng)用進行了研究.王鵬等［12］提出了基于模塊度的IP 網(wǎng)絡(luò)社區(qū)劃分算法，對衛(wèi)星IP 網(wǎng)絡(luò)進行了社區(qū)挖掘與重要節(jié)點識別；李宇婷［13］采用非重疊社區(qū)劃分方法對深圳市OFO 共享單車騎行網(wǎng)絡(luò)進行了社區(qū)劃分及特征研究；劉璐［14］在Louvain 算法的基礎(chǔ)上考慮了文本的語義相似度，對學(xué)術(shù)文獻(xiàn)引文網(wǎng)絡(luò)進行了社區(qū)劃分研究；李有紅等［15］提出了一種融合鄰邊屬性的NLA/SCD 社區(qū)劃分算法，對多屬性的個人社交網(wǎng)絡(luò)進行了有效劃分；張中軍等［16］提出了基于用戶轉(zhuǎn)發(fā)行為和社交網(wǎng)絡(luò)鏈路結(jié)構(gòu)的ABLF 算法，對微博社交網(wǎng)絡(luò)進行了網(wǎng)絡(luò)重疊社區(qū)劃分.

綜合上述研究，目前社區(qū)劃分算法種類繁多且應(yīng)用范圍廣泛.然而，將網(wǎng)絡(luò)社區(qū)劃分應(yīng)用于航線網(wǎng)絡(luò)領(lǐng)域的研究相對較少，且大部分社區(qū)劃分是以單層網(wǎng)絡(luò)為研究對象.在實際運營中，航線網(wǎng)絡(luò)往往由多個航空公司航線網(wǎng)絡(luò)構(gòu)成，若只構(gòu)建單層區(qū)域網(wǎng)絡(luò)，則無法較好地反映各航空公司的航線網(wǎng)絡(luò)結(jié)構(gòu).因此，本文作者將建立2011—2019 年歐盟多層加權(quán)航線網(wǎng)絡(luò)，運用基于改進Louvain 算法的網(wǎng)絡(luò)社區(qū)劃分模型對航線網(wǎng)絡(luò)進行社區(qū)劃分，分析各個社區(qū)的網(wǎng)絡(luò)效率，探討航線網(wǎng)絡(luò)度量指標(biāo)，以期為我國區(qū)域航線網(wǎng)絡(luò)樞紐機場的構(gòu)建、航空公司航線網(wǎng)絡(luò)規(guī)劃、優(yōu)化和網(wǎng)絡(luò)效率的提升提供參考借鑒.

1 多層航線網(wǎng)絡(luò)社區(qū)劃分模型

Louvain 算法是一種典型的模塊度優(yōu)化算法，其優(yōu)化目標(biāo)是使得整個社區(qū)網(wǎng)絡(luò)的模塊度最大化［7］.基于改進Louvain 算法的多層網(wǎng)絡(luò)社區(qū)劃分模型可以為多層映射聚合航線網(wǎng)絡(luò)進行社區(qū)劃分，從而更加準(zhǔn)確地挖掘航線網(wǎng)絡(luò)中的潛在社區(qū)結(jié)構(gòu)，為航線網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化提供參考借鑒［17］.本模型主要包括多層加權(quán)航線網(wǎng)絡(luò)的構(gòu)建、多層航線網(wǎng)絡(luò)的映射聚合以及基于改進Louvain 算法的社區(qū)劃分.此外，為了進一步探討航線網(wǎng)絡(luò)機場節(jié)點變化與網(wǎng)絡(luò)效率，提出了多層航線網(wǎng)絡(luò)度量指標(biāo)以及航線網(wǎng)絡(luò)效率評估模型.

1.1 多層加權(quán)航線網(wǎng)絡(luò)構(gòu)建與映射聚合

單層區(qū)域航線網(wǎng)絡(luò)僅能評估和分析網(wǎng)絡(luò)整體變動趨勢，在分析不同航空公司的樞紐化程度以及網(wǎng)絡(luò)結(jié)構(gòu)競爭方面存在欠缺，構(gòu)建多層加權(quán)航線網(wǎng)絡(luò)具有顯著優(yōu)勢.多層加權(quán)航線網(wǎng)絡(luò)可以抽象為由單層加權(quán)航線網(wǎng)絡(luò)集合S和層間網(wǎng)絡(luò)集合B構(gòu)成的圖G=(S，B)［18］.其中，S={(Vα，Eα)|α∈{1，2，…，M}}表示M層單層加權(quán)航線網(wǎng)絡(luò)集合，每一層航線網(wǎng)絡(luò)代表一家航空公司航線網(wǎng)絡(luò).表示第α層 航 線 網(wǎng) 絡(luò) 的nα個 機 場 節(jié) 點 集 合，Eα=表 示 第α層 航 線網(wǎng)絡(luò)中機場節(jié)點vαi與vαj的航線邊集合.由于在歐盟航線網(wǎng)絡(luò)中大部分航線為雙向航線，故將航線邊抽象為無向邊.Aα ij表示第α層航線網(wǎng)絡(luò)鄰接矩陣的元素，其關(guān)系表示為

如圖1 所示，第α層和第β層加權(quán)航線網(wǎng)絡(luò)具有不同的航線網(wǎng)絡(luò)結(jié)構(gòu)，經(jīng)過映射得到多層映射聚合航線網(wǎng)絡(luò)，該網(wǎng)絡(luò)為加權(quán)無向網(wǎng)絡(luò)，包含了所有單層航線網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)和航線邊的航班量權(quán)重.

圖1 多層加權(quán)映射聚合網(wǎng)絡(luò)Fig.1 Multi-layer weighted mapping polymerized network

1.2 多層航線網(wǎng)絡(luò)度量指標(biāo)

節(jié)點的度是復(fù)雜網(wǎng)絡(luò)中常用的度量指標(biāo)，在航線網(wǎng)絡(luò)中機場節(jié)點的度是指與該機場直接通航的相鄰機場個數(shù).與單層區(qū)域航線網(wǎng)絡(luò)相比，在多層航線網(wǎng)絡(luò)中，機場節(jié)點的度由向量形式表示，不僅可以反映機場在整體航線網(wǎng)絡(luò)中的重要程度，也可以表征機場在各個航空公司航線網(wǎng)絡(luò)中的重要性［19］.

對每一個機場節(jié)點vi，其在多層航線網(wǎng)絡(luò)中的度向量為其中kiα表示機場節(jié)點vi在第α層航線網(wǎng)絡(luò)中的度值［18］.多層網(wǎng)絡(luò)中機場節(jié)點vi的度Pi為該節(jié)點在各單層航線網(wǎng)絡(luò)中的度值之和，表達(dá)式為

多層航線網(wǎng)絡(luò)的平均度是指航線網(wǎng)絡(luò)中所有機場節(jié)點度的平均值，平均度值越大，表明航線網(wǎng)絡(luò)連通性越好.平均度表達(dá)式為

式中：N代表機場節(jié)點的總數(shù)量.

1.3 基于改進Louvain 算法的社區(qū)劃分模型

將社區(qū)劃分與航線網(wǎng)絡(luò)相結(jié)合，可以得到內(nèi)部航空運輸聯(lián)系緊密的若干個社區(qū)，從而能夠挖掘航線網(wǎng)絡(luò)中隱藏的機場聚簇信息，對于探究航線網(wǎng)絡(luò)樞紐機場、規(guī)劃和優(yōu)化航線網(wǎng)絡(luò)具有重要意義.社區(qū)劃分的數(shù)量越多，表明航線網(wǎng)絡(luò)聚集程度越強，航線網(wǎng)絡(luò)內(nèi)部聯(lián)系越緊密［7］.

模塊度是衡量社區(qū)劃分優(yōu)劣的重要指標(biāo)，其取值范圍通常在[-0.5，1)之間，取值越大，表示社區(qū)劃分的質(zhì)量越高，航線網(wǎng)絡(luò)的緊密性越強.傳統(tǒng)模塊度表達(dá)式如下

式中：?Wici′表示社區(qū)ci′內(nèi)所有機場與vi機場之間航線邊的航班量之和.

Louvain 算法是一種凝聚啟發(fā)式算法，其思想是將航線網(wǎng)絡(luò)中的每個機場節(jié)點視為一個單獨的社區(qū)，然后將機場節(jié)點分配到不同相鄰機場節(jié)點的社區(qū)，若此時加權(quán)模塊度增量的最大值大于零，則將該機場節(jié)點分配到此社區(qū)，然后對航線網(wǎng)絡(luò)進行更新聚合，對上述步驟進行循壞直至航線網(wǎng)絡(luò)的模塊度不再發(fā)生改變，則航線網(wǎng)絡(luò)社區(qū)劃分結(jié)束.在循壞迭代的過程中，并非每次劃分的效果都優(yōu)于前一次，因而會出現(xiàn)加權(quán)模塊度震蕩的現(xiàn)象［20］.改進的加權(quán)模塊度增量表達(dá)式如下

該算法綜合考慮了機場節(jié)點vi移動后ci與ci′兩個社區(qū)的模塊度變化，有利于消除加權(quán)模塊度的震蕩，提高計算效率.

考慮到初始的航線網(wǎng)絡(luò)中往往存在一定的邊緣節(jié)點，這些節(jié)點僅與一條航線相連，又被稱為葉子節(jié)點.在Louvain 算法中，由于葉子節(jié)點僅存在一個相鄰節(jié)點，其所屬社區(qū)必然與其相鄰節(jié)點所屬社區(qū)相同，而在運算過程中，每次迭代均需要計算葉子節(jié)點的模塊度增量，從而會產(chǎn)生很多重復(fù)而不必要的計算，降低了運算速度.因此，本文在上述改進的基礎(chǔ)上對Louvain 算法進行了進一步改進，在第一次社區(qū)劃分前先將葉子節(jié)點直接劃分到其相鄰節(jié)點所屬的社區(qū)，然后再對剩余節(jié)點計算模塊度增量.該改進保證了葉子節(jié)點僅在初始網(wǎng)絡(luò)中存在，從而減少了后續(xù)迭代過程中重復(fù)計算的次數(shù)，極大地提高了運算效率.

基于改進Louvain 算法的多層加權(quán)航線網(wǎng)絡(luò)社區(qū)劃分算法主要包括多層加權(quán)航線網(wǎng)絡(luò)映射聚合、模塊度優(yōu)化和航線網(wǎng)絡(luò)聚合3 個階段，具體步驟如下：

輸入：單層加權(quán)航線網(wǎng)絡(luò)集合S.

輸出：社區(qū)劃分結(jié)果φ={c1，c2，…，cNc}.

步驟1：根據(jù)S，構(gòu)建層間網(wǎng)絡(luò)集合B=

步驟2：構(gòu)建多層航線網(wǎng)絡(luò)，并根據(jù)層間網(wǎng)絡(luò)將多層航線網(wǎng)絡(luò)映射到新的航線網(wǎng)絡(luò)中，生成多層加權(quán)映射聚合航線網(wǎng)絡(luò)G.

步驟3：將多層加權(quán)映射聚合航線網(wǎng)絡(luò)中的每一個機場節(jié)點視為單獨的社區(qū)，即ci={vi}，φ=

步驟4：在所有機場節(jié)點ci={vi}中，找出全部葉子節(jié)點，分別將它們與其相鄰節(jié)點劃為同一社區(qū).更新航線網(wǎng)絡(luò)，將葉子節(jié)點與其相鄰節(jié)點視為一個節(jié)點，該節(jié)點的權(quán)重為葉子節(jié)點與其相鄰節(jié)點權(quán)重之和.

步驟5：在新航線網(wǎng)絡(luò)中隨機選擇一個機場節(jié)點vi，其所在社區(qū)為ci.找出vi所有相鄰機場節(jié)點所在的社區(qū)，計算將機場節(jié)點vi劃分至相鄰機場節(jié)點所在社區(qū)ci′后航線網(wǎng)絡(luò)的加權(quán)模塊度增量?Q′，并計算航線網(wǎng)絡(luò)加權(quán)模塊度Q.

步驟6：找出加權(quán)模塊度增量?Q′最大值所在的社區(qū)cg，將機場節(jié)點vi劃分至該社區(qū).即cg=cg+

步驟8：重復(fù)步驟5、步驟6 和步驟7，直至航線網(wǎng)絡(luò)加權(quán)模塊度Q不再發(fā)生改變，則航線網(wǎng)絡(luò)社區(qū)劃分結(jié)束.

由于基于改進Louvain 算法的多層航線網(wǎng)絡(luò)社區(qū)劃分模型是在單層航線網(wǎng)絡(luò)的基礎(chǔ)上進行多層映射，并獲得多層加權(quán)映射聚合航線網(wǎng)絡(luò)最優(yōu)的社區(qū)結(jié)構(gòu)，因此，該模型的模塊度優(yōu)化和網(wǎng)絡(luò)聚合步驟也同樣適用于單層航線網(wǎng)絡(luò)社區(qū)劃分.

1.4 航線網(wǎng)絡(luò)效率評估模型

航線網(wǎng)絡(luò)效率是指滿足航線網(wǎng)絡(luò)空間位移需求的實際能力與最佳能力之間的比值.航線網(wǎng)絡(luò)效率從復(fù)雜網(wǎng)絡(luò)的角度研究航線網(wǎng)絡(luò)兩點間運輸?shù)碾y易程度，反映了航線網(wǎng)絡(luò)運輸?shù)挠行耘c便捷性.航線網(wǎng)絡(luò)效率η∈(0，1)，η越大，表示航線網(wǎng)絡(luò)中任意兩個機場節(jié)點之間需要換乘的平均次數(shù)越少.航線網(wǎng)絡(luò)效率評估模型的表達(dá)式為

式中：dij表示機場節(jié)點vi與vj之間的最短路徑長度.

2 歐盟航線網(wǎng)絡(luò)社區(qū)劃分

運用航線網(wǎng)絡(luò)社區(qū)劃分模型、效率評估模型以及度量指標(biāo)，對歐盟航線網(wǎng)絡(luò)進行研究.2011—2019 年間，漢莎航空、法荷航空、英國航空、瑞安航空、易捷航空以及伏林航空占據(jù)了大部分歐盟航空運輸市場份額，其航線數(shù)量、機場數(shù)量、航班量和旅客運輸量等指標(biāo)能夠較好地代表整個歐盟區(qū)域航線網(wǎng)絡(luò).基于此，本文收集了來自O(shè)AG 數(shù)據(jù)庫2011—2019 年漢莎航空、法荷航空、英國航空、瑞安航空、易捷航空以及伏林航空的航班數(shù)據(jù)，包括出發(fā)機場、到達(dá)機場、出發(fā)國家、到達(dá)國家、航班量、年份6 項指標(biāo).將各個機場視為網(wǎng)絡(luò)節(jié)點，機場與機場間的航線視為網(wǎng)絡(luò)的邊，將航線中的航班量進行求和作為網(wǎng)絡(luò)中邊的權(quán)重，便可構(gòu)建由這6 家航空公司組成的歐盟多層航線網(wǎng)絡(luò).

2.1 改進Louvain 算法有效性分析

在本文中，選用Louvain 算法相比于其他算法更加合適.由于在Louvain 算法的計算過程中，模塊度增量的計算僅需考慮相鄰節(jié)點的社區(qū)，并且網(wǎng)絡(luò)中需要計算的邊和節(jié)點的數(shù)量會隨著社區(qū)的劃分而逐漸減少，因此與眾多算法相比，Louvain 算法是一種更加快速、高效的算法.其次，目前大部分社區(qū)劃分算法僅適用于節(jié)點和邊數(shù)較少的小規(guī)模網(wǎng)絡(luò)，而Louvain 算法能夠較好地適用于大規(guī)模網(wǎng)絡(luò)的社區(qū)劃分［7］.由于在本文的研究對象中，網(wǎng)絡(luò)的節(jié)點和邊的數(shù)量均在100～10 000 之間，屬于較大規(guī)模網(wǎng)絡(luò)，因而選用Louvain 算法可以更加迅速地獲取運算結(jié)果.此外，相比于其他算法而言，Louvain 算法能夠劃分層次性的社區(qū)結(jié)構(gòu)［7］，這一特殊的性質(zhì)恰好適用于本文多層航線網(wǎng)絡(luò)，因此Louvain算法具有較強的適用性.

此外，改進Louvain 算法相比于傳統(tǒng)Louvain 算法具有顯著優(yōu)勢.在模塊度上，以2011 年航線網(wǎng)絡(luò)為例，分別采用改進Louvain 算法、Louvain 算法、GN 算法和LED 算法對航線網(wǎng)絡(luò)進行社區(qū)化分，得到的模塊度結(jié)果如表1 所示.可以看出，采用改進Louvain 算法得到的模塊度最高，表明社區(qū)劃分效果最好，進一步說明了Louvain 算法相比于其他算法更加具有優(yōu)勢，也表明了改進Louvain 算法比傳統(tǒng)Louvain 算法效果更好.

在計算效率上，采用改進Louvain 算法與傳統(tǒng)Louvain 算法分別對2011 年歐盟航線網(wǎng)絡(luò)進行社區(qū)劃分，對計算時間進行比較，得到的時間提升百分比如圖2 所示.對于不同航線網(wǎng)絡(luò)而言，改進Louvain算法的計算效率相比于改進前均有明顯提升，表明改進Louvain 算法比傳統(tǒng)Louvain 算法更加合適有效.

表1 2011 年航線網(wǎng)絡(luò)不同算法模塊度比較Tab.1 Modularity of different algorithm with air transport networks in 2011

圖2 改進Louvain 算法相比于傳統(tǒng)Louvain 算法時間提升百分比Fig.2 Time lifting percentage of improved Louvain algorithm relative to traditional algorithm

2.2 社區(qū)劃分與航線網(wǎng)絡(luò)效率研究

運用基于改進Louvain 算法的社區(qū)劃分模型，對2011—2019 年漢莎航空、法荷航空、英國航空、瑞安航空、易捷航空、伏林航空以及歐盟多層航線網(wǎng)絡(luò)進行了社區(qū)劃分及模塊度的計算，結(jié)果如表2 所示.

在航線網(wǎng)絡(luò)中，劃分出的各個社區(qū)內(nèi)部機場節(jié)點之間聯(lián)系緊密，通航航線數(shù)量較多，航班密度較高，而社區(qū)與社區(qū)之間彼此聯(lián)系稀疏，通航航線數(shù)量稀少，連通性較低.基于此，社區(qū)劃分充分表征了航線網(wǎng)絡(luò)的中樞輻射式結(jié)構(gòu)布局，其中每一塊社區(qū)表征一個樞紐機場以及與其聯(lián)系緊密的支線機場群.

2011—2019 年間，歐盟多層航線網(wǎng)絡(luò)的社區(qū)數(shù)量在5～6 個之間不斷波動，模塊度由0.357 8 逐漸提升至0.391 5，表明樞紐機場數(shù)量較為穩(wěn)定，歐盟整體航線網(wǎng)絡(luò)內(nèi)部聯(lián)系越來越緊密.漢莎航空的模塊度最低且呈逐漸下降趨勢，社區(qū)數(shù)量由最初4 個變成了2 個，這是由于漢莎航空航線網(wǎng)絡(luò)逐漸由多樞紐輻射式結(jié)構(gòu)轉(zhuǎn)變?yōu)殡p樞紐輻射式結(jié)構(gòu)，近年來航班逐漸集中在法蘭克福機場與慕尼黑機場.法荷航空的社區(qū)數(shù)量穩(wěn)定在3，表明網(wǎng)絡(luò)的中樞輻射式結(jié)構(gòu)較為穩(wěn)定，夏爾戴高樂機場、阿姆斯特丹史基浦機場以及奧利機場三大機場在航線網(wǎng)絡(luò)中始終保持三足鼎立的地位，三角形樞紐輻射式結(jié)構(gòu)在航空運輸中發(fā)揮著重要作用.英國航空的社區(qū)數(shù)量保持在4而后增加至5，模塊度逐漸增長并成為第一，表明在英國航空多樞紐輻射式結(jié)構(gòu)中，樞紐機場的數(shù)量有所增加，網(wǎng)絡(luò)結(jié)構(gòu)由較為松散逐漸變得緊密，網(wǎng)絡(luò)規(guī)模逐漸增大，這大大促使了歐盟整體航線網(wǎng)絡(luò)規(guī)模的增大.瑞安航空、易捷航空以及伏林航空是歐盟最大的三家低成本航空公司，它們的平均社區(qū)數(shù)量在4 左右，且社區(qū)數(shù)量和模塊度均處于平穩(wěn)波動狀態(tài)，表明它們的蛛網(wǎng)式航線網(wǎng)絡(luò)結(jié)構(gòu)較為穩(wěn)定.

圖3 為2019 年歐盟多層航線網(wǎng)絡(luò)社區(qū)劃分結(jié)果分布圖，表3 為每個社區(qū)的機場數(shù)量與網(wǎng)絡(luò)效率統(tǒng)計結(jié)果.整體來看，在英國、希臘、法國、德國、意大利、西班牙、波蘭等西歐、南歐和中歐國家，機場節(jié)點分布較為密集；在挪威、芬蘭、立陶宛、拉脫維亞、愛沙尼亞等北歐和東歐國家，機場節(jié)點分布較為稀疏，這與歐盟經(jīng)濟發(fā)展水平分布狀況基本一致.歐盟航線網(wǎng)絡(luò)的社區(qū)劃分呈現(xiàn)明顯的地理聚集性，社區(qū)1 由79 個機場構(gòu)成，主要分布在意大利、希臘、羅馬尼亞等地區(qū)，地理分布較為廣泛，機場數(shù)量最多且網(wǎng)絡(luò)效率較高，表明社區(qū)規(guī)模最大且航線網(wǎng)絡(luò)連通性較好；社區(qū)2 主要由西班牙機場群構(gòu)成，機場數(shù)量僅有22 個，雖然數(shù)量最少但網(wǎng)絡(luò)效率最高，社區(qū)內(nèi)航空運輸最為便捷；社區(qū)3 和5 分布在中歐地區(qū)，社區(qū)3 主要分布在德國、波蘭、捷克、匈牙利等地區(qū)，社區(qū)5 主要分布在法國，二者網(wǎng)絡(luò)規(guī)模相似且網(wǎng)絡(luò)效率相同，整體連通性較好；社區(qū)4 主要由英國機場群構(gòu)成，包含的機場數(shù)量為65，社區(qū)規(guī)模較大但網(wǎng)絡(luò)效率最低，連通性相對較差.

表2 航線網(wǎng)絡(luò)社區(qū)數(shù)量與模塊度Tab.2 Community quantity and modularity of air transport networks

表3 2019 年歐盟多層航線網(wǎng)絡(luò)各社區(qū)網(wǎng)絡(luò)效率Tab.3 Efficiency of EU multi-layer air transport network in 2019

利用航線網(wǎng)絡(luò)效率評估模型，對2011-2019 年各航線網(wǎng)絡(luò)的網(wǎng)絡(luò)效率進行了研究，結(jié)果如表4 所示.2011-2019 年間，歐盟多層航線網(wǎng)絡(luò)的網(wǎng)絡(luò)效率在不斷增加，表明任意兩個機場節(jié)點之間的平均換乘次數(shù)有所減少，整體網(wǎng)絡(luò)結(jié)構(gòu)有所優(yōu)化.在航空公司網(wǎng)絡(luò)中，除瑞安航空外，其他航空公司的網(wǎng)絡(luò)效率均有所增加，其中漢莎航空的網(wǎng)絡(luò)效率最高，在航空運輸市場具有較大競爭力；英國航空網(wǎng)絡(luò)效率最低，航線連通性相對較差；易捷航空以及伏林航空的網(wǎng)絡(luò)效率近些年來逐漸升高，排名僅次于漢莎航空，突顯了低成本航空公司在航空運輸市場的巨大發(fā)展?jié)摿?

2.3 航線網(wǎng)絡(luò)度量指標(biāo)分析

表5 為歐盟多層航線網(wǎng)絡(luò)以及6 家航空公司航線網(wǎng)絡(luò)平均度值.2011—2019 年間，歐盟多層航線網(wǎng)絡(luò)、英國航空、瑞安航空、易捷航空和伏林航空航線網(wǎng)絡(luò)的平均度值有較大提升，航線網(wǎng)絡(luò)中與各機場直接通航的平均相鄰機場個數(shù)有所增加，航線網(wǎng)絡(luò)連通性逐漸增強.漢莎航空和法荷航空平均度值逐漸減小，航線網(wǎng)絡(luò)連通性逐漸降低.在各航空公司中，瑞安航空、易捷航空和伏林航空的平均度值分別在29、16、8 以上，而漢莎航空、法荷航空和英國航空的平均度值分別在6、7、5 以上，這表明低成本航空公司網(wǎng)絡(luò)中與機場節(jié)點相連的平均航線數(shù)遠(yuǎn)遠(yuǎn)大于全服務(wù)航空公司.

表4 不同航線網(wǎng)絡(luò)的網(wǎng)絡(luò)效率Tab.4 Efficiency of different air transport networks

表5 不同航線網(wǎng)絡(luò)的平均度Tab.5 Average degree of different air transport networks

為探討機場節(jié)點度變化對航線網(wǎng)絡(luò)模塊度和平均度值的影響，對2011—2019 年各航線網(wǎng)絡(luò)所有機場節(jié)點中度值變化最大的前5 個機場進行綜合統(tǒng)計，結(jié)果如表6 所示.2011—2019 年，里昂國際機場、布拉尼亞克機場、波爾多機場、杜塞爾多夫國際機場和漢堡國際機場等法荷航空與漢莎航空重要機場的度值有大幅減少，導(dǎo)致了法荷航空和漢莎航空航線網(wǎng)絡(luò)平均度值的減少.漢莎航空逐漸將航班集中在法蘭克福機場與慕尼黑機場，法荷航空逐漸將航班集中在夏爾戴高樂機場與阿姆斯特丹史基浦機場，導(dǎo)致了這兩家航空公司航線網(wǎng)絡(luò)社區(qū)數(shù)量和模塊度的減少.曼徹斯特機場、馬拉加機場、都柏林機場、馬略卡島帕爾馬機場、巴塞羅那安普拉特機場的度值有大幅增加，這些機場度值的提升來源于西歐、中歐和南歐地區(qū)大量新航線的開辟，這促使了英國航空、瑞安航空、易捷航空和伏林航空航線網(wǎng)絡(luò)平均度值的增加.盡管法荷航空和漢莎航空兩家大型全服務(wù)公司航線網(wǎng)絡(luò)的平均度值和模塊度有所減少，但是歐盟多層航線網(wǎng)絡(luò)的聚集程度、網(wǎng)絡(luò)效率與連通性仍然有所增強，這表明了低成本航空公司在歐盟航線網(wǎng)絡(luò)中占據(jù)重要地位，具有更強的市場競爭力與發(fā)展?jié)摿?

表6 歐盟航線網(wǎng)絡(luò)中度值變化最大的前5 個機場節(jié)點Tab.6 The top five airports with the largest degree value change in EU network

3 結(jié)論

1）2011-2019 年，歐盟多層航線網(wǎng)絡(luò)模塊度、網(wǎng)絡(luò)效率和平均度值不斷增加，聚集程度和連通性逐漸增強，整體網(wǎng)絡(luò)結(jié)構(gòu)有所優(yōu)化.航線網(wǎng)絡(luò)的社區(qū)數(shù)量在5～6 個之間穩(wěn)定波動，社區(qū)劃分呈現(xiàn)明顯的地理聚集性，機場節(jié)點主要集中在西歐、南歐和中歐地區(qū)，網(wǎng)絡(luò)效率較高的社區(qū)主要分布在意大利、西班牙等國家.

2）漢莎航空的社區(qū)數(shù)量、模塊度和平均度值均有所減少，網(wǎng)絡(luò)效率有所提升，網(wǎng)絡(luò)結(jié)構(gòu)由多樞紐輻射式逐漸轉(zhuǎn)變?yōu)殡p樞紐輻射式；法荷航空社區(qū)數(shù)量較為穩(wěn)定，模塊度和平均度值逐漸減少，網(wǎng)絡(luò)效率逐漸增加，三角形樞紐輻射式網(wǎng)絡(luò)結(jié)構(gòu)較為穩(wěn)定；英國航空的社區(qū)數(shù)量、模塊度、平均度值和網(wǎng)絡(luò)效率均有所提升，樞紐機場數(shù)量有所增加，航線網(wǎng)絡(luò)內(nèi)部聯(lián)系越來越緊密，多樞紐輻射式網(wǎng)絡(luò)結(jié)構(gòu)逐漸擴大；瑞安航空、易捷航空以及伏林航空三家低成本航空公司航線網(wǎng)絡(luò)連通性逐漸增強，蛛網(wǎng)式網(wǎng)絡(luò)結(jié)構(gòu)逐漸擴大，在歐盟航空運輸市場具有巨大的競爭力與發(fā)展?jié)摿?

3）本文提出的改進Louvain 算法社區(qū)劃分模型相比于傳統(tǒng)Louvain 算法具有更高的計算效率和模塊度，可以實現(xiàn)多層加權(quán)航線網(wǎng)絡(luò)的社區(qū)劃分.但本模型僅適用于非重疊社區(qū)劃分，在實際航線網(wǎng)絡(luò)中，機場節(jié)點往往具有多重社區(qū)屬性，使用重疊社區(qū)劃分算法可以更好地探究航線網(wǎng)絡(luò)社區(qū).因此，后續(xù)將從重疊社區(qū)劃分算法入手，對此展開工作.