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

王 林，王海新

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

王 林，王海新

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

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

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

0 引言

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

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

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

1 最大生成樹

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

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

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

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

2 利用最大生成樹劃分社團結構

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

2.1 節點聚類

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

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

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

(1)

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

(2)

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

2.2 局部社團合并

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

(3)

其中，

(4)

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

每次合并社團后都要計算相應的網絡模塊度，最終選擇模塊度最大時對應的社團結構作為最優劃分。

2.3 算法步驟及復雜度分析

本文算法步驟如下：

輸入：一個無向無權網絡G(V,E)；

輸出：網絡的社團結構，Q值及參數ε的值；

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

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

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

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

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

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

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

3 實驗結果及分析

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

3.1 真實網絡

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

圖1 Zachary網絡的最大生成樹

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

圖2 Q=0.373 3時算法對Zachary網劃分的結果

3.2 計算機生成網

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

3.2.1 準確性驗證

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

(5)

NMI值表示Y劃分與X劃分的接近程度，其中X表示網絡的正確劃分，Y表示算法得出的社團劃分；它是一個介于0與1之間的數，NMI值越接近1表示算法劃分出的社團結構準確度越高。

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

圖3 算法在計算機生成網上的對比結果

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

3.2.2 復雜度驗證

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

圖4 算法運行時間對比

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

4 結論與展望

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

[1] 王天成, 劉真真, 李天明，等. 復雜網絡社團結構劃分方法及其應用[J]. 信息通信, 2015(8):43-45.

[2] 鄭浩原, 黃戰. 復雜網絡社區挖掘——改進的層次聚類算法[J]. 微型機與應用, 2011, 30(16):85-88.

[3] 趙曉慧, 劉微, 謝鳳宏,等. 基于局部信息的復雜網絡社團結構發現算法[J]. 微型機與應用, 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]李曉佳, 張鵬, 狄增如,等. 復雜網絡中的社團結構[J]. 復雜系統與復雜性科學, 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] 李爭光, 宋利. 基于結點相似性的層次化社團發現算法[J]. 信息技術, 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] 梁宗文, 楊帆, 李建平. 基于節點相似性度量的社團結構劃分方法[J]. 計算機應用, 2015, 35(5):1213-1217.

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

王海新(1989-)， 男，碩士研究生，主要研究方向:復雜網絡。

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].微型機與應用，2017,36(7)：15-18.

2016-12-05)

王林(1963-)，男，博士，教授，主要研究方向:復雜網絡、大數據理論與應用、無線傳感器及計算機應用。