白伊史,翟海霞,劉 園

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

1 引 言

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

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

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

2 相關工作

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

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

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

3 Louvain算法問題分析及改進

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

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

3.1 Louvain算法問題分析

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

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

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

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

3.2 改進的Louvain算法

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

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

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

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

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

標簽傳播策略3.從與當前節(jié)點擁有共同鄰居數(shù)最多的節(jié)點中隨機選擇一個節(jié)點對應的標簽更新當前節(jié)點.

算法1. Louvain-INA 算法

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

輸出：社區(qū)劃分

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

2.while(true)

3. for eachvcinVcdo

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

5. 將最大模塊度增量對應的社區(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é)點進行標簽傳播;

12. ifDec(vc)和Dec(C)中存在擁有相同標簽的節(jié)點

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←當前社區(qū)劃分的模塊度;

22.if new_mod-cur_mod<θ

23. break;

24.else

25. cur_mod=new_mod

26.end if

27.end while

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法2. Louvain-IMO算法

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

輸出：由超節(jié)點構(gòu)成的社交網(wǎng)絡圖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. 計算v加入各鄰居社區(qū)后的模塊度增量;

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

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

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

10. else

11. 將v從Ns中刪除;

12. end if

13. end for

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

15.end while

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

17.returnGc

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

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

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

輸出：CGt

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

2.ifβ(t)≤0

3.Gc←Louvain-MO(Gt);

4. Louvain-INA(Gc);

5.else

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

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

8. Louvain-INA(Gc);

5 實 驗

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

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

本次實驗選擇了來自不同場景的4個真實動態(tài)數(shù)據(jù)集和10個人工動態(tài)數(shù)據(jù)集.4個真實數(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基準模型[24]生成,生成的參數(shù)分別為：混合參數(shù)mu取0.1到0.6的6個小數(shù),節(jié)點數(shù)為1000,平均度為10,最大度為20,時間片網(wǎng)絡數(shù)為20.另外4個人工數(shù)據(jù)集則來自Greene數(shù)據(jù)集[25].4個數(shù)據(jù)集的時間片網(wǎng)絡數(shù)都為5,每個數(shù)據(jù)集的初始時間片網(wǎng)絡包含1000個節(jié)點,節(jié)點的最大度為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é)點創(chuàng)建,10%的社區(qū)被刪除;Greene-2只包含合并和分裂事件,在每個時間片有10%的社區(qū)被拆分,10%的社區(qū)被兩兩合并;Greene-3只包含擴張和收縮事件,在每個時間片隨機選擇10%的社區(qū)擴張或收縮成它大小的25%;Greene-4包含間歇社區(qū),在每個時間片有10%的社區(qū)消失,并在下一時間片重新出現(xiàn).

5.2 實驗環(huán)境及評價指標

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

(2)

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

為避免隨機性,所有的算法均在相應的數(shù)據(jù)集上獨立運行100次,然后計算平均結(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ù)據(jù)集上,本算法和Louvain-dyn算法的Qms值明顯高于其它3個對比算法.其中,本算法的Qms值要明顯高于Louvain-dyn算法的Qms值.

圖4展示了算法在不同數(shù)據(jù)集上的運行時間.由圖4(a)可知,在LFR數(shù)據(jù)集上在mu取0.1到0.5的5個不同值對應的子集上,本文算法的運行時間均少于Louvain-dyn算法.只有在mu=0.6時,本文算法的運行時間略長于Louvain-dyn算法.由圖4(b)可知,在Greene數(shù)據(jù)集上本算法的運行時間明顯少于其它算法.本文算法在數(shù)據(jù)集Greene-1、Greene-2、Greene-3和Greene-4的運行時間分別比Louvain-dyn算法和QCA算法降低了約76%和97%,比DCDID算法和DABP算法降低了約56%和98%.由圖4(c)可知,本算法和Louvain-dyn算法在所有真實數(shù)據(jù)集上的運行時間要比其它對比算法少.雖然在CW、Enron和Rm數(shù)據(jù)集上本算法的運行時間比Louvain-dyn算法稍長,但是本算法在所有真實數(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ù)集上的運行時間(秒)對比Fig.4 Comparison of the running time(s)of the algorithm on different datasets

6 結(jié)束語

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