改進(jìn)的Louvain社團(tuán)劃分算法

吳祖峰，王鵬飛，秦志光，蔣紹權(quán)

(電子科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院 成都 611731)

在研究復(fù)雜的社會、技術(shù)以及信息系統(tǒng)時，常把這些系統(tǒng)描述成網(wǎng)絡(luò)。在這樣的關(guān)系網(wǎng)絡(luò)中，節(jié)點代表一個成員，而邊代表成員之間的關(guān)系[1]。社團(tuán)劃分是指根據(jù)網(wǎng)絡(luò)的屬性特征把關(guān)系網(wǎng)絡(luò)中各個節(jié)點劃分到各個具有特殊含義的社團(tuán)中。社團(tuán)是指在其內(nèi)部點之間的連接很緊密。而在社團(tuán)之間的連接相對比較松散。通過將社會生活中的關(guān)系網(wǎng)絡(luò)抽象成計算機(jī)能夠表示的圖，之后運用社團(tuán)劃分算法，根據(jù)圖的某種特性將圖劃分成一個個子圖(即社團(tuán))。

現(xiàn)實中的網(wǎng)絡(luò)不同于一個隨機(jī)網(wǎng)絡(luò)，它有很強(qiáng)的結(jié)構(gòu)特征。所以可以根據(jù)其結(jié)構(gòu)特征進(jìn)行社團(tuán)劃分。隨著社會的發(fā)展，人與人之間的關(guān)系越來越密切，現(xiàn)實生活中各種關(guān)系網(wǎng)絡(luò)也在不斷擴(kuò)大，其復(fù)雜程度也日益加大。人與人之間的關(guān)系網(wǎng)絡(luò)包含了很多有意義的特性，依據(jù)這些特性可以把網(wǎng)絡(luò)進(jìn)行劃分，從而便于理解網(wǎng)絡(luò)的結(jié)構(gòu)情況，以服務(wù)于我們的生活、工作、商業(yè)、國防等。

網(wǎng)絡(luò)劃分的算法有很多種，主要分為以下兩種：一種是分離法，找出社團(tuán)之間的邊把它們從網(wǎng)絡(luò)中移除[2-3]；一種是聚合法，將聯(lián)系緊密的點聚合為一個社團(tuán)[4-5]，并通過優(yōu)化某個相關(guān)變量的函數(shù)來實現(xiàn)聚合[6-7]。

根據(jù)兩類劃分算法的結(jié)果分析，聚合算法比分離算法好，且聚合算法的效率也相對較高。由于這些原因，聚合算法吸引了很多學(xué)者做了大量相關(guān)研究。文獻(xiàn)[4]提出了一個基于模塊屬性的測量方法。文中引入了一個變量，該變量被稱作模塊度，用于衡量社團(tuán)劃分結(jié)果的合理性。其原理是用某種劃分結(jié)果的模塊內(nèi)聚性與隨機(jī)劃分結(jié)果的內(nèi)聚性的差值對劃分結(jié)果進(jìn)行評測。因為要找到最優(yōu)的模塊性劃分是一個相當(dāng)困難的問題[8]，所以基于模塊度的社團(tuán)劃分算法的研究仍然在繼續(xù)。該模塊度對后來的社團(tuán)劃分有很重要的影響，很多有影響的算法都是基于該特性進(jìn)行算法設(shè)計的。隨后，文獻(xiàn)[9]提出了一個新的算法，采用貪心算法對模塊度函數(shù)進(jìn)行求解，得到了近似最優(yōu)結(jié)果。通過將測量公式運用于劃分算法，并利用模塊度增量[9]，使社團(tuán)劃分的算法效率大大提高。但是用該算法處理大型復(fù)雜網(wǎng)絡(luò)時，其所消耗的計算時間相當(dāng)長。文獻(xiàn)[10]提出了基于模塊度的一個快速算法——Louvain算法。該算法可以快速處理具有數(shù)以億計節(jié)點的網(wǎng)絡(luò)，用模塊性對社團(tuán)劃分的質(zhì)量進(jìn)行衡量，其值位于?1到1之間[2,11]。如果模塊性的值越大，說明社團(tuán)劃分的質(zhì)量越高。

本文的算法就是基于這個算法改進(jìn)而來的。在現(xiàn)實網(wǎng)絡(luò)中常常會有很多葉子節(jié)點。特別是對于層級結(jié)構(gòu)比較突出的網(wǎng)絡(luò)。所謂葉子節(jié)點就是指其只有一條邊與其他點相連，也屬于一種邊緣節(jié)點。該情況更多的會出現(xiàn)在等級分層的現(xiàn)實網(wǎng)絡(luò)中，如行政機(jī)關(guān)、學(xué)校、公司等等，但是這些情況在原算法中并未考慮，而葉節(jié)點是可以利用剪枝處理來加快處理速度。改進(jìn)算法通過對葉節(jié)點進(jìn)行剪枝處理，從而提高算法的處理速度。

1 算法思想

1.1 思想描述

Louvain算法是基于模塊性的算法，在一個有權(quán)的網(wǎng)絡(luò)中，模塊性的定義為：

式中，Aij表示連接節(jié)點i與j邊的權(quán)值；Ki表示和節(jié)點i相連的邊的權(quán)值之和；ci表示i所屬的社團(tuán)。?(u,v)表示u與v是否為同一個社團(tuán)，如果u與v為同一個社團(tuán)此值為1，否則為0；

不斷遍歷網(wǎng)絡(luò)中的點，將其從原來的社團(tuán)取出，計算該點加入到各個社團(tuán)產(chǎn)生的模塊性增量，從這些社團(tuán)中挑選一個對應(yīng)模塊性增量最大的社團(tuán)，把該點加進(jìn)去，直到?jīng)]有點可以移動，將各個社團(tuán)合并成一個超點。重復(fù)上述步驟，直到模塊性不再增加[10]。模塊性增量是指將一個點從原來的社團(tuán)取出加入另一個社團(tuán)后，模塊性的值發(fā)生變化，有：

式中，∑in表示在社團(tuán)C中的所有邊權(quán)值之和；C表示指點a要加入的社團(tuán)；a表示將要移動的節(jié)點；表示i點到C的所有邊的權(quán)值之和；∑tot表示所有連接到社團(tuán)C的邊的權(quán)值之和。

葉子節(jié)點只和一個其他節(jié)點相連接。而劃分結(jié)果是要避免單獨節(jié)點歸屬于一個社團(tuán)，除非該節(jié)點是孤點(沒有邊)。因此對于葉節(jié)點來說，其必然要劃歸到與其相連點所在的社團(tuán)中，所以相關(guān)的很多運算可以避免。如可以不用計算ΔQ而直接將葉節(jié)點移入到相應(yīng)的社團(tuán)，從而使算法的效率提高。帶葉節(jié)點的網(wǎng)絡(luò)如圖1所示，圖中，黑色節(jié)點有3個葉節(jié)點，在Louvain算法中要對這3個葉節(jié)點分別進(jìn)行處理，而在改進(jìn)算法中直接將其劃歸于黑色節(jié)點所在的社團(tuán)。通常葉節(jié)點只在第一層劃分的時候存在，而一旦形成超點后就不再有葉節(jié)點了。所以改進(jìn)算法是對算法的第一層劃分進(jìn)行改進(jìn)。第一層劃分處理的數(shù)據(jù)量是最大的。隨著層數(shù)的增高，節(jié)點數(shù)也隨之減少。所以改進(jìn)后的算法的明顯提高了算法效率。

圖1 帶葉節(jié)點的網(wǎng)絡(luò)

Louvain算法主要分為兩個步驟：1) 將各個節(jié)點不斷的在各個社團(tuán)中遷移，直到所有模塊度增量不再為正值；2) 將各個社團(tuán)合并成一個超點。這兩個步驟運行的結(jié)果產(chǎn)生一個層級，層級不斷提高，直到模塊度的值不再增加，算法結(jié)束。改進(jìn)算法就是在第一步中遷移節(jié)點的時候加入剪枝判斷，如果為葉節(jié)點，將后來的所有運算跳過，直接將該點從原社團(tuán)移入該點鄰接點所在的社團(tuán)中。

1.2 改進(jìn)后的算法的偽代碼

為了更好地理解改進(jìn)后的算法，給出了算法的偽代碼。改進(jìn)的Louvain社團(tuán)劃分算法為：

輸入 用鄰接表表示的網(wǎng)絡(luò)圖G(V，E)

輸出 對進(jìn)行G(V，E)劃分后的結(jié)果

2 實驗結(jié)果與分析

為了驗證算法的有效性，分別用改進(jìn)算法和Louvain算法處理了18組程序生成的數(shù)據(jù)集和某個機(jī)構(gòu)一周內(nèi)的郵件數(shù)據(jù)集。通過對比運行結(jié)果，發(fā)現(xiàn)改進(jìn)算法有比較明顯的優(yōu)勢。

改進(jìn)算法在處理葉節(jié)點較多的網(wǎng)絡(luò)時優(yōu)勢比較明顯，對應(yīng)于現(xiàn)實關(guān)系網(wǎng)絡(luò)，層級結(jié)構(gòu)比較明顯的網(wǎng)絡(luò)葉節(jié)點往往比較多。因此，本文根據(jù)層級結(jié)構(gòu)的特征，用程序生成了18組實驗數(shù)據(jù)集。每組數(shù)據(jù)集中包含了約500 000個節(jié)點。18組數(shù)據(jù)集中的葉節(jié)點所占的比重不同。

圖2顯示了改進(jìn)后算法比Louvain算法效率有提升。豎軸的百分比(1?改進(jìn)后算法運行時間/原始算法運行時間)。當(dāng)數(shù)據(jù)集的葉節(jié)點數(shù)量所占總節(jié)點數(shù)量的百分比低于10%的時候，改進(jìn)算法的優(yōu)勢體現(xiàn)的不是很明顯。當(dāng)葉節(jié)點數(shù)量達(dá)到20%的時候改進(jìn)算法相對于Louvain算法所用時間減少了0.706%。當(dāng)葉節(jié)點數(shù)量達(dá)到30%的時候改進(jìn)算法相對于Louvain算法所用時間減少了1.324%。當(dāng)葉節(jié)點數(shù)量達(dá)到40%的時候改進(jìn)算法相對于Louvain算法所用時間減少了2.083%。當(dāng)葉節(jié)點數(shù)量到50%的時候改進(jìn)算法相對于Louvain算法所用時間減少了2.736%。當(dāng)葉節(jié)點數(shù)量達(dá)到60%的時候改進(jìn)算法相對于Louvain算法所用時間減少了4.081%。同時計算了改進(jìn)算法和Louvain算法劃分結(jié)果的模塊度，發(fā)現(xiàn)兩種結(jié)果所得出的模塊度的值完全一樣。所以改進(jìn)算法相對于Louvain算法并沒有改變劃分結(jié)果的準(zhǔn)確度。

圖2 改進(jìn)前后算法對比結(jié)果

為了驗證改進(jìn)算法對于實際網(wǎng)絡(luò)有同樣的效果，本文采集了某個機(jī)構(gòu)一周內(nèi)收發(fā)的郵件。用該郵件數(shù)據(jù)形成一個網(wǎng)絡(luò)，發(fā)件人和收件人用節(jié)點表示，郵件用邊表示。在該郵件網(wǎng)絡(luò)中，有23 671個節(jié)點和306 184條邊。分別用改進(jìn)算法和原始算法對該網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行處理，結(jié)果發(fā)現(xiàn)改進(jìn)算法相對于原始算法所用時間減少了3.931%，且兩者劃分出的社團(tuán)的模塊度完全一致。所以本文算法在現(xiàn)實社交網(wǎng)絡(luò)中相對于Louvain算法仍有明顯的優(yōu)勢。

3 總 結(jié)

由于改進(jìn)后的算法主要是對葉子節(jié)點進(jìn)行優(yōu)化，更適合用于處理葉子節(jié)點比較多的網(wǎng)絡(luò)。在對網(wǎng)絡(luò)處理的初期，會有很多葉子節(jié)點，在第一次進(jìn)行社團(tuán)劃分的時候用改進(jìn)算法，隨著超點的形成，再采用Louvain算法。

以上只是對算法運行結(jié)果的第一層進(jìn)行了改進(jìn)。到達(dá)第二層時由于每個超點都包含多個節(jié)點，所以每個超點相對于原圖來說，都不是葉節(jié)點，因此不能使用改進(jìn)的算法。但是對于一些網(wǎng)絡(luò)，可以預(yù)測或者人為規(guī)定它劃分出的每個社團(tuán)的節(jié)點個數(shù)不會少于某個值N時，可以對算法每一層都進(jìn)行改進(jìn)。只要某個葉子超點內(nèi)的節(jié)點數(shù)不超過N，就可以將其直接劃歸到其鄰居節(jié)點所在的社團(tuán)中，特別是在一些等級比較嚴(yán)格的網(wǎng)絡(luò)，在處理的過程中隨著每一層中低級葉節(jié)點的消失，同時新的葉子超點在不斷的出現(xiàn)，這樣改進(jìn)算法仍然可以使用，從而進(jìn)一步提高了效率。

[1] NEWMAN M E J, BARABASI A L, WATTS D J. The structure and dynamics of networks[M]. Princeton, USA:Princeton University Press, 2006.

[2] GIRVAN M, NEWMAN M E J. Improved spectral algorithm for the detection of network communities[J]. Proc Natl Acad Sci USA, 2002(99): 7821-7826.

[3] RADICCHI F, CASTELLANO C, CECCONI F, et al.Defining and identifying communities in networks[J]. Proc Natl Acad Sci USA, 2004(101): 2658-2663.

[4] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Phys Rev E, 2004,69(2): 026113-1-026113-15.

[5] CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very large networks[J]. Phys Rev E,2004, 70(6): 066111-1-066111-6.

[6] WU F, HUBERMAN B A. Finding communities in linear time: a physics approach[J]. Phys J B, 2003, 38(2): 331-338.

[7] NEWMAN M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Phys Rev E, 2006,74(3): 036104-1-036104-19.

[8] BRANDES U, DELLING D, GAERTLER M, et al.Maximizing modularity is hard[EB/OL]. [2010-05-20].http://arxiv.org/abs/physics/0608255.

[9] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Phys Rev E, 2004, 69(6):066133-1- 066133-5.

[10] VINCENT D B, GUILLAUME J L, RENAUD L, et al.Fast unfolding of communities in large network[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008(10):1-12.

[11] NEWMAN M E J. Modularity and community structure in networks[J]. Proc Natl Acad Sci USA, 2006(103): 8577-8582.