王 林，王海新

基于最大生成樹的社團(tuán)劃分算法

王 林，王海新

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

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

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

0 引言

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

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

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

1 最大生成樹

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

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

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

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

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

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

2.1 節(jié)點(diǎn)聚類

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

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

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

(1)

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

(2)

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

2.2 局部社團(tuán)合并

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

(3)

其中，

(4)

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

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

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

本文算法步驟如下：

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

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

(1)生成最大生成樹：首先計(jì)算網(wǎng)絡(luò)中每條邊的權(quán)值，將無(wú)向無(wú)權(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é)點(diǎn)：對(duì)T(V,ET)上邊的權(quán)值進(jìn)行排序并記錄到隊(duì)列WT中，在候選隊(duì)列WT中選擇一個(gè)新值作為ε的值，然后在最大生成樹T(V,ET)上根據(jù)式(1)計(jì)算出所有的核節(jié)點(diǎn)；

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

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

3.2.1 準(zhǔn)確性驗(yàn)證

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

(5)

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

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

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

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

3.2.2 復(fù)雜度驗(yàn)證

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

圖4 算法運(yùn)行時(shí)間對(duì)比

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

4 結(jié)論與展望

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

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

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

[3] 趙曉慧, 劉微, 謝鳳宏,等. 基于局部信息的復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法[J]. 微型機(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ò)中的社團(tuán)結(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] 吳蔚蔚, 劉功申, 黃晨. 基于相似度的社團(tuán)劃分算法[J]. 計(jì)算機(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] 李爭(zhēng)光, 宋利. 基于結(jié)點(diǎn)相似性的層次化社團(tuán)發(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é)點(diǎn)相似性度量的社團(tuán)結(jié)構(gòu)劃分方法[J]. 計(jì)算機(jī)應(yīng)用, 2015, 35(5):1213-1217.

[15] 王林, 高紅艷, 王佰超. 基于局部相似性的K—means譜聚類算法[J]. 西安理工大學(xué)學(xué)報(bào), 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

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

2016-12-05)

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