基于Louvain算法的鐵路旅客社會網(wǎng)絡社區(qū)劃分研究

徐 進,鄧樂齡

1.西南交通大學 經(jīng)濟管理學院,四川 成都 610031

2.西南交通大學“服務科學與創(chuàng)新”四川省重點實驗室,四川 成都 610031

1 引 言

隨著我國軌道交通行業(yè)的飛速發(fā)展，鐵路客運量也不斷攀升。基于社會網(wǎng)絡的旅客出行行為研究能幫助客運部門了解旅客團體出行特征，提升服務質量[1,2]。對于旅客社會網(wǎng)絡中整體緊密度較低的連通子網(wǎng)，需要進行社區(qū)劃分，才能夠對網(wǎng)絡拓撲結構進行更深入的分析。由于鐵路客運量巨大，基于鐵路票務數(shù)據(jù)構建的旅客社會網(wǎng)絡規(guī)模也十分龐大，因此，相應的社區(qū)劃分算法必須具備高效和快速的特點。Louvain算法是一種基于圖凝聚思想的層次社區(qū)劃分算法[3-5]，它利用模塊度[6]來評價劃分質量，在面對大型網(wǎng)絡時也能高效率地完成社區(qū)劃分，并且其能夠在非監(jiān)督（不用設定社區(qū)數(shù)量）的情況下完成社區(qū)的劃分。Renaud Lambiotte[7]認為使用模塊度為質量函數(shù)的社區(qū)劃分算法容易對特定結構的模型產(chǎn)生偏差，因此，加入解析度（Resolution）來靈活地控制社區(qū)劃分數(shù)量以及規(guī)模。Traag[8]調整了Louvain算法中節(jié)點加入社區(qū)時的移動策略，使網(wǎng)絡整體模塊度變動較小的情況下完成了Louvain算法加速。吳祖峰等人[9]在社區(qū)移動聚合過程中直接移除葉節(jié)點，提高Louvain算法的運行效率。吳衛(wèi)江[10]提出了基于Louvain的并行社區(qū)劃分方法，提高了社區(qū)劃分效率。林定等人[11]在Louvain社區(qū)劃分的基礎上結合三維樹形映射表達社區(qū)劃分結果。本文利用春運期間的鐵路客運大數(shù)據(jù)，構建鐵路旅客社會網(wǎng)絡，并利用Louvain算法將最大連通子網(wǎng)進行社區(qū)劃分，進一步研究最大連通子網(wǎng)的網(wǎng)絡拓撲結構，并從社區(qū)結構中發(fā)現(xiàn)旅客共同出行規(guī)律。

2 基于Louvain算法的社區(qū)劃分方法

Louvain算法是一種基于聚類法的社區(qū)劃分算法，該算法能夠快速有效地對大型網(wǎng)絡進行社區(qū)劃分，且劃分精準度高，能夠有效辨別有層次的社區(qū)結構。Louvain算法中，兩個主要的參數(shù)為模塊度（Modularity，記為Q）以及模塊度增量（Delta Modularity，記為ΔQ）[3]。其中模塊度Q能夠描述劃分的社區(qū)內(nèi)部節(jié)點的緊密程度，取值范圍在[0,1]之間，該值越大，表示劃分效果越好。其計算公式如下：

式中，∑in和∑tot分別表示社區(qū)內(nèi)部邊權重之和以及所有與社區(qū)內(nèi)部相連的邊權重之和；ki,in表示節(jié)點i加入到社區(qū)c中時的權重之和。

3 旅客社會網(wǎng)絡的社區(qū)特征分析

3.1 旅客社會網(wǎng)絡構建

3.1.1 網(wǎng)絡構建規(guī)則 旅客社會網(wǎng)絡是由旅客節(jié)點之間連線構成的網(wǎng)絡圖。旅客社會網(wǎng)絡圖G可看成是由旅客節(jié)點及節(jié)點間的邊集合組成，即G={N，L}，其中節(jié)點數(shù)量為g，邊數(shù)量為e。節(jié)點度dni表示與第i個節(jié)點ni相連的節(jié)點個數(shù)。本文構建的旅客社會網(wǎng)絡中，每個旅客節(jié)點都具有一起出行的行為，因此最小節(jié)點度dni=1，而理論最大節(jié)點度dni=g-1。

3.1.2 網(wǎng)絡相關參數(shù) 最短路徑：在連通子網(wǎng)中，兩個節(jié)點的最短路徑指的是從一個節(jié)點出發(fā)，到達另一個節(jié)點需要經(jīng)過的最小邊數(shù)[12]。

網(wǎng)絡密度：網(wǎng)絡密度指的是網(wǎng)絡中實際存在的邊的數(shù)量與可能存在最大邊的數(shù)量的比值[12]。網(wǎng)絡密度Δ可以展現(xiàn)整個網(wǎng)絡的連通性，也可以用來衡量整個網(wǎng)絡的緊密程度，其計算公式為：

式中，L表示旅客節(jié)點之間的邊集合，g表示節(jié)點數(shù)量。

平均聚類系數(shù)：也稱平均聚集系數(shù)[13]，主要體現(xiàn)網(wǎng)絡中某個節(jié)點與其周圍節(jié)點連接的緊密程度。通過平均聚類系數(shù)和平均最短路徑可以判斷某個網(wǎng)絡是否具有小世界特性。即若一個網(wǎng)絡與相同節(jié)點數(shù)量的隨機圖相比，有更小平均最短路徑和更高的平均聚類系數(shù)，則說明該網(wǎng)絡具有小世界性質。節(jié)點ni的聚類系數(shù)CC計算方式如下：

式中，v代表節(jié)點ni與所有相鄰節(jié)點之間的邊個數(shù)；dni表示節(jié)點ni的節(jié)點度。

3.1.3 網(wǎng)絡整體特征 本文采用某鐵路局2015年春運40 d的旅客出行數(shù)據(jù)構建旅客社會網(wǎng)絡，原始數(shù)據(jù)集有20696133條票務數(shù)據(jù)，其中包含獨立旅客共計12569600人。本文構建的鐵路旅客社會網(wǎng)絡包含4152829個旅客節(jié)點，4230808條邊，邊的最大權重值為34，最小權重值為1，平均邊權重為2.79。由此可見，擁有一起出行行為的鐵路旅客數(shù)量占該鐵路春運數(shù)據(jù)集中旅客總數(shù)的33.03%，說明旅客一起出行的現(xiàn)象普遍存在。其中，最大連通子網(wǎng)包含1476個節(jié)點，5152條邊，節(jié)點的平均度為6.981。網(wǎng)絡的平均路徑長度為11.11，平均聚類系數(shù)為0.688，網(wǎng)絡密度為0.005。如果構建與最大連通子網(wǎng)對應的節(jié)點數(shù)量與邊數(shù)量相當?shù)碾S機網(wǎng)絡，其網(wǎng)絡直徑為14，平均路徑長度為4.53，平均聚類系數(shù)為0.005，網(wǎng)絡密度為0.002?？梢?，最大連通子網(wǎng)的平均聚類系數(shù)遠遠超過對應的隨機網(wǎng)絡的平均聚類系數(shù)，網(wǎng)絡密度也大于隨機網(wǎng)絡的密度，但平均路徑長度卻遠大于隨機網(wǎng)絡。由此可見，鐵路旅客社會網(wǎng)絡最大連通子網(wǎng)的小世界特性不明顯。同時，鐵路旅客社會網(wǎng)絡的聚類系數(shù)較高，說明網(wǎng)絡中存在凝聚程度高的結構。因此需要對網(wǎng)絡進行社區(qū)劃分，以更好地分析網(wǎng)絡拓撲結構。

3.2 旅客社會網(wǎng)絡的社區(qū)劃分

利用Louvian算法對鐵路旅客社會網(wǎng)絡進行社區(qū)劃分。在劃分的過程中，隨著解析度的增大，社區(qū)化模塊度逐漸降低，所劃分的社區(qū)數(shù)量也逐漸減少。不同解析度對應的社區(qū)劃分結果如圖1所示，根據(jù)圖中不同的劃分結果，決定將社區(qū)劃分的模塊化度控制在0.8以上，取resolution的取值為4.5，將網(wǎng)絡劃分為13個社區(qū)。

圖1 不同解析度情況下模塊化度與社區(qū)數(shù)量變化圖Fig.1 Modularization degree and community quantity change diagram under different resolutions

3.3 社區(qū)劃分結果與分析

圖2 社區(qū)可視化效果圖Fig.2 Community visualization effect

在社區(qū)劃分結果中，根據(jù)社區(qū)規(guī)模將13個社區(qū)編號重新編號。每個社區(qū)的網(wǎng)絡相關測度以及同等規(guī)模的隨機網(wǎng)絡的平均聚類系數(shù)和路徑長度如表1所示。在13個社區(qū)中，規(guī)模較大的兩個社區(qū)的可視化效果如圖2所示。圖2中節(jié)點面積的大小表示該節(jié)點的節(jié)點度，即該旅客節(jié)點春運期間與其共同出行旅客的數(shù)量。

在節(jié)點數(shù)量超過100的6個社區(qū)中，1號社區(qū)節(jié)點最多，數(shù)量達到353個，包含1477條邊。除了5號社區(qū)之外，伴隨著社區(qū)結構的規(guī)模增加，社區(qū)的平均節(jié)點度有減少的趨勢。1號網(wǎng)絡節(jié)點平均度最高，為8.368，6號網(wǎng)絡的節(jié)點度最低，為5.049。社區(qū)的密度隨著社區(qū)規(guī)模的減少有增大的趨勢，密度最大的社區(qū)為3號社區(qū)，其網(wǎng)絡密度為0.06，同時3號節(jié)點對間的平均路徑長度為3.534，在六個社區(qū)中是最短的平均路徑。結合3號社區(qū)的密度以及平均路徑長度，可以看出3號社區(qū)中節(jié)點的聚集程度最，旅客的關系較為密切。

由表1觀察可知，每個社區(qū)的網(wǎng)絡密度都遠遠大于整體子網(wǎng)。各社區(qū)與同等規(guī)模的隨機網(wǎng)絡的平均聚類系數(shù)和平均路徑長度比較可知，無論是規(guī)模最大的1號社區(qū)還是規(guī)模最小的13號社區(qū)，其平均路徑長度與對應隨機網(wǎng)絡相差較小，但是它們的平均聚類系數(shù)都遠遠超過了相應的隨機網(wǎng)絡，說明它們都具備小世界特性。綜上所述，Louvain算法能夠非常高質量地劃分旅客社會網(wǎng)絡。邊

表1 社區(qū)特征表Table 1 Community characteristics

4 結論與展望

本文利用Louvain算法對鐵路旅客社會網(wǎng)絡的最大連通子網(wǎng)進行社區(qū)劃分。經(jīng)過對劃分結果的分析，發(fā)現(xiàn)每一個社區(qū)內(nèi)部節(jié)點的緊密程度都高于最大連通子網(wǎng)，且都具備非常顯著的小世界特征，說明Louvain算法對鐵路旅客社會網(wǎng)絡社區(qū)劃分的結果十分理想。Louvain算法能將鐵路旅客社會網(wǎng)絡迅速地劃分為聯(lián)系緊密的社區(qū)團體，有利于鐵路旅客社會網(wǎng)絡的進一步研究和分析。但其在劃分的過程中并不能考慮旅客共同出行距離，共同出行時間等特征，在后續(xù)的研究過程中，將考慮結合鐵路旅客社會網(wǎng)絡的節(jié)點屬性與結構特征，對Louvain算法進行相應的優(yōu)化，使其能夠更加精確地劃分旅客出行團體。