基于用戶特征和鏈接關(guān)系的Louvain算法研究*

胡 健 薛龍龍

（北方工業(yè)大學(xué) 北京 100144）

1 引言

社區(qū)存在于人類社會(huì)所構(gòu)成的各種網(wǎng)絡(luò)中，如社區(qū)可以是科學(xué)家合作網(wǎng)絡(luò)中處于同一個(gè)研究領(lǐng)域的研究群組、引文網(wǎng)絡(luò)中處于同一個(gè)課題的論文、社交網(wǎng)絡(luò)中具備相似愛好的興趣團(tuán)體等［1］。在網(wǎng)絡(luò)科學(xué)文獻(xiàn)中，網(wǎng)絡(luò)社區(qū)檢測問題一直受眾多學(xué)者的廣泛研究［2］。隨著微博、微信等社交網(wǎng)絡(luò)的蓬勃發(fā)展，社交數(shù)據(jù)呈爆炸式的增長，挖掘和分析社交網(wǎng)絡(luò)結(jié)構(gòu)對(duì)于了解和預(yù)測社交網(wǎng)絡(luò)中的關(guān)聯(lián)關(guān)系具有重要意義［3～6］。社區(qū)內(nèi)部的成員相對(duì)于外部的成員是緊密聯(lián)系的。一種流行且快速的社區(qū)檢測方法是基于模塊度函數(shù)優(yōu)化的。Newman和Girvan共同提出了模塊度函數(shù)。隨后，Newman提出通過優(yōu)化模塊化函數(shù)來檢測社區(qū)的思想［2］。Louvain算法是一種基于模塊度函數(shù)優(yōu)化的算法，有易于理解、非監(jiān)督、計(jì)算快速的優(yōu)點(diǎn)且能夠發(fā)現(xiàn)層次性的社區(qū)結(jié)構(gòu)［7］，因此Louvain社區(qū)發(fā)現(xiàn)算法受到多數(shù)研究者的青睞。

在研究Louvain社區(qū)發(fā)現(xiàn)算法時(shí)候，多數(shù)研究者未考慮邊的實(shí)際權(quán)值及有向邊對(duì)社區(qū)發(fā)現(xiàn)結(jié)果的影響。本文從社交網(wǎng)絡(luò)中用戶的特征及鏈接關(guān)系可以進(jìn)一步改善Louvain社區(qū)發(fā)現(xiàn)算法的結(jié)果［8～9］出發(fā)，提出一種基于用戶的特征及鏈接關(guān)系的混合AHP層次分析法、PageRank算法思想及Louvain算法的社區(qū)發(fā)現(xiàn)策略APL。該策略將網(wǎng)絡(luò)中用戶的特征及鏈接關(guān)系進(jìn)行混合分析。首先利用AHP層次分析法對(duì)提取出的用戶特征進(jìn)行權(quán)重劃分，然后計(jì)算各個(gè)用戶的初始影響力并利用PageRank思想計(jì)算用戶的最終影響力，再根據(jù)用戶的最終影響力擴(kuò)散計(jì)算網(wǎng)絡(luò)中各邊的權(quán)值，最后，運(yùn)用Louvain社區(qū)發(fā)現(xiàn)方法對(duì)初始化后的帶權(quán)網(wǎng)絡(luò)進(jìn)行社區(qū)劃分。本文所提出的方法能進(jìn)一步改善社區(qū)發(fā)現(xiàn)的結(jié)果，使結(jié)果更符合實(shí)際。

2 相關(guān)工作

由于大型網(wǎng)絡(luò)數(shù)據(jù)集的可用性日益增加以及網(wǎng)絡(luò)對(duì)日常生活的影響，近年來，學(xué)者們對(duì)快速社區(qū)發(fā)現(xiàn)算法的研究產(chǎn)生很大興趣。關(guān)于社交網(wǎng)絡(luò)中的社區(qū)檢測問題，相關(guān)的社區(qū)發(fā)現(xiàn)算法主要分為分裂的算法和凝聚的算法［5］。分裂的算法檢測社區(qū)間鏈接并將其從網(wǎng)絡(luò)中移除。凝聚的算法遞歸地合并相似的節(jié)點(diǎn)或社區(qū)。兩類算法的優(yōu)化目標(biāo)都是基于最大化目標(biāo)函數(shù)［7］。

典型的分裂算法是GN（Girvan-Newman）算法［10］。GN算法是一種基于邊介數(shù)的分裂算法。其基本思想是不斷去除網(wǎng)絡(luò)中邊介數(shù)最大的邊，最終將網(wǎng)絡(luò)劃分為多個(gè)社區(qū)。GN算法不需要預(yù)先設(shè)定社區(qū)數(shù)量，但是由于邊介數(shù)的計(jì)算較耗時(shí)，其算法時(shí)間復(fù)雜度較高。典型的凝聚算法是Louvain算法［7］。Louvain算法是一種層次貪心算法，被公認(rèn)為是運(yùn)行最快的非重疊社區(qū)發(fā)現(xiàn)算法之一。吳祖峰等提出了一種改進(jìn)的Louvain社區(qū)劃分算法［11］，它通過對(duì)葉節(jié)點(diǎn)進(jìn)行剪枝來降低算法的運(yùn)行時(shí)間，其改進(jìn)的算法沒有提升社區(qū)劃分準(zhǔn)確度。基于Louvain算法的有向圖社區(qū)發(fā)現(xiàn)算法［12］能夠有效地發(fā)現(xiàn)大規(guī)模有向網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。使用多級(jí)細(xì)化策略改進(jìn)的Louvain算法［13］，其通過在原社區(qū)網(wǎng)絡(luò)多次執(zhí)行本地移動(dòng)的啟發(fā)式方式來確保通過節(jié)點(diǎn)之間的移動(dòng)無法進(jìn)一步優(yōu)化算法的模塊度，這種策略可能需要多次的迭代。Ludo Waltmana and Nees Jan van Eck提出的智能本地移動(dòng)算法［2］，其通過對(duì)本地移動(dòng)啟發(fā)式方法產(chǎn)生的社區(qū)構(gòu)建子網(wǎng)，在對(duì)各個(gè)子網(wǎng)應(yīng)用本地移動(dòng)啟發(fā)式方法，使得算法無法通過社區(qū)分割和節(jié)點(diǎn)集移動(dòng)來進(jìn)一步提高Louvain算法的模塊度，這種策略可能需要多次的迭代。李雷、閆光輝等提出了基于孤立節(jié)點(diǎn)分離策略的改進(jìn)Louvain算法［14］，該算法在每次迭代中將輸入網(wǎng)絡(luò)的孤立節(jié)點(diǎn)提前分離出去，只令其中的連通節(jié)點(diǎn)實(shí)際參與迭代過程，并在存儲(chǔ)社區(qū)發(fā)現(xiàn)結(jié)果時(shí)將孤立節(jié)點(diǎn)和非孤立節(jié)點(diǎn)分開存儲(chǔ)，其進(jìn)一步提高了Louvain算法的效率。A.Meligy等提出一種改進(jìn)社區(qū)發(fā)現(xiàn)結(jié)果預(yù)處理策略［8］，其根據(jù)節(jié)點(diǎn)的中間度核心性和邊的中間度核心性計(jì)算節(jié)點(diǎn)間邊的實(shí)際距離，從而改善社區(qū)發(fā)現(xiàn)算法的結(jié)果，其缺點(diǎn)是節(jié)點(diǎn)的中間度核心性和邊的中間度核心性的計(jì)算非常復(fù)雜和耗時(shí)。

在社交網(wǎng)絡(luò)中，用戶的影響力可以用于評(píng)估用戶間的實(shí)際距離，據(jù)此可以進(jìn)一步優(yōu)化Louvain社區(qū)發(fā)現(xiàn)的結(jié)果［8］。尹紅軍提出一種個(gè)性化PageR-ank算法，使結(jié)果偏向于偏好的節(jié)點(diǎn)［5］，然而，此方法需要維護(hù)n個(gè)節(jié)點(diǎn)偏好向量，內(nèi)存耗費(fèi)大且計(jì)算復(fù)雜。Tunkelang等利用Twitter用戶節(jié)點(diǎn)之間的關(guān)注關(guān)系，構(gòu)造了一張基于鏈接關(guān)系的有向圖，并且利用PageRank模型實(shí)現(xiàn)了Twitter用戶的影響力排序［15］。本文主要根據(jù)用戶特征來計(jì)算用戶的影響力，進(jìn)而計(jì)算用戶間的距離。

綜上分析，多數(shù)研究者在研究Louvain社區(qū)發(fā)現(xiàn)算法時(shí)，側(cè)重考慮Louvain社區(qū)發(fā)現(xiàn)算法的效率，且其研究大都基于無向圖，而未考慮網(wǎng)絡(luò)中邊的實(shí)際權(quán)值及其有向邊對(duì)社區(qū)發(fā)現(xiàn)結(jié)果的影響?，F(xiàn)實(shí)生活中的網(wǎng)絡(luò)大都是有向的且其數(shù)據(jù)量很大，在算法準(zhǔn)確度達(dá)到一定標(biāo)準(zhǔn)后，研究實(shí)際數(shù)據(jù)對(duì)算法的影響則更有意義。因此，本文基于真實(shí)微博數(shù)據(jù)集構(gòu)建有向網(wǎng)絡(luò)圖并且根據(jù)用戶的特征及鏈接關(guān)系迭代計(jì)算用戶間邊的真實(shí)權(quán)值，然后運(yùn)用Louvain算法進(jìn)行社區(qū)檢測，最終獲得更具實(shí)際意義的社區(qū)發(fā)現(xiàn)結(jié)果。

3 基于用戶特征和鏈接關(guān)系的社區(qū)發(fā)現(xiàn)

3.1 用戶初始影響力計(jì)算

用戶初始影響力主要根據(jù)用戶的特征，如微博中用戶的粉絲數(shù)、微博被轉(zhuǎn)發(fā)數(shù)量、微博被評(píng)論數(shù)量等，來計(jì)算。由于用戶的各個(gè)特征所占的比重是不同的，因此，本文采用AHP層次分析法［16］進(jìn)行特征權(quán)重的確定，層次分析法（Analytic Hierarchy Process，AHP）是在20世紀(jì)70年代由美國運(yùn)籌學(xué)家A.L.Saaty提出的，這是一種定性與定量相結(jié)合的決策分析方法［16］，其可以通過兩兩元素進(jìn)行重要性的比較從而確定權(quán)重，方法更為嚴(yán)謹(jǐn)。本文提出的用戶初始影響力計(jì)算公式如下：

3.2 基于鏈接關(guān)系的用戶最終影響力計(jì)算

社交網(wǎng)絡(luò)中用戶間的鏈接關(guān)系非常符合PageRank的核心思想。為了綜合考慮社交網(wǎng)絡(luò)中用戶之間的相互鏈接關(guān)系，本文首先根據(jù)用戶的特征計(jì)算用戶的初始影響力，然后根據(jù)PageRank算法思想計(jì)算用戶的最終影響力，從而得出更為準(zhǔn)確的用戶影響力值。

本文提出的計(jì)算用戶最終影響力的步驟如下：

1）從社交網(wǎng)絡(luò)的所有用戶集合U中，選取一個(gè)初始用戶Ui，作為影響力擴(kuò)散計(jì)算的起點(diǎn)，并將用戶Ui添加到集合A中（A中記錄的是已進(jìn)行過影響力擴(kuò)散的用戶）；

2）利用式（2）計(jì)算用戶的最終影響力：

其中R（x）表示x的最終影響力值，B（x）表示所有關(guān)注x的用戶，N（j）表示j用戶關(guān)注的人數(shù)，常數(shù)C為加權(quán)系數(shù)，用戶縮放用戶的最終影響力值；

3）從集合U中選取一個(gè)新的沒有進(jìn)行過最終影響力計(jì)算的用戶，將其加入集合A中，重復(fù)上述步驟，直到所有的用戶都進(jìn)行了最終影響力值的計(jì)算，則算法結(jié)束。

3.3 Louvain社區(qū)發(fā)現(xiàn)算法

Louvain是基于模塊度的社區(qū)發(fā)現(xiàn)算法，其優(yōu)化的目標(biāo)是最大化整個(gè)圖的模塊度。算法主要分為三個(gè)步驟：首先將每個(gè)節(jié)點(diǎn)初始化為一個(gè)小的社區(qū)；然后，不斷遍歷網(wǎng)絡(luò)中的所有節(jié)點(diǎn)，將其從原來的社區(qū)中取出，計(jì)算該點(diǎn)加入到各個(gè)社區(qū)產(chǎn)生的模塊度增量，如果該模塊度增量大于零，則從這些大于零的模塊度增量所對(duì)應(yīng)的簇中選出對(duì)應(yīng)模塊增量最大的簇，將該點(diǎn)與之合并，重復(fù)上述過程，直到網(wǎng)絡(luò)中所有節(jié)點(diǎn)所屬的社區(qū)不再發(fā)生變化，停止迭代；最后，將網(wǎng)絡(luò)圖進(jìn)行約簡，把一個(gè)社區(qū)內(nèi)的所有節(jié)點(diǎn)抽象成一個(gè)節(jié)點(diǎn)，新節(jié)點(diǎn)之間的權(quán)值就是原社區(qū)之間的權(quán)值，重復(fù)前兩個(gè)階段的過程，直到簇間不再發(fā)生合并為止。

3.3.1 模塊度

模塊度是Louvain算法用來評(píng)估一個(gè)社區(qū)網(wǎng)絡(luò)劃分好壞的度量方法，它的物理含義是社區(qū)內(nèi)節(jié)點(diǎn)的連邊數(shù)與隨機(jī)情況下的邊數(shù)之差，它的取值范圍是［-1/2，1），一般以Q=0.3作為網(wǎng)絡(luò)有明顯社區(qū)結(jié)構(gòu)的度量，Q值越接近1，說明發(fā)現(xiàn)的社區(qū)質(zhì)量越高。

其定義如下：

其中，Aij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間邊的權(quán)重，網(wǎng)絡(luò)不是帶權(quán)圖時(shí)，所有邊的權(quán)重初始化為1；表示所有與節(jié)點(diǎn)i相連的邊的權(quán)重之和；ci表示節(jié)點(diǎn)i所屬的社區(qū)；表示網(wǎng)絡(luò)中所有邊的權(quán)重之和。

3.3.2 模塊度增量

Louvain算法根據(jù)節(jié)點(diǎn)的模塊度增量來判斷是否將其加入另外一個(gè)社區(qū)。Louvain算法能夠產(chǎn)生層次性的社區(qū)結(jié)構(gòu)，其中計(jì)算耗時(shí)較多的是最底一層的社區(qū)劃分，節(jié)點(diǎn)按社區(qū)壓縮后，將大大縮小邊和節(jié)點(diǎn)數(shù)目，并且計(jì)算節(jié)點(diǎn)i分配到其鄰居j所在社區(qū)時(shí)的模塊度的變化只與節(jié)點(diǎn)i、j的社區(qū)有關(guān)，與其他社區(qū)無關(guān)，因此計(jì)算很快。把節(jié)點(diǎn)i分配到鄰居節(jié)點(diǎn)j所在的社區(qū)c時(shí)模塊度變化為

其中Ki，in是社區(qū)c內(nèi)節(jié)點(diǎn)與節(jié)點(diǎn)i的邊權(quán)重之和，注意：Ki，in是對(duì)應(yīng)邊權(quán)重加起來再乘以2。ΔQ分兩部分，前面部分表示把節(jié)點(diǎn)i加入到社區(qū)c后的模塊度，后一部分是節(jié)點(diǎn)i作為一個(gè)獨(dú)立社區(qū)和社區(qū)c的模塊度。

3.4 本文提出的APL社區(qū)發(fā)現(xiàn)方法的步驟

1）根據(jù)AHP層次分析法及用戶初始影響力計(jì)算公式（1）來計(jì)算用戶i的初始影響力值initPRi；

2）根據(jù)3.2節(jié)介紹的用戶影響力計(jì)算步驟及initPRi來計(jì)算用戶i的最終影響力值lastPRi；

3）根據(jù)上一步驟求出的lastPRi，求社交網(wǎng)絡(luò)中節(jié)點(diǎn)間邊的權(quán)值，公式如下：

其中weighti→j為節(jié)點(diǎn)i到節(jié)點(diǎn)j的有向邊的權(quán)值，outi為節(jié)點(diǎn)i的出度；

4）經(jīng)過前三步后，可以得到帶有實(shí)際意義邊權(quán)值的社交網(wǎng)絡(luò)矩陣W，然后利用3.3節(jié)介紹的Louvain算法進(jìn)行迭代計(jì)算，最終將得到符合實(shí)際的社區(qū)發(fā)現(xiàn)結(jié)果。

4 實(shí)驗(yàn)與分析

實(shí)驗(yàn)所用到目標(biāo)數(shù)據(jù)集來自數(shù)據(jù)堂公開的可用于學(xué)術(shù)研究的某微博數(shù)據(jù)集，其包含63641個(gè)微博用戶信息，1391718條用戶關(guān)注關(guān)系，84168條用戶的微博信息、27759條微博轉(zhuǎn)發(fā)關(guān)系。為了便于展示，本文從1391718條用戶關(guān)注關(guān)系中按數(shù)據(jù)分區(qū)方式提取出6萬條邊來研究和分析。

4.1 微博用戶特征提取及權(quán)重計(jì)算

本文僅從微博數(shù)據(jù)集提取出粉絲數(shù)、評(píng)論數(shù)、轉(zhuǎn)發(fā)數(shù)、獲贊數(shù)、微博數(shù)這5個(gè)用戶特征。根據(jù)這5個(gè)特征構(gòu)建的AHP對(duì)比矩陣如表1。

表1 AHP對(duì)比矩陣

經(jīng)AHP層次分析法計(jì)算得到這五個(gè)特征的權(quán)重依次為0.4036，0.1368，0.1368，0.0782，0.2446。

4.2 用戶最終影響力的結(jié)果與分析

表2 本文提出的用戶影響力計(jì)算方法和PageRank算法的結(jié)果對(duì)比

說明：表中的結(jié)果皆按照用戶影響力逆排序，且取部分結(jié)果。

通過對(duì)用戶影響力兩種計(jì)算方法結(jié)果的對(duì)比，可得出如下的結(jié)論：

1）若僅考慮用戶間的鏈接關(guān)系，則節(jié)點(diǎn)編號(hào)為1195230310用戶為最有影響力的用戶，若綜合考慮用戶的特征，則節(jié)點(diǎn)編號(hào)為2704048113的用戶為最有影響力的用戶，即排名更偏向于有影響力的用戶；

2）多數(shù)inf值很大用戶都不在pr值最大的幾個(gè)用戶中，而inf值排名第二的1761179351用戶，排在pr值排名的第6位，從兩種算法總的輸出結(jié)果分析得出，inf值大的用戶在pr值排名中越靠前；

3）由于微博特征數(shù)據(jù)是基于整個(gè)微博網(wǎng)絡(luò)的，而微博用戶間的鏈接關(guān)系僅僅取了6萬條，因此，1）和2）中的部分排名差異現(xiàn)象是正常的。

4.3 社區(qū)發(fā)現(xiàn)結(jié)果與分析

使用APL（混合AHP、PageRank思想及Louvain）社區(qū)發(fā)現(xiàn)方法和原Louvain算法分別對(duì)上文提到的微博數(shù)據(jù)集進(jìn)行分析，來驗(yàn)證本文提出的社區(qū)發(fā)現(xiàn)方法APL的有效性。

表3 本文提出的社區(qū)發(fā)現(xiàn)方法APL和原Louvain社區(qū)發(fā)現(xiàn)的結(jié)果對(duì)比

圖1 未改進(jìn)Louvian社區(qū)發(fā)現(xiàn)結(jié)果

圖2 APL社區(qū)發(fā)現(xiàn)結(jié)果

圖3 和圖1對(duì)應(yīng)的社區(qū)成員數(shù)占比

圖4 和圖2對(duì)應(yīng)的社區(qū)成員數(shù)占比

通過對(duì)表3及四張圖的對(duì)比分析，可得到如下的結(jié)論：

1）從表3的輸出結(jié)果可知，本文提出的APL社區(qū)發(fā)現(xiàn)方法將社區(qū)模塊度從原來的0.2625提高的0.3197；

2）從圖1和圖2可知，本文提出的社區(qū)發(fā)現(xiàn)方法和原方法挖掘到的關(guān)鍵人物是一致的，如用戶1195230310、1705586121、1265061803；

3）從圖3和圖4可知，兩種方法都檢測到6個(gè)主要的社區(qū)，只是社區(qū)人數(shù)占比不同，這和分塊選擇的6萬條數(shù)據(jù)相符合；

4）綜上分析及模塊度越大則社區(qū)發(fā)現(xiàn)結(jié)果越好的原理，因此本文提出社區(qū)發(fā)現(xiàn)方法是有效的。

5 結(jié)語

通過對(duì)微博數(shù)據(jù)中用戶的特征及其鏈接關(guān)系的分析，本文提出一種融合AHP層次分析法、PageRank算法思想和Louvain算法的社區(qū)發(fā)現(xiàn)方法，此方法在用戶鏈接關(guān)系的基礎(chǔ)上結(jié)合了用戶的特征，進(jìn)一步改善了社區(qū)發(fā)現(xiàn)的結(jié)果。雖然，可以通過Betweenness Centrality的概念先計(jì)算節(jié)點(diǎn)的中心度和邊的中心度，最后求出節(jié)點(diǎn)間邊的距離［4］，然而，此方法計(jì)算量很大且計(jì)算復(fù)雜，而本文提出的計(jì)算用戶間距離的過程簡單，能大大減少時(shí)間復(fù)雜度。為了研究的便利，本文僅從上文提到的微博數(shù)據(jù)集提取出粉絲數(shù)、評(píng)論數(shù)、轉(zhuǎn)發(fā)數(shù)、獲贊數(shù)、微博數(shù)這5個(gè)用戶特征，實(shí)際應(yīng)用中，可以提取出更多的用戶特征以進(jìn)一步優(yōu)化社區(qū)發(fā)現(xiàn)的結(jié)果。