基于最大生成樹的社團劃分算法

王 林，王海新

基于最大生成樹的社團劃分算法

王 林，王海新

(西安理工大學(xué) 自動化與信息工程學(xué)院，陜西 西安 710048)

針對層次聚類算法存在復(fù)雜度高、準確度低等問題，提出了一種基于最大生成樹的社團劃分算法。該算法重新定義了節(jié)點間相似度，并利用最大生成樹進行初始聚類，然后根據(jù)社團相似度合并局部社團得到最終劃分結(jié)果。算法不僅降低了時間復(fù)雜度，而且在劃分社團的準確度方面有所提高。將該方法在真實網(wǎng)絡(luò)與人工網(wǎng)絡(luò)上進行驗證和比對，實驗結(jié)果表明基于最大生成樹的社團劃分算法能夠快速、準確地劃分出網(wǎng)絡(luò)中的社團結(jié)構(gòu)。

社團劃分；層次聚類；最大生成樹；節(jié)點相似度

0 引言

隨著社會的發(fā)展與進步，現(xiàn)實世界涌現(xiàn)出越來越多的復(fù)雜系統(tǒng)，許多復(fù)雜系統(tǒng)都可以直接或間接地以復(fù)雜網(wǎng)絡(luò)的形式存在。因此，復(fù)雜網(wǎng)絡(luò)一直是各個學(xué)科領(lǐng)域的研究熱點。而社團結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)中的一個重要屬性，復(fù)雜網(wǎng)絡(luò)中同一社團內(nèi)節(jié)點之間連接緊密、而不同社團內(nèi)的節(jié)點之間連接稀疏[1-2]。社團結(jié)構(gòu)對于分析和了解整個網(wǎng)絡(luò)的結(jié)構(gòu)、功能及特性具有重要的意義[3]。

層次聚類算法是一類重要的社團劃分算法，它從節(jié)點出發(fā)利用節(jié)點間的相似度分層次地進行聚類，然后利用模塊度函數(shù)來確定社團的最優(yōu)劃分。層次聚類算法主要分為兩種：一種是分裂式的方法，具有代表性的算法是GN算法[4]，它通過不斷計算邊介數(shù)并移除邊介數(shù)最大的邊來劃分復(fù)雜網(wǎng)絡(luò)的社團，但是由于計算邊介數(shù)的代價較大，導(dǎo)致GN算法的復(fù)雜度比較高[5]；另一種是凝聚式算法，如Newman快速算法[6]，通過不斷合并節(jié)點并計算合并后的模塊度增量Q，選擇Q增加最多或者減少最小的合并方式進行社團合并，該算法在計算時間上比GN算法有了很大改善。之后，Clauset等人提出了CNM算法[7]，通過結(jié)合堆和二叉樹，對Newman快速算法進行了改進，使算法不僅計算高效，而且節(jié)省存儲空間；但是CNM算法在劃分社團時準確度卻不高[8]。Blondel等人提出了BGLL算法[9]，該算法起始時將網(wǎng)絡(luò)中每一個頂點視為一個局部社團，網(wǎng)絡(luò)朝著模塊度增量改變最大的方向進行合并，直到模塊度增量小于零。該算法簡單、快速，但劃分的結(jié)果受到模塊度分辨率的限制，算法準確度低[10]。Eustace等人[11]提出了一種基于局部社團合并的方法，通過重新定義節(jié)點與節(jié)點、節(jié)點與社團、社團與社團之間的相似度來衡量它們之間的關(guān)系，通過不斷合并節(jié)點或社團來達到劃分社團的目的，但是該算法容易陷入局部最優(yōu)解。由上可知，已有的層次聚類算法普遍存在計算速度快但準確度低的問題。

針對上述研究中所出現(xiàn)的問題，本文提出了一種新的層次聚類算法，該算法在最大生成樹上對社團進行初始聚類，然后逐步合并局部社團得到社團結(jié)構(gòu)。而最大生成樹包含網(wǎng)絡(luò)中所有節(jié)點，但是不包括所有邊，因此在最大生成樹上進行社團劃分可以降低算法復(fù)雜度[12]。此外，相比傳統(tǒng)的相似度度量方式，本文定義了一種新的節(jié)點相似度公式，它不僅考慮到網(wǎng)絡(luò)局部信息，而且兼顧網(wǎng)絡(luò)的全局信息，使得算法的準確性得到進一步提高。

1 最大生成樹

一個連通且不存在回路的圖稱為樹，如果一個圖G的生成子圖T是樹，則稱它為G的生成樹，一個加權(quán)的最大生成樹是G的具有最大權(quán)值的生成樹。對于一個給定網(wǎng)絡(luò)G(V,E)，其中V是節(jié)點集合，E是邊集合。在計算它的最大生成樹之前先要為每條邊賦值，本文使用節(jié)點相似度作為每條邊的權(quán)值，記為ω(vk,vk+1)，其中vk、vk+1分別為第k個節(jié)點和第k+1個節(jié)點，這里相似度等于兩節(jié)點的共同鄰居節(jié)點個數(shù)與所有的鄰居節(jié)點個數(shù)之比。構(gòu)建其最大生成樹首先從一棵空樹T開始，往集合T中逐條選擇并加入權(quán)值最大的n-1條邊，最終生成一棵包含n個節(jié)點和n-1條邊的最大生成樹。構(gòu)建最大生成樹的步驟如下：

(1)初始化集合Vnew={x}和Enew={}，其中x為起始節(jié)點；

(2)在邊集E中選擇權(quán)值最大的邊加入集合Enew中，其中u為集合Vnew中的元素，節(jié)點v∈V但v不在集合Vnew當(dāng)中。

(3)重復(fù)步驟(2)，直到所有節(jié)點都被加入到集合Vnew中。

2 利用最大生成樹劃分社團結(jié)構(gòu)

本文算法聚類部分分為兩個階段：第一階段是網(wǎng)絡(luò)的初始聚類，就是在最大生成樹上對節(jié)點進行聚類得到局部社團；第二階段是迭代合并第一階段產(chǎn)生的局部社團，直到所有的局部社團都被合并到一個社團，然后根據(jù)Q值選取網(wǎng)絡(luò)社團結(jié)構(gòu)的最佳劃分。

2.1 節(jié)點聚類

這一階段主要是在最大生成樹上把節(jié)點聚類成局部社團，即是將最大生成樹上的節(jié)點與其最相似的核節(jié)點合并為一個局部社團。

節(jié)點聚類之前首先要找到生成樹上所有的核節(jié)點。對于一個節(jié)點u，其與鄰居節(jié)點的邊權(quán)值大于ε的集合為：

Γε(u,v)={v∈Nghb(u)|ω(u,v)≥ε}

(1)

其中ω(u,v)為邊的權(quán)值。若|Γε(u,v)|>μ，則u是一個核節(jié)點。參數(shù)ε對核節(jié)點的確定有很大影響，本文使用最大生成樹的邊權(quán)值集合作為ε的候選集合。為使節(jié)點準確地劃分到局部社團中，本文新定義了一個節(jié)點相似度公式，該公式將節(jié)點間路徑考慮進去，這樣就同時兼顧了局部信息和網(wǎng)絡(luò)的全局拓撲結(jié)構(gòu)，能夠更加準確地衡量節(jié)點間的相似度。其相似度公式定義如下：

(2)

其中，ω(vk,vk+1)表示節(jié)點與其鄰居節(jié)點之間的邊權(quán)值，p(s,t)是節(jié)點s與t之間的路徑。

2.2 局部社團合并

第二階段任務(wù)就是合并局部社團，但在合并之前首先判斷是否存在核節(jié)點直接相連接的情況。若存在且它們的邊權(quán)值大于參數(shù)ε，則可直接將這種核節(jié)點所在的局部社團進行合并；反之，則迭代合并社團相似度[13]最大的兩個局部社團，這種迭代一直持續(xù)到整個網(wǎng)絡(luò)呈現(xiàn)為僅有的一個大社團。其社團相似度公式定義如下：

(3)

其中，

(4)

式(3)中num(ci,cj)表示社團ci和cj相連的邊的數(shù)量；式(4)中degree(vj)表示社團ci中任意一點的度值。

每次合并社團后都要計算相應(yīng)的網(wǎng)絡(luò)模塊度，最終選擇模塊度最大時對應(yīng)的社團結(jié)構(gòu)作為最優(yōu)劃分。

2.3 算法步驟及復(fù)雜度分析

本文算法步驟如下：

輸入：一個無向無權(quán)網(wǎng)絡(luò)G(V,E)；

輸出：網(wǎng)絡(luò)的社團結(jié)構(gòu)，Q值及參數(shù)ε的值；

(1)生成最大生成樹：首先計算網(wǎng)絡(luò)中每條邊的權(quán)值，將無向無權(quán)網(wǎng)絡(luò)G(V,E)轉(zhuǎn)換成加權(quán)網(wǎng)絡(luò)G(V,E,W)，然后生成網(wǎng)絡(luò)的最大生成樹T(V,ET)；

(2)確定核節(jié)點：對T(V,ET)上邊的權(quán)值進行排序并記錄到隊列WT中，在候選隊列WT中選擇一個新值作為ε的值，然后在最大生成樹T(V,ET)上根據(jù)式(1)計算出所有的核節(jié)點；

(3)節(jié)點聚類：計算所有節(jié)點到所有核節(jié)點的相似度S(s,t)，并選擇與其相似度最大的核節(jié)點進行合并，由此產(chǎn)生各個局部社團。判斷核節(jié)點之間是否存在直接連邊,且它們的相似度值S(s,t)>ε，如果存在就將這兩個核節(jié)點所在的局部社團直接合并；

(4)局部社團合并：計算局部社團間的相似度，選擇相似度最大的兩個局部社團進行合并，然后計算并記錄Q值；

(5)重復(fù)步驟(4)直到網(wǎng)絡(luò)合并為一個社團，找到最大的Q值并記錄到隊列Qs中；

(6)判斷隊列WT中的值是否被完全遍歷，如果沒有則重復(fù)步驟(2)～(5)，如果完全遍歷則算法結(jié)束，選擇Qs中最大的Q值及其對應(yīng)的社團結(jié)構(gòu)和ε進行輸出。

假定網(wǎng)絡(luò)中節(jié)點個數(shù)是n，邊數(shù)是m，則計算最大生成樹在最壞情況下的復(fù)雜度為O(mlogn)；假定最大生成樹上的核節(jié)點數(shù)目為k，計算節(jié)點與各個核節(jié)點相似度的復(fù)雜度為nk；k個核節(jié)點聚類成k個局部社團，將這k個局部社團聚類成一個社團需要k-1步，因此局部社團合并的時間復(fù)雜度為k-1；由于算法中將最大生成樹T(V,ET)上的邊權(quán)值作為ε的候選集合，因此在最壞的情況下,上述過程要重復(fù)執(zhí)行n-1次。綜上，基于最大生成樹的社團劃分算法在整個運行過程中的時間復(fù)雜度為O(mn)。

3 實驗結(jié)果及分析

通過本文算法對真實網(wǎng)絡(luò)進行社團劃分，然后利用人工網(wǎng)絡(luò)對該算法的運行時間和準確性進行分析。實驗在一臺4核2.3 GHz的CPU、4 GB RAM 的筆記本電腦上運行，使用MATLAB軟件進行編程和仿真，使用Gephi軟件對實驗結(jié)果進行處理和可視化。

3.1 真實網(wǎng)絡(luò)

在這里，選擇Zachary空手道俱樂部網(wǎng)作為真實網(wǎng)絡(luò)。利用本文算法首先計算出俱樂部網(wǎng)的最大生成樹，然后在最大生成樹上進行初始聚類，初始聚類結(jié)果如圖1所示。

圖1 Zachary網(wǎng)絡(luò)的最大生成樹

圖1中交替使用灰和白兩種節(jié)點顏色表示局部社團，同一顏色的節(jié)點被聚類到相同的局部社團中，這些社團再繼續(xù)聚類而形成不同的社團結(jié)構(gòu)。當(dāng)μ=3，ε=0.334時，最大生成樹上節(jié)點7、2、4、33、34都為核節(jié)點，由于核節(jié)點33、34直接相連且它們的權(quán)值為0.526大于ε，所以它們可以直接合并。本文提出的算法在俱樂部網(wǎng)上的最大Q值為0.373 3，在最大Q值時網(wǎng)絡(luò)劃分為兩個社團，其結(jié)果如圖2所示。

圖2 Q=0.373 3時算法對Zachary網(wǎng)劃分的結(jié)果

3.2 計算機生成網(wǎng)

為了進一步衡量算法的準確度，將本文算法在LFR計算機生成網(wǎng)上與其他算法進行比較。網(wǎng)絡(luò)的相應(yīng)參數(shù)設(shè)置如下：網(wǎng)絡(luò)節(jié)點數(shù)為N=1 000，平均度數(shù)Davg=4.8，最大度為Dmax=50，最小社團節(jié)點數(shù)Cmin=20，最大社團節(jié)點數(shù)Cmax=100。mu值為可變參數(shù)，它反映處于不同社團之間的邊在所有邊中所占的比例。mu值越大，表示處于不同社團之間的邊越多，社團結(jié)構(gòu)就越不明顯[14]。

3.2.1 準確性驗證

社團劃分的準確度用歸一化互信息(Normalized mutual information)[15]來衡量，它的定義如下：

(5)

NMI值表示Y劃分與X劃分的接近程度，其中X表示網(wǎng)絡(luò)的正確劃分，Y表示算法得出的社團劃分；它是一個介于0與1之間的數(shù)，NMI值越接近1表示算法劃分出的社團結(jié)構(gòu)準確度越高。

圖3給出了本文算法與CNM算法和BGLL算法在不同mu值下對計算機生成網(wǎng)劃分準確度的對比。

圖3 算法在計算機生成網(wǎng)上的對比結(jié)果

在混合參數(shù)mu<0.4時算法能完全正確地劃分出社團，隨著mu的增加，社團結(jié)構(gòu)變得越來越模糊，算法的準確度也隨之下降，但其NMI始終大于CNM算法和BGLL算法。圖3表明，本文算法對計算機生成網(wǎng)的劃分結(jié)果要優(yōu)于CNM算法和BGLL算法。

3.2.2 復(fù)雜度驗證

為了評估本文算法的運行時間效率，選擇快速Newman算法和CNM算法作為對比，其結(jié)果如圖4所示。

圖4 算法運行時間對比

其中節(jié)點數(shù)目分別從1 000增長到5 000，邊數(shù)目為節(jié)點數(shù)目的10倍。方格線代表CNM算法，圓圈線代表Newman快速算法，十字線代表本文算法。從圖中可以看出，本文算法的運行時間效率要優(yōu)于快速Newman算法，而CNM算法的復(fù)雜度近似線性。本文算法雖然在運行速度上略遜于CNM算法，但是在算法準確度上比CNM算法高，且本文復(fù)雜度在可接受的范圍內(nèi)。

4 結(jié)論與展望

針對現(xiàn)有的層次聚類算法復(fù)雜度高、準確度低等問題，本文提出了一種基于最大生成樹的層次聚類算法。該算法首先在最大生成樹上找到核節(jié)點，然后根據(jù)其他節(jié)點與核節(jié)點的相似度聚類成局部社團，最后逐步合并局部社團得到最優(yōu)劃分結(jié)果。算法在初次聚類時的相似度度量方法充分考慮了局部信息與全局信息，極大地提高了算法的準確度。實驗結(jié)果證明，基于最大生成樹的社團劃分算法在執(zhí)行效率和結(jié)果的可靠性方面優(yōu)于已有的社團劃分算法。在今后的工作中，通過對參數(shù)ε選取方式的改進，有可能進一步降低時間復(fù)雜度。

[1] 王天成, 劉真真, 李天明，等. 復(fù)雜網(wǎng)絡(luò)社團結(jié)構(gòu)劃分方法及其應(yīng)用[J]. 信息通信, 2015(8):43-45.

[2] 鄭浩原, 黃戰(zhàn). 復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘——改進的層次聚類算法[J]. 微型機與應(yīng)用, 2011, 30(16):85-88.

[3] 趙曉慧, 劉微, 謝鳳宏,等. 基于局部信息的復(fù)雜網(wǎng)絡(luò)社團結(jié)構(gòu)發(fā)現(xiàn)算法[J]. 微型機與應(yīng)用, 2011, 30(15):43-46.

[4] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks [J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12):7821-7826.

[5]李曉佳, 張鵬, 狄增如,等. 復(fù)雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2008, 5(3):19-42.

[6] NEWMAN M E. Fast algorithm for detecting community structure in networks [J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 69(6):066133.

[7] CLAUSET A, NEWMAN M E, MOORE C. Finding community structure in very large networks [J]. Physical Review E, 2005, 70(6 Pt 2):264-277.

[8] 吳蔚蔚, 劉功申, 黃晨. 基于相似度的社團劃分算法[J]. 計算機工程, 2015, 41(11):67-72.

[9] BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large networks [J]. Journal of Statistical Mechanics Theory & Experiment, 2008, 2008(10):155-168.

[10] EUSTACE J, WANG X, CUI Y. Community detection using local neighborhood in complex networks [J]. Physica A Statistical Mechanics & Its Applications, 2015, 436:665-677.

[11] 李爭光, 宋利. 基于結(jié)點相似性的層次化社團發(fā)現(xiàn)算法[J]. 信息技術(shù), 2012(5):82-87.

[12] BEHERA R K, RATH S K, JENA M. Spanning tree based community detection using min-max modularity [J]. Procedia Computer Science, 2016, 93:1070-1076.

[13] SAOUD B, MOUSSAOUI A. Community detection in networks based on minimum spanning tree and modularity [J]. Physica A Statistical Mechanics & Its Applications, 2016, 460:230-234.

[14] 梁宗文, 楊帆, 李建平. 基于節(jié)點相似性度量的社團結(jié)構(gòu)劃分方法[J]. 計算機應(yīng)用, 2015, 35(5):1213-1217.

[15] 王林, 高紅艷, 王佰超. 基于局部相似性的K—means譜聚類算法[J]. 西安理工大學(xué)學(xué)報, 2013, 35(4):455-459.

王海新(1989-)， 男，碩士研究生，主要研究方向:復(fù)雜網(wǎng)絡(luò)。

A community partitioning algorithm based on maximum spanning tree

Wang Lin，Wang Haixin

(School of Automation and Information Engineering, Xi’an University of Technology, Xi’an 710048, China)

Aiming at the issue of high complexity and low accuracy in the hierarchical clustering algorithm, a new algorithm based on maximal spanning tree is proposed. The similarity among nodes is redefined, and maximum spanning tree is used for initial clustering, and then the final classification results are obtained by merging local communities according to the similarity among communities. Not only time complexity is reduced, but the accuracy of the classification society is improved by this algorithm. On the basis of the algorithms,we used the method in real networks and artificial networks for verification and comparison, the experimental results indicate that the maximum spanning tree based community detection algorithm is capable of partitioning the community structure more quickly and accurately.

community division; hierarchical clustering; maximum spanning tree; node similarity

TN929.12

A

10.19358/j.issn.1674- 7720.2017.07.005

王林，王海新.基于最大生成樹的社團劃分算法[J].微型機與應(yīng)用，2017,36(7)：15-18.

2016-12-05)

王林(1963-)，男，博士，教授，主要研究方向:復(fù)雜網(wǎng)絡(luò)、大數(shù)據(jù)理論與應(yīng)用、無線傳感器及計算機應(yīng)用。