一種混合的動態(tài)社區(qū)發(fā)現(xiàn)算法

白伊史,翟海霞,劉 園

(河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,河南 焦作 454003) E-mail：liuaspire@163.com

1 引 言

社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)具有的重要特征之一.根據(jù)社區(qū)結(jié)構(gòu)是否隨時間變化,可將社區(qū)發(fā)現(xiàn)算法分為動態(tài)社區(qū)發(fā)現(xiàn)算法和靜態(tài)社區(qū)發(fā)現(xiàn)算法.而在實(shí)際情況中,網(wǎng)絡(luò)用戶的注冊與注銷活動、社交用戶之間的關(guān)注與取關(guān)以及互動等等都與時間因素密切相關(guān)[1].因此研究復(fù)雜網(wǎng)絡(luò)中的動態(tài)社區(qū)發(fā)現(xiàn)算法更具現(xiàn)實(shí)意義.

增量式社區(qū)發(fā)現(xiàn)算法利用網(wǎng)絡(luò)的歷史快照具有的社區(qū)結(jié)構(gòu)針對網(wǎng)絡(luò)的增量變化局部調(diào)整社區(qū)結(jié)構(gòu),從而快速得到當(dāng)前時間片網(wǎng)絡(luò)的社區(qū)劃分結(jié)果.目前,增量式社區(qū)發(fā)現(xiàn)”算法已成為主流的動態(tài)社區(qū)發(fā)現(xiàn)算法[2-6].然而,該類算法存在兩個問題：一是含累積歷史快照社區(qū)劃分結(jié)果中存在的誤差;二是當(dāng)社區(qū)演變劇烈時,對增量的處理會增加計(jì)算成本,制約算法性能.盡管針對增量式動態(tài)社區(qū)發(fā)現(xiàn)算法開展了大量研究,但是該類算法中由累積誤差引起的社區(qū)劃分結(jié)果準(zhǔn)確率問題和增量處理引起的性能問題仍然是開放問題.

針對增量式動態(tài)社區(qū)發(fā)現(xiàn)算法存在的問題,本文提出了一種混合的增量式動態(tài)社區(qū)發(fā)現(xiàn)算法,利用模塊度增量算法和標(biāo)簽傳播算法進(jìn)行社區(qū)劃分.該算法將社區(qū)的動態(tài)變化分為劇烈演變和非劇烈演變兩種情況.為了減少增量處理,對于劇烈演變的情況,將對應(yīng)的網(wǎng)絡(luò)快照看作獨(dú)立的網(wǎng)絡(luò)劃分社區(qū).對于非劇烈演變的情況,則采用增量的方式劃分社區(qū).在社區(qū)劃分過程中同時采用了基于模塊度優(yōu)化的Louvain算法和標(biāo)簽傳播算法進(jìn)行社區(qū)結(jié)構(gòu)調(diào)整,在保留Louvain算法性能優(yōu)勢的同時,利用標(biāo)簽傳播算法提高社區(qū)的分辨率,即識別小社區(qū)的能力.

2 相關(guān)工作

在動態(tài)社區(qū)發(fā)現(xiàn)算法[7]中,主要包括基于聚類的算法和基于增量的算法.對于基于聚類的動態(tài)社區(qū)發(fā)現(xiàn)算法,Chen等人[8]提出了一種用于動態(tài)網(wǎng)絡(luò)聚類的多周期MK-均值算法,Liu等人[9]提出了一種基于譜聚類和度校正的全局社區(qū)檢測方法.基于聚類的算法時間復(fù)雜度較高,為了提升算法效率,研究人員提出了增量社區(qū)發(fā)現(xiàn)算法.郭等人[10]提出了一種基于密度聚類的增量動態(tài)社區(qū)檢測算法.Zhao等人[11]提出了一種通過處理子圖來檢測社區(qū)的增量方法.

基于模塊度優(yōu)化的算法也被應(yīng)用到增量式社區(qū)發(fā)現(xiàn)[12],Louvain算法便是其中之一.該算法具有檢測社區(qū)速度快、準(zhǔn)確性高等優(yōu)點(diǎn),但也存在不容易辨別出某些特殊小社區(qū)的缺點(diǎn),即存在分辨率局限性問題.Held等人[13]提出了Louvain-dyn算法,該算法僅對增量節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)進(jìn)行劃分,雖然提升了社區(qū)劃分的效率,但卻降低了社區(qū)劃分的準(zhǔn)確率.胡北辰[14]提出一種自適應(yīng)的動態(tài)社區(qū)發(fā)現(xiàn)算法,該算法重點(diǎn)關(guān)注相鄰社區(qū)的節(jié)點(diǎn)變化,針對不同的變化提出不同的增量處理策略對當(dāng)前時間片網(wǎng)絡(luò)進(jìn)行社區(qū)劃分.Meng等人[15]提出一種基于模塊度優(yōu)化的動態(tài)社區(qū)檢測算法,該算法對Louvain算法進(jìn)行改進(jìn)使其適應(yīng)動態(tài)網(wǎng)絡(luò),從動態(tài)網(wǎng)絡(luò)中獲取平滑演化的社區(qū)結(jié)構(gòu).

上述基于Louvain的動態(tài)社區(qū)發(fā)現(xiàn)算法仍然存在分辨率局限性問題,降低了每個時間片網(wǎng)絡(luò)社區(qū)劃分的準(zhǔn)確性,存在較大的累積誤差.該類算法在進(jìn)行動態(tài)社區(qū)發(fā)現(xiàn)時對網(wǎng)絡(luò)中的增量逐一進(jìn)行處理,忽略了增量之間的聯(lián)系,無法自適應(yīng)的檢測社區(qū).此外,當(dāng)網(wǎng)絡(luò)發(fā)生劇烈演變會產(chǎn)生較多增量,而單獨(dú)對每個增量進(jìn)行處理則會增加計(jì)算成本,制約算法的性能.

3 Louvain算法問題分析及改進(jìn)

本文用圖G=(V,E)表示復(fù)雜網(wǎng)絡(luò),其中V是節(jié)點(diǎn)集合,E是邊集合,v和e分別表示單個的節(jié)點(diǎn)和邊.t時刻的網(wǎng)絡(luò)快照用Gt表示,Gt的社區(qū)結(jié)構(gòu)用CGt表示.

本節(jié)在復(fù)雜網(wǎng)絡(luò)圖的基礎(chǔ)上分析Louvain算法存在的問題并給出解決方法.

3.1 Louvain算法問題分析

Louvain算法包括模塊度優(yōu)化和網(wǎng)絡(luò)聚合兩個階段[16].在模塊度優(yōu)化階段,首先將網(wǎng)絡(luò)中的每一個節(jié)點(diǎn)作為獨(dú)立的社區(qū)構(gòu)造初始網(wǎng)絡(luò),然后隨機(jī)選取網(wǎng)絡(luò)中的某一節(jié)點(diǎn),針對此節(jié)點(diǎn)計(jì)算將該節(jié)點(diǎn)加入某鄰居節(jié)點(diǎn)所在社區(qū)后的模塊度增量：若最大模塊度增量大于0,則將該節(jié)點(diǎn)加入最大模塊度增量對應(yīng)的社區(qū);反之,則該節(jié)點(diǎn)保持原社區(qū)不變.重復(fù)此過程,直到遍歷完網(wǎng)絡(luò)中的所有節(jié)點(diǎn),并且每個節(jié)點(diǎn)的社區(qū)歸屬不再改變?yōu)橹?在網(wǎng)絡(luò)聚合階段,首先根據(jù)模塊度優(yōu)化階段的社區(qū)劃分結(jié)果構(gòu)建壓縮圖：將每個社區(qū)分別壓縮成一個超節(jié)點(diǎn),社區(qū)內(nèi)部邊為超節(jié)點(diǎn)的自邊,社區(qū)間的邊為相應(yīng)超節(jié)點(diǎn)之間的連邊.將每個超節(jié)點(diǎn)看作一個獨(dú)立的社區(qū),按照模塊度優(yōu)化的方法進(jìn)行社區(qū)結(jié)構(gòu)調(diào)整,直至所有節(jié)點(diǎn)無法改變社區(qū)歸屬時停止.此時的社區(qū)劃分結(jié)果為Louvain算法最終的社區(qū)劃分結(jié)果.

Louvain算法在網(wǎng)絡(luò)聚合階段的社區(qū)劃分實(shí)質(zhì)是在進(jìn)行社區(qū)合并.每一個超節(jié)點(diǎn)其實(shí)是包含若干節(jié)點(diǎn)的一個子圖,Louvain算法僅僅依據(jù)模塊度增量合并社區(qū)的做法,沒有考慮到合并后社區(qū)內(nèi)部的緊密性,這可能會將本應(yīng)屬于不同社區(qū)的節(jié)點(diǎn)劃分到一個社區(qū)內(nèi).

此處,以派系網(wǎng)絡(luò)為例說明這一問題.派系是由若干節(jié)點(diǎn)構(gòu)成的完全圖.圖1(a)中的網(wǎng)絡(luò)就由16個派系構(gòu)成.按照Louvain算法思想,在模塊度優(yōu)化階段,16個派系劃分為16個社區(qū)得到的模塊度最大,所以將每個派系劃分為一個社區(qū),得到圖1(b)所示的包含16個社區(qū)的網(wǎng)絡(luò)圖;然后將16個社區(qū)分別壓縮成超節(jié)點(diǎn),構(gòu)造新網(wǎng)絡(luò),得到圖1(c)所示的壓縮圖;在網(wǎng)絡(luò)聚合階段,每兩個相鄰的派系被劃分到一個社區(qū),最終得到圖1(d)所示的包含8個社區(qū)的社區(qū)結(jié)構(gòu),兩個派系之間僅有一條邊相連,故而社區(qū)內(nèi)部緊密性不強(qiáng).若把每個派系作為一個社區(qū),則每個社區(qū)內(nèi)部緊密性都很強(qiáng).因此,Louvain算法在網(wǎng)絡(luò)聚合階段僅根據(jù)模塊度增量進(jìn)行社區(qū)合并的做法并不合理.

圖1 派系網(wǎng)絡(luò)社區(qū)劃分結(jié)果Fig.1 Results of the division of the faction network community

3.2 改進(jìn)的Louvain算法

針對Louvain算法在網(wǎng)絡(luò)聚合階段存在社區(qū)劃分不合理的問題,本文結(jié)合標(biāo)簽傳播算法對Louvain算法的網(wǎng)絡(luò)聚合階段進(jìn)行了改進(jìn).在網(wǎng)絡(luò)聚合階段的社區(qū)合并過程中,除了考慮模塊度增量因素,還要衡量社區(qū)合并后新社區(qū)內(nèi)部的緊密性.只有在模塊度和緊密性兩項(xiàng)因素同時滿足要求時,才進(jìn)行社區(qū)合并.

本文利用標(biāo)簽傳播算法對2個社區(qū)進(jìn)行緊密性檢查.首先對超節(jié)點(diǎn)解壓縮,將其恢復(fù)為節(jié)點(diǎn)和邊.然后將涉及緊密性檢查的所有節(jié)點(diǎn)和相關(guān)聯(lián)的邊看作獨(dú)立的網(wǎng)絡(luò),給每個節(jié)點(diǎn)初始化唯一的標(biāo)簽并進(jìn)行標(biāo)簽傳播.最后,根據(jù)標(biāo)簽傳播結(jié)果進(jìn)行緊密性檢查.在傳播結(jié)束后,若兩個社區(qū)中有標(biāo)簽相同的節(jié)點(diǎn),則認(rèn)為兩個社區(qū)連接緊密,適合合并;反之,則認(rèn)為兩個社區(qū)連接不緊密,不能合并.

為了避免標(biāo)簽傳播中的隨機(jī)性影響社區(qū)劃分結(jié)果的穩(wěn)定性,本文在文獻(xiàn)[17]原有標(biāo)簽傳播策略的基礎(chǔ)上引入了新的傳播策略,描述如下：

標(biāo)簽傳播策略1.若在鄰居節(jié)點(diǎn)中出現(xiàn)最多的標(biāo)簽同時有多個,則計(jì)算這些標(biāo)簽所屬節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的共同鄰居,根據(jù)策略2進(jìn)行標(biāo)簽更新.

標(biāo)簽傳播策略2.若與當(dāng)前節(jié)點(diǎn)擁有共同鄰居數(shù)最多的節(jié)點(diǎn)只有一個,則選擇此節(jié)點(diǎn)的標(biāo)簽更新當(dāng)前節(jié)點(diǎn);否則,按策略3更新當(dāng)前節(jié)點(diǎn)的標(biāo)簽.

標(biāo)簽傳播策略3.從與當(dāng)前節(jié)點(diǎn)擁有共同鄰居數(shù)最多的節(jié)點(diǎn)中隨機(jī)選擇一個節(jié)點(diǎn)對應(yīng)的標(biāo)簽更新當(dāng)前節(jié)點(diǎn).

算法1. Louvain-INA 算法

輸入：由超節(jié)點(diǎn)構(gòu)成的社交網(wǎng)絡(luò)圖Gc=(Vc,Ec)

輸出：社區(qū)劃分

1.將Gc中的每個超節(jié)點(diǎn)vc作為一個獨(dú)立的社區(qū),并計(jì)算此時社區(qū)劃分的模塊度←cur_mod;

2.while(true)

3. for eachvcinVcdo

4. 計(jì)算vc加入各個鄰居社區(qū)后的模塊度增量;

5. 將最大模塊度增量對應(yīng)的社區(qū)加入Clist;

6. matched=false;

7. while(Clist!matched andClist!null)

8. if最大的模塊度增量>0

9.C←Clist.get(i)

10.V′←Dec(vc)∪Dec(C);

11. 對V′中的節(jié)點(diǎn)進(jìn)行標(biāo)簽傳播;

12. ifDec(vc)和Dec(C)中存在擁有相同標(biāo)簽的節(jié)點(diǎn)

13.vc加入社區(qū)C;

14. matched=true;

15. else

16. 將C從Clist中刪除;

17. end if

18. end if

19. end while

20.end for

21.new_mod←當(dāng)前社區(qū)劃分的模塊度;

22.if new_mod-cur_mod<θ

23. break;

24.else

25. cur_mod=new_mod

26.end if

27.end while

算法1展示了改進(jìn)后的網(wǎng)絡(luò)聚合階段的算法,記為Louvain-INA算法.以圖2虛線框內(nèi)的超節(jié)點(diǎn)為例說明根據(jù)Louvain-INA算法融合社區(qū)的過程.首先超節(jié)點(diǎn)進(jìn)行解壓縮,得到局部網(wǎng)絡(luò)圖;然后對該局部網(wǎng)絡(luò)進(jìn)行標(biāo)簽傳播,標(biāo)簽傳播完成后進(jìn)行緊密性檢查.由于兩個超節(jié)點(diǎn)分別解壓縮并進(jìn)行標(biāo)簽傳播后得到的節(jié)點(diǎn)中沒有標(biāo)簽相同的節(jié)點(diǎn),所以兩個超節(jié)點(diǎn)連接不緊密,不能合并為一個社區(qū).由上述過程易知,每個超節(jié)點(diǎn)都不加入鄰居社區(qū),而做為獨(dú)立社區(qū)存在,最終得到正確的社區(qū)劃分結(jié)果.

圖2 劃分超節(jié)點(diǎn)Fig.2 Partitioning super nodes

4 混合的動態(tài)社區(qū)發(fā)現(xiàn)算法

本文根據(jù)網(wǎng)絡(luò)的演變程度采用不同的方式劃分社區(qū).對于網(wǎng)絡(luò)劇烈演變的情況,將當(dāng)前時間快照看作靜態(tài)網(wǎng)絡(luò),采用改進(jìn)的Louvain算法劃分社區(qū);對于網(wǎng)絡(luò)的非劇烈演變,則在改進(jìn)的Louvain算法基礎(chǔ)上設(shè)計(jì)增量社區(qū)發(fā)現(xiàn)算法,以增量的方式劃分社區(qū).

4.1 社區(qū)演變程度分析

社交網(wǎng)絡(luò)在不同時間的演化程度是不同的.當(dāng)網(wǎng)絡(luò)演化程度較小時對應(yīng)的網(wǎng)絡(luò)增量較少,在歷史社區(qū)劃分結(jié)果的基礎(chǔ)上根據(jù)網(wǎng)絡(luò)增量調(diào)整社區(qū)結(jié)構(gòu),可以節(jié)省社區(qū)劃分的時間,提升社區(qū)劃分性能.當(dāng)網(wǎng)絡(luò)演變程度較劇烈時會產(chǎn)生過多的網(wǎng)絡(luò)增量,若此時仍在歷史劃分結(jié)果的基礎(chǔ)上進(jìn)行增量式社區(qū)劃分,不僅會因?yàn)檎{(diào)整過多的增量而導(dǎo)致時間復(fù)雜度增加,而且還會在歷史劃分結(jié)果的基礎(chǔ)上累積誤差.

要解決由于網(wǎng)絡(luò)劇烈演變而導(dǎo)致的社區(qū)劃分過程中計(jì)算復(fù)雜度和累積誤差增加的問題,必須對社區(qū)網(wǎng)絡(luò)的演變程度加以區(qū)分,針對不同的演化程度采取不同的社區(qū)劃分方法.為此,本文定義了網(wǎng)絡(luò)演變度.

定義1.網(wǎng)絡(luò)演變度.描述相對于t-1時刻,t時刻網(wǎng)絡(luò)的演變程度,記β(t).

β(t)=1-|St|/|Vt-1|

(1)

β(t)根據(jù)式(1)計(jì)算.在該式中,St表示t時刻變化的節(jié)點(diǎn)集合.本文認(rèn)為,如果β(t)≤0,則表示Gt相對于Gt-1發(fā)生了劇烈演變,此時的節(jié)點(diǎn)增量和邊增量較多.為減少這些增量對社區(qū)劃分的計(jì)算復(fù)雜度和累積誤差的影響,將當(dāng)前時間片網(wǎng)絡(luò)看作靜態(tài)網(wǎng)絡(luò),采用改進(jìn)后的Louvain算法劃分社區(qū).在β(t)>0的情況下才采用增量的方式劃分社區(qū).

4.2 增量式社區(qū)發(fā)現(xiàn)

當(dāng)β(t)>0時,本文認(rèn)為從t-1到t時刻網(wǎng)絡(luò)經(jīng)歷了非劇烈演變,此時應(yīng)采用增量式的社區(qū)劃分方法.網(wǎng)絡(luò)演變表現(xiàn)為節(jié)點(diǎn)的變化和邊的變化.節(jié)點(diǎn)和邊的變化分為兩種情況,一是新節(jié)點(diǎn)或邊的出現(xiàn),二是已有節(jié)點(diǎn)或邊的消失.社區(qū)內(nèi)增加邊或社區(qū)間減少邊不會導(dǎo)致社區(qū)結(jié)構(gòu)發(fā)生改變[18],因此本文只考慮可能會對社區(qū)結(jié)構(gòu)造成影響的增量,并將其分為4種類型：1)新節(jié)點(diǎn)出現(xiàn);2)已有節(jié)點(diǎn)消失;3)與已有節(jié)點(diǎn)關(guān)聯(lián)的新邊出現(xiàn);4)非消失節(jié)點(diǎn)關(guān)聯(lián)的邊消失.

為便于處理這4種增量,本文引入了搖擺節(jié)點(diǎn)的概念統(tǒng)一從節(jié)點(diǎn)的角度入手處理這4種變化.引入搖擺節(jié)點(diǎn)之后,對4種增量引起的社區(qū)結(jié)構(gòu)的調(diào)整就轉(zhuǎn)變?yōu)閾u擺節(jié)點(diǎn)所屬社區(qū)結(jié)構(gòu)的調(diào)整.

定義2.搖擺節(jié)點(diǎn).社區(qū)歸屬可能發(fā)生改變的節(jié)點(diǎn)稱為搖擺節(jié)點(diǎn).

在進(jìn)行增量社區(qū)劃分時,必須先篩選搖擺節(jié)點(diǎn).為此,引入了引力節(jié)點(diǎn)和動搖社區(qū)的概念.引力節(jié)點(diǎn)成對出現(xiàn),試圖將對方吸引到自己所在的社區(qū).動搖社區(qū)結(jié)構(gòu)可能保持不變,也可能發(fā)生變化.動搖社區(qū)可能發(fā)生分裂,由一個社區(qū)演變?yōu)槎鄠€社區(qū);也可能發(fā)生社區(qū)融合,與其它社區(qū)部分或者全部融合.

定義3.引力節(jié)點(diǎn).社區(qū)之間新增加的邊所關(guān)聯(lián)的已有節(jié)點(diǎn)即為引力節(jié)點(diǎn).

1http：//www.sociopatterns.org/datasets/

定義4.動搖社區(qū).文獻(xiàn)[19]提出,如果一個度為1的節(jié)點(diǎn)在社區(qū)中消失,則該社區(qū)結(jié)構(gòu)不變.除此之外,將存在消失邊的社區(qū)稱為動搖社區(qū).

搖擺節(jié)點(diǎn)收集策略描述如下：

收集策略1.所有新出現(xiàn)的節(jié)點(diǎn)全部視為搖擺節(jié)點(diǎn),加入搖擺節(jié)點(diǎn)列表.

收集策略2.將動搖社區(qū)中的全部節(jié)點(diǎn)視作搖擺節(jié)點(diǎn),全部加入搖擺節(jié)點(diǎn)列表.

收集策略3.將引力節(jié)點(diǎn)視作搖擺節(jié)點(diǎn),加入搖擺節(jié)點(diǎn)列表.

增量社區(qū)動態(tài)劃分方法首先初始化社區(qū)結(jié)構(gòu),將每個搖擺節(jié)點(diǎn)視作獨(dú)立社區(qū),非搖擺節(jié)點(diǎn)則保持原社區(qū);然后根據(jù)模塊度優(yōu)化算法對搖擺節(jié)點(diǎn)進(jìn)行社區(qū)劃分,具體過程如算法2所示.將上一步劃分出的社區(qū)壓縮成超節(jié)點(diǎn),生成由超節(jié)點(diǎn)構(gòu)成的社交網(wǎng)絡(luò)圖;最后,利用Louvain-INA算法對包含超節(jié)點(diǎn)的社交網(wǎng)絡(luò)圖進(jìn)行社區(qū)結(jié)構(gòu)調(diào)整,形成最終的社區(qū)劃分結(jié)果.

算法2. Louvain-IMO算法

輸入：Gt,Ns//根據(jù)CGt-1及Gt收集的搖擺節(jié)點(diǎn)列表Ns

輸出：由超節(jié)點(diǎn)構(gòu)成的社交網(wǎng)絡(luò)圖Gc

1.θ=0.001;

2.new_mod←Gt-1時刻的社區(qū)劃分模塊度,cur_mod←0

3.while(Ns!null and(new_mod-cur_mod≥θ))

4. cur_mod=new_mod;

5. for eachvinNs

6. 計(jì)算v加入各鄰居社區(qū)后的模塊度增量;

7. if 最大的模塊度增量>0

8. 將v加入最大模塊度增量對應(yīng)的社區(qū);

9. 將v不在Ns的鄰居節(jié)點(diǎn)加入Ns;

10. else

11. 將v從Ns中刪除;

12. end if

13. end for

14. new_mod←當(dāng)前社區(qū)劃分的模塊度;

15.end while

16.將每個社區(qū)壓縮為一個超節(jié)點(diǎn),構(gòu)建壓縮圖Gc;

17.returnGc

算法2展示了引入搖擺節(jié)點(diǎn)后利用模塊度優(yōu)化進(jìn)行社區(qū)結(jié)構(gòu)調(diào)整并生成由超節(jié)點(diǎn)構(gòu)成的社交網(wǎng)絡(luò)圖的過程.在第8行中,當(dāng)模塊度增量最大的社區(qū)不止一個時,節(jié)點(diǎn)將隨機(jī)選擇一個社區(qū)加入.算法3展示了基于Louvain算法和標(biāo)簽傳播算法構(gòu)造的混合式動態(tài)社區(qū)發(fā)現(xiàn)算法.

算法3.基于Louvain的改進(jìn)動態(tài)社區(qū)發(fā)現(xiàn)算法

輸入：Gt-1,Gt,CGt-1

輸出：CGt

1.計(jì)算演化程度β(t);

2.ifβ(t)≤0

3.Gc←Louvain-MO(Gt);

4. Louvain-INA(Gc);

5.else

6.Ns←根據(jù)CGt-1及Gt收集的搖擺節(jié)點(diǎn)列表Ns;

7.Gc←Louvain-IMO(Gt,Ns);

8. Louvain-INA(Gc);

5 實(shí) 驗(yàn)

本文采用實(shí)驗(yàn)的方法來評價本文方法.通過和Louvain-dyn算法、基于模塊度的QCA算法[19]、DABP[20]及DCDID算法[21]比較在真實(shí)數(shù)據(jù)集和人工數(shù)據(jù)集上的執(zhí)行結(jié)果來驗(yàn)證本文方法的正確性和有效性.

5.1 數(shù)據(jù)集

本次實(shí)驗(yàn)選擇了來自不同場景的4個真實(shí)動態(tài)數(shù)據(jù)集和10個人工動態(tài)數(shù)據(jù)集.4個真實(shí)數(shù)據(jù)集分別是RM數(shù)據(jù)集[22]、安然郵件數(shù)據(jù)集Enron[23]、來自SocioPatterns1的CW數(shù)據(jù)集和PS數(shù)據(jù)集.10個人工數(shù)據(jù)集中有6個是根據(jù)動態(tài)LFR基準(zhǔn)模型[24]生成,生成的參數(shù)分別為：混合參數(shù)mu取0.1到0.6的6個小數(shù),節(jié)點(diǎn)數(shù)為1000,平均度為10,最大度為20,時間片網(wǎng)絡(luò)數(shù)為20.另外4個人工數(shù)據(jù)集則來自Greene數(shù)據(jù)集[25].4個數(shù)據(jù)集的時間片網(wǎng)絡(luò)數(shù)都為5,每個數(shù)據(jù)集的初始時間片網(wǎng)絡(luò)包含1000個節(jié)點(diǎn),節(jié)點(diǎn)的最大度為50,平均度為15;包含33個社區(qū),社區(qū)內(nèi)部的邊數(shù)和總邊數(shù)的比為10%.

記來自Greene數(shù)據(jù)集的4個數(shù)據(jù)集分別為Greene-1、Greene-2、Greene-3和Greene-4.Greene-1只包含出生和死亡事件,在每個時間片有10%的社區(qū)通過現(xiàn)存社區(qū)移除的節(jié)點(diǎn)創(chuàng)建,10%的社區(qū)被刪除;Greene-2只包含合并和分裂事件,在每個時間片有10%的社區(qū)被拆分,10%的社區(qū)被兩兩合并;Greene-3只包含擴(kuò)張和收縮事件,在每個時間片隨機(jī)選擇10%的社區(qū)擴(kuò)張或收縮成它大小的25%;Greene-4包含間歇社區(qū),在每個時間片有10%的社區(qū)消失,并在下一時間片重新出現(xiàn).

5.2 實(shí)驗(yàn)環(huán)境及評價指標(biāo)

實(shí)驗(yàn)中采用Qms值以及運(yùn)行時間來評估算法的性能.Qms根據(jù)式(2)計(jì)算.在該式中,|s|表示時間片網(wǎng)絡(luò)總數(shù),Qi表示時間片網(wǎng)絡(luò)i對應(yīng)的社區(qū)劃分的模塊度Q值[26].Qms越高表示算法的效果越好.

(2)

實(shí)驗(yàn)中涉及的所有算法均用python語言實(shí)現(xiàn),且在相同的windows10系統(tǒng)下執(zhí)行.該系統(tǒng)采用Intel Core i5-7300 CPU,配置8GB的內(nèi)存空間.

為避免隨機(jī)性,所有的算法均在相應(yīng)的數(shù)據(jù)集上獨(dú)立運(yùn)行100次,然后計(jì)算平均結(jié)果.

圖3展示了算法在不同數(shù)據(jù)集上的Qms值對比.由圖可知,在基于LFR生成的人工數(shù)據(jù)集上,本文算法在mu取不同值時所產(chǎn)生的每個數(shù)據(jù)集上得到的Qms值都是最高的,其次是Louvain-dyn算法和DABP算法.在Greene數(shù)據(jù)集上本文算法得到Qms值也明顯高于其他對比算法,其次是QCA算法.Louvain-dyn算法和DCDIID算法則不相上下.在4個真實(shí)數(shù)據(jù)集上,本算法和Louvain-dyn算法的Qms值明顯高于其它3個對比算法.其中,本算法的Qms值要明顯高于Louvain-dyn算法的Qms值.

圖4展示了算法在不同數(shù)據(jù)集上的運(yùn)行時間.由圖4(a)可知,在LFR數(shù)據(jù)集上在mu取0.1到0.5的5個不同值對應(yīng)的子集上,本文算法的運(yùn)行時間均少于Louvain-dyn算法.只有在mu=0.6時,本文算法的運(yùn)行時間略長于Louvain-dyn算法.由圖4(b)可知,在Greene數(shù)據(jù)集上本算法的運(yùn)行時間明顯少于其它算法.本文算法在數(shù)據(jù)集Greene-1、Greene-2、Greene-3和Greene-4的運(yùn)行時間分別比Louvain-dyn算法和QCA算法降低了約76%和97%,比DCDID算法和DABP算法降低了約56%和98%.由圖4(c)可知,本算法和Louvain-dyn算法在所有真實(shí)數(shù)據(jù)集上的運(yùn)行時間要比其它對比算法少.雖然在CW、Enron和Rm數(shù)據(jù)集上本算法的運(yùn)行時間比Louvain-dyn算法稍長,但是本算法在所有真實(shí)數(shù)據(jù)集上的Qms值卻優(yōu)于Louvain-dyn算法.

圖3 算法在不同數(shù)據(jù)集上的Qms值對比Fig.3 Comparison of the Qmsvalue of the algorithm on different datasets

圖4 算法在不同數(shù)據(jù)集上的運(yùn)行時間(秒)對比Fig.4 Comparison of the running time(s)of the algorithm on different datasets

6 結(jié)束語

本文提出了一種混合的動態(tài)社區(qū)發(fā)現(xiàn)算法來應(yīng)對增量式動態(tài)社區(qū)發(fā)現(xiàn)算法存在的誤差累積和算法復(fù)雜度受網(wǎng)絡(luò)增量影響的問題.對于產(chǎn)生增量較多的網(wǎng)絡(luò)劇烈演化,該方法直接將對應(yīng)的網(wǎng)絡(luò)快照看做完整網(wǎng)絡(luò),采用靜態(tài)方法劃分社區(qū).而對于產(chǎn)生增量較少的非劇烈演變,則采用增量式方法發(fā)現(xiàn)社區(qū).在社區(qū)發(fā)現(xiàn)過程中,同時采用標(biāo)簽傳播算法和基于模塊度優(yōu)化的Louvain算法,在利用Louvain算法性能優(yōu)勢的同時,利用標(biāo)簽傳播算法彌補(bǔ)其在社區(qū)分辨率方面的不足.在未來工作中,將研究跨網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn).