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

徐 進(jìn),鄧樂齡

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

2.西南交通大學(xué)“服務(wù)科學(xué)與創(chuàng)新”四川省重點(diǎn)實(shí)驗(yàn)室,四川 成都 610031

1 引 言

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

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

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

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

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

3.1 旅客社會(huì)網(wǎng)絡(luò)構(gòu)建

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論與展望

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