王林，王海新

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

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

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

　　中圖分類號：TN929.12文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.07.005

　　引用格式：王林，王海新.基于最大生成樹的社團劃分算法［J］.微型機與應用，2017,36（7）：15-18.

0引言

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

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

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

1最大生成樹

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

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

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

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

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

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

　　2.1節(jié)點聚類

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

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

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

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

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

　　2.2局部社團合并

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

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

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

　　2.3算法步驟及復雜度分析

　　本文算法步驟如下：

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

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

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

　　(2)確定核節(jié)點：對T(V,ET)上邊的權值進行排序并記錄到隊列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)重復步驟(4)直到網(wǎng)絡合并為一個社團，找到最大的Q值并記錄到隊列Qs中；

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

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

3實驗結果及分析

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

　　3.1真實網(wǎng)絡

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

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

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

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

　　3.2.1準確性驗證

　　社團劃分的準確度用歸一化互信息（Normalized mutual information）［15］來衡量，它的定義如下：

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

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

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

　　3.2.2復雜度驗證

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

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

4結論與展望

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

參考文獻

　?。?］ 王天成, 劉真真, 李天明，等. 復雜網(wǎng)絡社團結構劃分方法及其應用［J］. 信息通信, 2015(8):43-45.

　?。?］ 鄭浩原, 黃戰(zhàn). 復雜網(wǎng)絡社區(qū)挖掘——改進的層次聚類算法［J］. 微型機與應用, 2011, 30(16):85-88.

　?。?］ 趙曉慧, 劉微, 謝鳳宏,等. 基于局部信息的復雜網(wǎng)絡社團結構發(fā)現(xiàn)算法［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.

　?。?］李曉佳, 張鵬, 狄增如,等. 復雜網(wǎng)絡中的社團結構［J］. 復雜系統(tǒng)與復雜性科學, 2008, 5(3):19-42.

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

　?。?］ 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.

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

　?。?］ 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.

　?。?1］ 李爭光, 宋利. 基于結點相似性的層次化社團發(fā)現(xiàn)算法［J］. 信息技術, 2012(5):82-87.

　?。?2］ 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.

　?。?4］ 梁宗文, 楊帆, 李建平. 基于節(jié)點相似性度量的社團結構劃分方法［J］. 計算機應用, 2015, 35(5):1213-1217.

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