改进Louvain 算法的多层航线网络社区划分

蒋 云，杨文东

（南京航空航天大学民航学院，南京 211106）

近年来，基于复杂网络理论的网络分析技术已较为成熟，网络社区划分逐渐成为网络领域新的研究热点.网络社区划分广泛地存在于现实生活中，旨在利用网络节点的拓扑信息挖掘网络的不同社区.研究网络社区化分，对于网络的功能分析、结构分析和行为预测具有重要理论意义［1］.

对于社区划分的研究可追溯到1970 年，Kernighan 等［2］提出了一种基于图分割的KL 算法，它是一种利用贪婪算法将复杂网络社区内连边数与社区间连边数差值最小化的二分法.为了改进图分割算法仅能分出两个社区的不足，Girvan 等［3］提出了一种基于层次聚类的分裂算法——GN 算法，通过判断边的介数中心性并迭代去除图的边来划分图中的多个社区；Ma 等［4］提出了基于结构聚类的LED 算法，将节点的结构相似度视为权重，从而可以对重叠社区进行划分.考虑到静态网络算法具有一定的局限性，Lancichinetti 等［5］提出了基于动态网络的社区划分算法，通过在不同时间段的图结构中寻找相似性，从而实现社区划分；Messaoudi 等［6］提出了多目标蝙蝠算法，该算法利用均值漂移技术解决参数收敛问题，利用蝙蝠算法来优化动态网络中的社区划分结果.

上述关于网络社区划分算法的研究较为丰富，但大部分算法仅适用于节点数量较少的小规模网络，并且存在运算复杂度过高的问题［7］.与众多社区划分算法相比，Louvain 算法是一种适用于大型网络、运算高效快速的模块度优化算法［8］.Louvain 算法最早由Blondel 等［9］于2008 年提出，该算法是一种基于快速贪婪算法的凝聚算法，通过不断更新模块度增量从而实现整个社区网络的模块度最大化；Traag 等［10］在此基础上提出了用计算一个随机相邻节点模块度增量代替遍历所有相邻节点的方法，提高了Louvain 算法的运算效率；冯成强等［11］提出了基于相似度投票的改进Louvain 算法，解决了Louvain 算法底层社区划分耗时较多的问题.

除了算法研究，不少学者对社区划分应用进行了研究.王鹏等［12］提出了基于模块度的IP 网络社区划分算法，对卫星IP 网络进行了社区挖掘与重要节点识别；李宇婷［13］采用非重叠社区划分方法对深圳市OFO 共享单车骑行网络进行了社区划分及特征研究；刘璐［14］在Louvain 算法的基础上考虑了文本的语义相似度，对学术文献引文网络进行了社区划分研究；李有红等［15］提出了一种融合邻边属性的NLA/SCD 社区划分算法，对多属性的个人社交网络进行了有效划分；张中军等［16］提出了基于用户转发行为和社交网络链路结构的ABLF 算法，对微博社交网络进行了网络重叠社区划分.

综合上述研究，目前社区划分算法种类繁多且应用范围广泛.然而，将网络社区划分应用于航线网络领域的研究相对较少，且大部分社区划分是以单层网络为研究对象.在实际运营中，航线网络往往由多个航空公司航线网络构成，若只构建单层区域网络，则无法较好地反映各航空公司的航线网络结构.因此，本文作者将建立2011—2019 年欧盟多层加权航线网络，运用基于改进Louvain 算法的网络社区划分模型对航线网络进行社区划分，分析各个社区的网络效率，探讨航线网络度量指标，以期为我国区域航线网络枢纽机场的构建、航空公司航线网络规划、优化和网络效率的提升提供参考借鉴.

1 多层航线网络社区划分模型

Louvain 算法是一种典型的模块度优化算法，其优化目标是使得整个社区网络的模块度最大化［7］.基于改进Louvain 算法的多层网络社区划分模型可以为多层映射聚合航线网络进行社区划分，从而更加准确地挖掘航线网络中的潜在社区结构，为航线网络结构优化提供参考借鉴［17］.本模型主要包括多层加权航线网络的构建、多层航线网络的映射聚合以及基于改进Louvain 算法的社区划分.此外，为了进一步探讨航线网络机场节点变化与网络效率，提出了多层航线网络度量指标以及航线网络效率评估模型.

1.1 多层加权航线网络构建与映射聚合

单层区域航线网络仅能评估和分析网络整体变动趋势，在分析不同航空公司的枢纽化程度以及网络结构竞争方面存在欠缺，构建多层加权航线网络具有显著优势.多层加权航线网络可以抽象为由单层加权航线网络集合S和层间网络集合B构成的图G=(S，B)［18］.其中，S={(Vα，Eα)|α∈{1，2，…，M}}表示M层单层加权航线网络集合，每一层航线网络代表一家航空公司航线网络.表示第α层 航 线 网 络 的nα个 机 场 节 点 集 合，Eα=表 示 第α层 航 线网络中机场节点vαi与vαj的航线边集合.由于在欧盟航线网络中大部分航线为双向航线，故将航线边抽象为无向边.Aα ij表示第α层航线网络邻接矩阵的元素，其关系表示为

如图1 所示，第α层和第β层加权航线网络具有不同的航线网络结构，经过映射得到多层映射聚合航线网络，该网络为加权无向网络，包含了所有单层航线网络的网络结构和航线边的航班量权重.

图1 多层加权映射聚合网络Fig.1 Multi-layer weighted mapping polymerized network

1.2 多层航线网络度量指标

节点的度是复杂网络中常用的度量指标，在航线网络中机场节点的度是指与该机场直接通航的相邻机场个数.与单层区域航线网络相比，在多层航线网络中，机场节点的度由向量形式表示，不仅可以反映机场在整体航线网络中的重要程度，也可以表征机场在各个航空公司航线网络中的重要性［19］.

对每一个机场节点vi，其在多层航线网络中的度向量为其中kiα表示机场节点vi在第α层航线网络中的度值［18］.多层网络中机场节点vi的度Pi为该节点在各单层航线网络中的度值之和，表达式为

多层航线网络的平均度是指航线网络中所有机场节点度的平均值，平均度值越大，表明航线网络连通性越好.平均度表达式为

式中：N代表机场节点的总数量.

1.3 基于改进Louvain 算法的社区划分模型

将社区划分与航线网络相结合，可以得到内部航空运输联系紧密的若干个社区，从而能够挖掘航线网络中隐藏的机场聚簇信息，对于探究航线网络枢纽机场、规划和优化航线网络具有重要意义.社区划分的数量越多，表明航线网络聚集程度越强，航线网络内部联系越紧密［7］.

模块度是衡量社区划分优劣的重要指标，其取值范围通常在[-0.5，1)之间，取值越大，表示社区划分的质量越高，航线网络的紧密性越强.传统模块度表达式如下

式中：∆Wici′表示社区ci′内所有机场与vi机场之间航线边的航班量之和.

Louvain 算法是一种凝聚启发式算法，其思想是将航线网络中的每个机场节点视为一个单独的社区，然后将机场节点分配到不同相邻机场节点的社区，若此时加权模块度增量的最大值大于零，则将该机场节点分配到此社区，然后对航线网络进行更新聚合，对上述步骤进行循坏直至航线网络的模块度不再发生改变，则航线网络社区划分结束.在循坏迭代的过程中，并非每次划分的效果都优于前一次，因而会出现加权模块度震荡的现象［20］.改进的加权模块度增量表达式如下

该算法综合考虑了机场节点vi移动后ci与ci′两个社区的模块度变化，有利于消除加权模块度的震荡，提高计算效率.

考虑到初始的航线网络中往往存在一定的边缘节点，这些节点仅与一条航线相连，又被称为叶子节点.在Louvain 算法中，由于叶子节点仅存在一个相邻节点，其所属社区必然与其相邻节点所属社区相同，而在运算过程中，每次迭代均需要计算叶子节点的模块度增量，从而会产生很多重复而不必要的计算，降低了运算速度.因此，本文在上述改进的基础上对Louvain 算法进行了进一步改进，在第一次社区划分前先将叶子节点直接划分到其相邻节点所属的社区，然后再对剩余节点计算模块度增量.该改进保证了叶子节点仅在初始网络中存在，从而减少了后续迭代过程中重复计算的次数，极大地提高了运算效率.

基于改进Louvain 算法的多层加权航线网络社区划分算法主要包括多层加权航线网络映射聚合、模块度优化和航线网络聚合3 个阶段，具体步骤如下：

输入：单层加权航线网络集合S.

输出：社区划分结果φ={c1，c2，…，cNc}.

步骤1：根据S，构建层间网络集合B=

步骤2：构建多层航线网络，并根据层间网络将多层航线网络映射到新的航线网络中，生成多层加权映射聚合航线网络G.

步骤3：将多层加权映射聚合航线网络中的每一个机场节点视为单独的社区，即ci={vi}，φ=

步骤4：在所有机场节点ci={vi}中，找出全部叶子节点，分别将它们与其相邻节点划为同一社区.更新航线网络，将叶子节点与其相邻节点视为一个节点，该节点的权重为叶子节点与其相邻节点权重之和.

步骤5：在新航线网络中随机选择一个机场节点vi，其所在社区为ci.找出vi所有相邻机场节点所在的社区，计算将机场节点vi划分至相邻机场节点所在社区ci′后航线网络的加权模块度增量∆Q′，并计算航线网络加权模块度Q.

步骤6：找出加权模块度增量∆Q′最大值所在的社区cg，将机场节点vi划分至该社区.即cg=cg+

步骤8：重复步骤5、步骤6 和步骤7，直至航线网络加权模块度Q不再发生改变，则航线网络社区划分结束.

由于基于改进Louvain 算法的多层航线网络社区划分模型是在单层航线网络的基础上进行多层映射，并获得多层加权映射聚合航线网络最优的社区结构，因此，该模型的模块度优化和网络聚合步骤也同样适用于单层航线网络社区划分.

1.4 航线网络效率评估模型

航线网络效率是指满足航线网络空间位移需求的实际能力与最佳能力之间的比值.航线网络效率从复杂网络的角度研究航线网络两点间运输的难易程度，反映了航线网络运输的有效性与便捷性.航线网络效率η∈(0，1)，η越大，表示航线网络中任意两个机场节点之间需要换乘的平均次数越少.航线网络效率评估模型的表达式为

式中：dij表示机场节点vi与vj之间的最短路径长度.

2 欧盟航线网络社区划分

运用航线网络社区划分模型、效率评估模型以及度量指标，对欧盟航线网络进行研究.2011—2019 年间，汉莎航空、法荷航空、英国航空、瑞安航空、易捷航空以及伏林航空占据了大部分欧盟航空运输市场份额，其航线数量、机场数量、航班量和旅客运输量等指标能够较好地代表整个欧盟区域航线网络.基于此，本文收集了来自OAG 数据库2011—2019 年汉莎航空、法荷航空、英国航空、瑞安航空、易捷航空以及伏林航空的航班数据，包括出发机场、到达机场、出发国家、到达国家、航班量、年份6 项指标.将各个机场视为网络节点，机场与机场间的航线视为网络的边，将航线中的航班量进行求和作为网络中边的权重，便可构建由这6 家航空公司组成的欧盟多层航线网络.

2.1 改进Louvain 算法有效性分析

在本文中，选用Louvain 算法相比于其他算法更加合适.由于在Louvain 算法的计算过程中，模块度增量的计算仅需考虑相邻节点的社区，并且网络中需要计算的边和节点的数量会随着社区的划分而逐渐减少，因此与众多算法相比，Louvain 算法是一种更加快速、高效的算法.其次，目前大部分社区划分算法仅适用于节点和边数较少的小规模网络，而Louvain 算法能够较好地适用于大规模网络的社区划分［7］.由于在本文的研究对象中，网络的节点和边的数量均在100～10 000 之间，属于较大规模网络，因而选用Louvain 算法可以更加迅速地获取运算结果.此外，相比于其他算法而言，Louvain 算法能够划分层次性的社区结构［7］，这一特殊的性质恰好适用于本文多层航线网络，因此Louvain算法具有较强的适用性.

此外，改进Louvain 算法相比于传统Louvain 算法具有显著优势.在模块度上，以2011 年航线网络为例，分别采用改进Louvain 算法、Louvain 算法、GN 算法和LED 算法对航线网络进行社区化分，得到的模块度结果如表1 所示.可以看出，采用改进Louvain 算法得到的模块度最高，表明社区划分效果最好，进一步说明了Louvain 算法相比于其他算法更加具有优势，也表明了改进Louvain 算法比传统Louvain 算法效果更好.

在计算效率上，采用改进Louvain 算法与传统Louvain 算法分别对2011 年欧盟航线网络进行社区划分，对计算时间进行比较，得到的时间提升百分比如图2 所示.对于不同航线网络而言，改进Louvain算法的计算效率相比于改进前均有明显提升，表明改进Louvain 算法比传统Louvain 算法更加合适有效.

表1 2011 年航线网络不同算法模块度比较Tab.1 Modularity of different algorithm with air transport networks in 2011

图2 改进Louvain 算法相比于传统Louvain 算法时间提升百分比Fig.2 Time lifting percentage of improved Louvain algorithm relative to traditional algorithm

2.2 社区划分与航线网络效率研究

运用基于改进Louvain 算法的社区划分模型，对2011—2019 年汉莎航空、法荷航空、英国航空、瑞安航空、易捷航空、伏林航空以及欧盟多层航线网络进行了社区划分及模块度的计算，结果如表2 所示.

在航线网络中，划分出的各个社区内部机场节点之间联系紧密，通航航线数量较多，航班密度较高，而社区与社区之间彼此联系稀疏，通航航线数量稀少，连通性较低.基于此，社区划分充分表征了航线网络的中枢辐射式结构布局，其中每一块社区表征一个枢纽机场以及与其联系紧密的支线机场群.

2011—2019 年间，欧盟多层航线网络的社区数量在5～6 个之间不断波动，模块度由0.357 8 逐渐提升至0.391 5，表明枢纽机场数量较为稳定，欧盟整体航线网络内部联系越来越紧密.汉莎航空的模块度最低且呈逐渐下降趋势，社区数量由最初4 个变成了2 个，这是由于汉莎航空航线网络逐渐由多枢纽辐射式结构转变为双枢纽辐射式结构，近年来航班逐渐集中在法兰克福机场与慕尼黑机场.法荷航空的社区数量稳定在3，表明网络的中枢辐射式结构较为稳定，夏尔戴高乐机场、阿姆斯特丹史基浦机场以及奥利机场三大机场在航线网络中始终保持三足鼎立的地位，三角形枢纽辐射式结构在航空运输中发挥着重要作用.英国航空的社区数量保持在4而后增加至5，模块度逐渐增长并成为第一，表明在英国航空多枢纽辐射式结构中，枢纽机场的数量有所增加，网络结构由较为松散逐渐变得紧密，网络规模逐渐增大，这大大促使了欧盟整体航线网络规模的增大.瑞安航空、易捷航空以及伏林航空是欧盟最大的三家低成本航空公司，它们的平均社区数量在4 左右，且社区数量和模块度均处于平稳波动状态，表明它们的蛛网式航线网络结构较为稳定.

图3 为2019 年欧盟多层航线网络社区划分结果分布图，表3 为每个社区的机场数量与网络效率统计结果.整体来看，在英国、希腊、法国、德国、意大利、西班牙、波兰等西欧、南欧和中欧国家，机场节点分布较为密集；在挪威、芬兰、立陶宛、拉脱维亚、爱沙尼亚等北欧和东欧国家，机场节点分布较为稀疏，这与欧盟经济发展水平分布状况基本一致.欧盟航线网络的社区划分呈现明显的地理聚集性，社区1 由79 个机场构成，主要分布在意大利、希腊、罗马尼亚等地区，地理分布较为广泛，机场数量最多且网络效率较高，表明社区规模最大且航线网络连通性较好；社区2 主要由西班牙机场群构成，机场数量仅有22 个，虽然数量最少但网络效率最高，社区内航空运输最为便捷；社区3 和5 分布在中欧地区，社区3 主要分布在德国、波兰、捷克、匈牙利等地区，社区5 主要分布在法国，二者网络规模相似且网络效率相同，整体连通性较好；社区4 主要由英国机场群构成，包含的机场数量为65，社区规模较大但网络效率最低，连通性相对较差.

表2 航线网络社区数量与模块度Tab.2 Community quantity and modularity of air transport networks

表3 2019 年欧盟多层航线网络各社区网络效率Tab.3 Efficiency of EU multi-layer air transport network in 2019

利用航线网络效率评估模型，对2011-2019 年各航线网络的网络效率进行了研究，结果如表4 所示.2011-2019 年间，欧盟多层航线网络的网络效率在不断增加，表明任意两个机场节点之间的平均换乘次数有所减少，整体网络结构有所优化.在航空公司网络中，除瑞安航空外，其他航空公司的网络效率均有所增加，其中汉莎航空的网络效率最高，在航空运输市场具有较大竞争力；英国航空网络效率最低，航线连通性相对较差；易捷航空以及伏林航空的网络效率近些年来逐渐升高，排名仅次于汉莎航空，突显了低成本航空公司在航空运输市场的巨大发展潜力.

2.3 航线网络度量指标分析

表5 为欧盟多层航线网络以及6 家航空公司航线网络平均度值.2011—2019 年间，欧盟多层航线网络、英国航空、瑞安航空、易捷航空和伏林航空航线网络的平均度值有较大提升，航线网络中与各机场直接通航的平均相邻机场个数有所增加，航线网络连通性逐渐增强.汉莎航空和法荷航空平均度值逐渐减小，航线网络连通性逐渐降低.在各航空公司中，瑞安航空、易捷航空和伏林航空的平均度值分别在29、16、8 以上，而汉莎航空、法荷航空和英国航空的平均度值分别在6、7、5 以上，这表明低成本航空公司网络中与机场节点相连的平均航线数远远大于全服务航空公司.

表4 不同航线网络的网络效率Tab.4 Efficiency of different air transport networks

表5 不同航线网络的平均度Tab.5 Average degree of different air transport networks

为探讨机场节点度变化对航线网络模块度和平均度值的影响，对2011—2019 年各航线网络所有机场节点中度值变化最大的前5 个机场进行综合统计，结果如表6 所示.2011—2019 年，里昂国际机场、布拉尼亚克机场、波尔多机场、杜塞尔多夫国际机场和汉堡国际机场等法荷航空与汉莎航空重要机场的度值有大幅减少，导致了法荷航空和汉莎航空航线网络平均度值的减少.汉莎航空逐渐将航班集中在法兰克福机场与慕尼黑机场，法荷航空逐渐将航班集中在夏尔戴高乐机场与阿姆斯特丹史基浦机场，导致了这两家航空公司航线网络社区数量和模块度的减少.曼彻斯特机场、马拉加机场、都柏林机场、马略卡岛帕尔马机场、巴塞罗那安普拉特机场的度值有大幅增加，这些机场度值的提升来源于西欧、中欧和南欧地区大量新航线的开辟，这促使了英国航空、瑞安航空、易捷航空和伏林航空航线网络平均度值的增加.尽管法荷航空和汉莎航空两家大型全服务公司航线网络的平均度值和模块度有所减少，但是欧盟多层航线网络的聚集程度、网络效率与连通性仍然有所增强，这表明了低成本航空公司在欧盟航线网络中占据重要地位，具有更强的市场竞争力与发展潜力.

表6 欧盟航线网络中度值变化最大的前5 个机场节点Tab.6 The top five airports with the largest degree value change in EU network

3 结论

1）2011-2019 年，欧盟多层航线网络模块度、网络效率和平均度值不断增加，聚集程度和连通性逐渐增强，整体网络结构有所优化.航线网络的社区数量在5～6 个之间稳定波动，社区划分呈现明显的地理聚集性，机场节点主要集中在西欧、南欧和中欧地区，网络效率较高的社区主要分布在意大利、西班牙等国家.

2）汉莎航空的社区数量、模块度和平均度值均有所减少，网络效率有所提升，网络结构由多枢纽辐射式逐渐转变为双枢纽辐射式；法荷航空社区数量较为稳定，模块度和平均度值逐渐减少，网络效率逐渐增加，三角形枢纽辐射式网络结构较为稳定；英国航空的社区数量、模块度、平均度值和网络效率均有所提升，枢纽机场数量有所增加，航线网络内部联系越来越紧密，多枢纽辐射式网络结构逐渐扩大；瑞安航空、易捷航空以及伏林航空三家低成本航空公司航线网络连通性逐渐增强，蛛网式网络结构逐渐扩大，在欧盟航空运输市场具有巨大的竞争力与发展潜力.

3）本文提出的改进Louvain 算法社区划分模型相比于传统Louvain 算法具有更高的计算效率和模块度，可以实现多层加权航线网络的社区划分.但本模型仅适用于非重叠社区划分，在实际航线网络中，机场节点往往具有多重社区属性，使用重叠社区划分算法可以更好地探究航线网络社区.因此，后续将从重叠社区划分算法入手，对此展开工作.