基于Louvain算法的铁路旅客社会网络社区划分研究

徐 进,邓乐龄

1.西南交通大学 经济管理学院,四川 成都 610031

2.西南交通大学“服务科学与创新”四川省重点实验室,四川 成都 610031

1 引 言

随着我国轨道交通行业的飞速发展，铁路客运量也不断攀升。基于社会网络的旅客出行行为研究能帮助客运部门了解旅客团体出行特征，提升服务质量[1,2]。对于旅客社会网络中整体紧密度较低的连通子网，需要进行社区划分，才能够对网络拓扑结构进行更深入的分析。由于铁路客运量巨大，基于铁路票务数据构建的旅客社会网络规模也十分庞大，因此，相应的社区划分算法必须具备高效和快速的特点。Louvain算法是一种基于图凝聚思想的层次社区划分算法[3-5]，它利用模块度[6]来评价划分质量，在面对大型网络时也能高效率地完成社区划分，并且其能够在非监督（不用设定社区数量）的情况下完成社区的划分。Renaud Lambiotte[7]认为使用模块度为质量函数的社区划分算法容易对特定结构的模型产生偏差，因此，加入解析度（Resolution）来灵活地控制社区划分数量以及规模。Traag[8]调整了Louvain算法中节点加入社区时的移动策略，使网络整体模块度变动较小的情况下完成了Louvain算法加速。吴祖峰等人[9]在社区移动聚合过程中直接移除叶节点，提高Louvain算法的运行效率。吴卫江[10]提出了基于Louvain的并行社区划分方法，提高了社区划分效率。林定等人[11]在Louvain社区划分的基础上结合三维树形映射表达社区划分结果。本文利用春运期间的铁路客运大数据，构建铁路旅客社会网络，并利用Louvain算法将最大连通子网进行社区划分，进一步研究最大连通子网的网络拓扑结构，并从社区结构中发现旅客共同出行规律。

2 基于Louvain算法的社区划分方法

Louvain算法是一种基于聚类法的社区划分算法，该算法能够快速有效地对大型网络进行社区划分，且划分精准度高，能够有效辨别有层次的社区结构。Louvain算法中，两个主要的参数为模块度（Modularity，记为Q）以及模块度增量（Delta Modularity，记为ΔQ）[3]。其中模块度Q能够描述划分的社区内部节点的紧密程度，取值范围在[0,1]之间，该值越大，表示划分效果越好。其计算公式如下：

式中，∑in和∑tot分别表示社区内部边权重之和以及所有与社区内部相连的边权重之和；ki,in表示节点i加入到社区c中时的权重之和。

3 旅客社会网络的社区特征分析

3.1 旅客社会网络构建

3.1.1 网络构建规则 旅客社会网络是由旅客节点之间连线构成的网络图。旅客社会网络图G可看成是由旅客节点及节点间的边集合组成，即G={N，L}，其中节点数量为g，边数量为e。节点度dni表示与第i个节点ni相连的节点个数。本文构建的旅客社会网络中，每个旅客节点都具有一起出行的行为，因此最小节点度dni=1，而理论最大节点度dni=g-1。

3.1.2 网络相关参数 最短路径：在连通子网中，两个节点的最短路径指的是从一个节点出发，到达另一个节点需要经过的最小边数[12]。

网络密度：网络密度指的是网络中实际存在的边的数量与可能存在最大边的数量的比值[12]。网络密度Δ可以展现整个网络的连通性，也可以用来衡量整个网络的紧密程度，其计算公式为：

式中，L表示旅客节点之间的边集合，g表示节点数量。

平均聚类系数：也称平均聚集系数[13]，主要体现网络中某个节点与其周围节点连接的紧密程度。通过平均聚类系数和平均最短路径可以判断某个网络是否具有小世界特性。即若一个网络与相同节点数量的随机图相比，有更小平均最短路径和更高的平均聚类系数，则说明该网络具有小世界性质。节点ni的聚类系数CC计算方式如下：

式中，v代表节点ni与所有相邻节点之间的边个数；dni表示节点ni的节点度。

3.1.3 网络整体特征 本文采用某铁路局2015年春运40 d的旅客出行数据构建旅客社会网络，原始数据集有20696133条票务数据，其中包含独立旅客共计12569600人。本文构建的铁路旅客社会网络包含4152829个旅客节点，4230808条边，边的最大权重值为34，最小权重值为1，平均边权重为2.79。由此可见，拥有一起出行行为的铁路旅客数量占该铁路春运数据集中旅客总数的33.03%，说明旅客一起出行的现象普遍存在。其中，最大连通子网包含1476个节点，5152条边，节点的平均度为6.981。网络的平均路径长度为11.11，平均聚类系数为0.688，网络密度为0.005。如果构建与最大连通子网对应的节点数量与边数量相当的随机网络，其网络直径为14，平均路径长度为4.53，平均聚类系数为0.005，网络密度为0.002。可见，最大连通子网的平均聚类系数远远超过对应的随机网络的平均聚类系数，网络密度也大于随机网络的密度，但平均路径长度却远大于随机网络。由此可见，铁路旅客社会网络最大连通子网的小世界特性不明显。同时，铁路旅客社会网络的聚类系数较高，说明网络中存在凝聚程度高的结构。因此需要对网络进行社区划分，以更好地分析网络拓扑结构。

3.2 旅客社会网络的社区划分

利用Louvian算法对铁路旅客社会网络进行社区划分。在划分的过程中，随着解析度的增大，社区化模块度逐渐降低，所划分的社区数量也逐渐减少。不同解析度对应的社区划分结果如图1所示，根据图中不同的划分结果，决定将社区划分的模块化度控制在0.8以上，取resolution的取值为4.5，将网络划分为13个社区。

图1 不同解析度情况下模块化度与社区数量变化图Fig.1 Modularization degree and community quantity change diagram under different resolutions

3.3 社区划分结果与分析

图2 社区可视化效果图Fig.2 Community visualization effect

在社区划分结果中，根据社区规模将13个社区编号重新编号。每个社区的网络相关测度以及同等规模的随机网络的平均聚类系数和路径长度如表1所示。在13个社区中，规模较大的两个社区的可视化效果如图2所示。图2中节点面积的大小表示该节点的节点度，即该旅客节点春运期间与其共同出行旅客的数量。

在节点数量超过100的6个社区中，1号社区节点最多，数量达到353个，包含1477条边。除了5号社区之外，伴随着社区结构的规模增加，社区的平均节点度有减少的趋势。1号网络节点平均度最高，为8.368，6号网络的节点度最低，为5.049。社区的密度随着社区规模的减少有增大的趋势，密度最大的社区为3号社区，其网络密度为0.06，同时3号节点对间的平均路径长度为3.534，在六个社区中是最短的平均路径。结合3号社区的密度以及平均路径长度，可以看出3号社区中节点的聚集程度最，旅客的关系较为密切。

由表1观察可知，每个社区的网络密度都远远大于整体子网。各社区与同等规模的随机网络的平均聚类系数和平均路径长度比较可知，无论是规模最大的1号社区还是规模最小的13号社区，其平均路径长度与对应随机网络相差较小，但是它们的平均聚类系数都远远超过了相应的随机网络，说明它们都具备小世界特性。综上所述，Louvain算法能够非常高质量地划分旅客社会网络。边

表1 社区特征表Table 1 Community characteristics

4 结论与展望

本文利用Louvain算法对铁路旅客社会网络的最大连通子网进行社区划分。经过对划分结果的分析，发现每一个社区内部节点的紧密程度都高于最大连通子网，且都具备非常显著的小世界特征，说明Louvain算法对铁路旅客社会网络社区划分的结果十分理想。Louvain算法能将铁路旅客社会网络迅速地划分为联系紧密的社区团体，有利于铁路旅客社会网络的进一步研究和分析。但其在划分的过程中并不能考虑旅客共同出行距离，共同出行时间等特征，在后续的研究过程中，将考虑结合铁路旅客社会网络的节点属性与结构特征，对Louvain算法进行相应的优化，使其能够更加精确地划分旅客出行团体。