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

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

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

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

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

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

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

1 算法思想

1.1 思想描述

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

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

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

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

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

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

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

1.2 改進后的算法的偽代碼

為了更好地理解改進后的算法，給出了算法的偽代碼。改進的Louvain社團劃分算法為：

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

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

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

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

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

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

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

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

3 總 結(jié)

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

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