郭 昆,彭勝波,張瑛瑛,陳羽中

1(福州大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院,福州 350116)2(福建省網(wǎng)絡(luò)計算與智能信息處理重點實驗室,福州 350116)3(空間數(shù)據(jù)挖掘與信息共享教育部重點實驗室,福州 350116)4(國網(wǎng)信通億力科技有限責(zé)任公司,福州 350003)

1 引 言

在現(xiàn)實世界中存在大量復(fù)雜網(wǎng)絡(luò),如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、文獻(xiàn)引用網(wǎng)絡(luò).研究表明,這些復(fù)雜網(wǎng)絡(luò)普遍存在著一定的社區(qū)結(jié)構(gòu),各社區(qū)內(nèi)部節(jié)點連接較為緊密,社區(qū)間連接較為稀疏[1].社區(qū)發(fā)現(xiàn)研究的就是如何準(zhǔn)確的識別出復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu).

傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法是將網(wǎng)絡(luò)劃分成若干個互不相連的社區(qū),網(wǎng)絡(luò)中每個節(jié)點和邊只能隸屬一個固定社區(qū).包括模塊度優(yōu)化方法[2-4],層次聚類算法[1,5],標(biāo)簽傳播算法[6,7]和信息論算法[8-10].然而,真實網(wǎng)絡(luò)中,社區(qū)之間通常是互相交叉,彼此聯(lián)系的,這種情形下,網(wǎng)絡(luò)中的節(jié)點不再僅隸屬于單個社區(qū),而是同時被包含到多個相關(guān)聯(lián)的社區(qū)中.因而,研究重疊社區(qū)結(jié)構(gòu)具有更重要意義.

目前,重疊社區(qū)發(fā)現(xiàn)算法主要包括基于派系過濾的算法、基于局部社區(qū)的算法、基于多標(biāo)簽傳播的算法和基于鏈接聚類的算法等.最近,Wang等人[11]提出了一種基于密度峰值聚類的社區(qū)發(fā)現(xiàn)算法LCCD,該算法利用密度峰值選取網(wǎng)絡(luò)的局部結(jié)構(gòu)中心,然后擴(kuò)展局部結(jié)構(gòu)中心來發(fā)現(xiàn)社區(qū),具有較高的社區(qū)精度,且能識別網(wǎng)絡(luò)的核心點和孤立點.但是,LCCD算法還存在時間復(fù)雜度較高和不能較好的應(yīng)用于重疊社區(qū)發(fā)現(xiàn)等不足.針對這些問題,提出一種基于密度峰值和社區(qū)歸屬度的重疊社區(qū)發(fā)現(xiàn)算法OCDPCB(Overlapping Community Detection based on Density Peaks and Community Belongingness),利用密度峰值聚類來生成非重疊社區(qū),基于社區(qū)歸屬度生成重疊社區(qū).主要貢獻(xiàn)如下:

1)提出一種基于節(jié)點直接鄰居和間接鄰居的距離度量方法,具有近似線性的時間復(fù)雜度;

2)設(shè)計一種聚類中心點的局部密度閾值和跟隨距離閾值計算方法,根據(jù)這兩個閾值自動選取聚類中心點,可以解決密度峰值聚類算法中聚類中心需要人為選定問題;

3)提出社區(qū)歸屬度計算方法,并對采用密度峰值聚類算法生成的社區(qū)邊界節(jié)點進(jìn)行社區(qū)歸屬計算,根據(jù)社區(qū)歸屬度把社區(qū)邊界點劃分到對應(yīng)社區(qū)中,可以較好的識別出網(wǎng)絡(luò)的重疊社區(qū).

2 相關(guān)工作

目前,重疊社區(qū)發(fā)現(xiàn)可以分為基于派系過濾的算法、基于局部社區(qū)的算法、基于標(biāo)簽傳播的算法和基于鏈接聚類的算法等.Palla等人[12]提出的基于派系過濾的CPM算法,其核心思想是基k極大團(tuán)發(fā)現(xiàn)重疊社區(qū).類似的算法還包括文獻(xiàn)[13,14],該類算法能較準(zhǔn)確的識別出網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu),但是具有較高的時間開銷,且不適用于稀疏網(wǎng)絡(luò).基于局部種子社區(qū)優(yōu)化和擴(kuò)展的重疊社區(qū)發(fā)現(xiàn)算法首先尋找網(wǎng)絡(luò)的初始種子社區(qū),之后通過貪心策略并結(jié)合局部適應(yīng)度函數(shù)對已有種子社區(qū)進(jìn)行擴(kuò)展發(fā)現(xiàn)重疊社區(qū),節(jié)點加入順序會對社區(qū)發(fā)現(xiàn)結(jié)果穩(wěn)定性造成影響.代表算法有LFM[15]算法、DEMON[16]算法、OCDW[17]算法、i-SEOCD[18]算法.基于標(biāo)簽傳播的重疊社區(qū)發(fā)現(xiàn)算法[19-21],該類算法為每個節(jié)點保留多個標(biāo)簽,每個標(biāo)簽對應(yīng)一個社區(qū).Evans等人[22]提出了一種基于線圖和鏈接切分的算法LGLPOC,該算法對網(wǎng)絡(luò)的邊進(jìn)行劃分,將邊集映射成節(jié)點集,能夠自然地識別出重疊社區(qū).Ahn等人[23]提出邊社區(qū)發(fā)現(xiàn)算法LC,采用Jaccard相似度衡量邊相似度,以自底向上的方式對邊進(jìn)行合并,直到目標(biāo)函數(shù)達(dá)到最大值,最后將邊社區(qū)轉(zhuǎn)化節(jié)點社區(qū).朱牧等人[24]提出了一種基于鏈接密度的社區(qū)發(fā)現(xiàn)算法DBLINK,通過密度聚類的方式檢測出噪聲邊,在聚類的過程中忽略噪聲邊,避免社區(qū)結(jié)構(gòu)的過度重疊.然而,該算法未對社區(qū)邊界邊和噪聲邊進(jìn)行合理處理,會造成社區(qū)邊界模糊和出現(xiàn)丟失部分節(jié)點和邊的情況.Zhou等人[25]提出了一種基于密度的鏈接聚類的算法DBLC,該方提出了一種相似度策略來處理邊界邊和噪聲邊,解決了社區(qū)邊界模糊問題,但未考慮噪聲邊可能形成獨立的小社區(qū),降低了社區(qū)發(fā)現(xiàn)精度.另外,該算法的時空復(fù)雜度較高.

Rodriguez等人[26]于2014年提出了密度峰值聚類方(Density Peaks Clustering,簡稱為DPC),該方法只依賴于節(jié)點之間的距離,根據(jù)節(jié)點分布的局部密度選擇聚類中心,能夠獲得穩(wěn)定的聚類結(jié)果.近年來,密度峰值聚類被很好的應(yīng)用到社區(qū)發(fā)現(xiàn)中.李玉[27]提出了CSDPC算法,該算法首先結(jié)合余弦相似度和節(jié)點間的最短路徑,把網(wǎng)絡(luò)的連邊關(guān)系映射成節(jié)點間的距離,之后再通過密度峰值聚類算法進(jìn)行社區(qū)發(fā)現(xiàn),能夠發(fā)現(xiàn)有效的社區(qū)結(jié)構(gòu).隋鵬[28]提出了IA-UDR算法,該算法通過模擬真實網(wǎng)絡(luò)中用戶的多種親密關(guān)系來表示節(jié)點之間的距離,并改進(jìn)了密度峰值聚類算法的中心選取策略,IA-UDR算法可以得到較好的社區(qū)劃分,且具有較好的泛化性.上述基于密度峰值聚類的社區(qū)發(fā)現(xiàn)算法雖然具有良好的穩(wěn)定性,且具有較高社區(qū)發(fā)現(xiàn)精度,但是沒有解決密度峰值算法存在的時間復(fù)雜度較高、聚類中心需要人為選定以及不能很好的應(yīng)用到重疊社區(qū)發(fā)現(xiàn)的問題.

3 OCDPCB算法

3.1 基本概念

設(shè)G=(V,E),其中V={Σvi|i=1,2,…,n}表示網(wǎng)絡(luò)中的節(jié)點集合,E={Σei|i=1,2,…,n}表示網(wǎng)絡(luò)中的邊集.下面主要介紹社區(qū)發(fā)現(xiàn)的基本概念和定義.

定義1.社區(qū)集合.設(shè)C={Ci},其中Ci表示在網(wǎng)絡(luò)G上生成的第i個社區(qū),C表示生成的所有社區(qū)集合.

定義2.節(jié)點直接鄰居.?v∈V,DNB+(v)表示包括節(jié)點自身的鄰居節(jié)點集合,DNB(v)表示不包括節(jié)點自身的鄰居節(jié)點集合.

定義3.節(jié)點間接鄰居.節(jié)點的間接鄰居是指節(jié)點鄰居的鄰居,節(jié)點v的間接鄰居INB(v)定義為:

INB(v)=t|t∈DNB(u)∧u∈DNB(v)

(1)

定義4.余弦相似度.兩節(jié)點u,v的余弦相似度σ(u,v)定義為:

(2)

其中,|DNB(u+)|表示節(jié)點u的直接鄰居節(jié)點個數(shù).

定義5.社區(qū)邊界點[11].社區(qū)Ci的邊界點BCi定義為:

BCi={v|d(v,w)≤dc∧v∈Ci∧w?Ci}

(3)

3.2 密度峰值聚類

DPC算法可以較好的用于網(wǎng)絡(luò)聚類.該算法基于以下兩個假設(shè):1)簇中心的局部密度相對較大;2)簇中心與更高局部密度的節(jié)點的距離相對較遠(yuǎn).下面對DPC算法聚類過程做個簡單介紹.

1)局部密度計算,節(jié)點的局部密度定義如下:

(4)

(5)

其中ρi是節(jié)點i的局部密度,dij是節(jié)點i和節(jié)點j間的距離,dc是距離閾值,可以選擇dc使得節(jié)點的平均鄰居數(shù)大約是數(shù)據(jù)集中節(jié)點總數(shù)的1%～2%.

2)跟隨距離計算,節(jié)點的跟隨距離定義如下:

(6)

其中,δi是節(jié)點i到其他具有更高局部密度節(jié)點的最小距離,也即節(jié)點i的跟隨距離.

3)節(jié)點分派到簇,在得到節(jié)點的ρi和δi后,可根據(jù)ρi和δi畫出一個決策圖,圖中具有高δ值和相對較高ρ值的節(jié)點會被選為簇中心.在簇中心確定之后,余下的非簇中心節(jié)點將會按照局部密度從高至低分派到密度比當(dāng)前節(jié)點大且距離當(dāng)前節(jié)點最近的節(jié)點所在的簇中.

DPC算法能夠保證節(jié)點分配過程的可靠性,且算法對距離閾值dc和對大數(shù)據(jù)集具有較好的魯棒性.但由于DPC算法在計算節(jié)點間距離時需要計算任意兩點間的距離,所以改算法的時空復(fù)雜度較高;另外,簇中心的選取需要根據(jù)決策圖人為指定,在結(jié)構(gòu)復(fù)雜的網(wǎng)絡(luò)中,這種方式無法較為準(zhǔn)確的選取簇中心.最后,節(jié)點的跟隨策略決定了DPC算法不能進(jìn)行模糊聚類.

3.3 算法設(shè)計思想

OCDPCB算法由以下幾個步驟組成:

1)節(jié)點間距離計算:由于復(fù)雜網(wǎng)絡(luò)的拓?fù)渲兄话?jié)點及其連邊關(guān)系,只有把這些連邊關(guān)系映射成節(jié)點之間距離才能采用密度峰值聚類算法進(jìn)行節(jié)點聚類,考慮到真實網(wǎng)絡(luò)中節(jié)點與直接鄰居、間接鄰居的關(guān)系較為密切,而與其他節(jié)點較為疏遠(yuǎn),同時為了降低算法的時間復(fù)雜度,在計算節(jié)點間距離時,只計算節(jié)點與直接鄰居、間接鄰居間的距離.距離可以通過節(jié)點間的路徑長度和路徑數(shù)目來度量,路徑越短,兩點間距離越近;相同長度的路徑數(shù)目越多,兩點間距離越近,節(jié)點間的距離采用公式(7)計算.

(7)

其中,d(u,v)表示節(jié)點u,v間的距離.當(dāng)u∈DNB(v)時,節(jié)點u,v間距離由長度為1的路徑所表示的距離和長度為2的路徑所表示的距離相加計算得到.而當(dāng)u?DNB(v)時,節(jié)點u,v間距離只需考慮由長度為2的路徑所表示的距離.

2)局部密度計算:在獲取到節(jié)點間距離后,繼續(xù)根據(jù)距離計算節(jié)點的局部密度.為了增加節(jié)點局部密度取值的多樣性以及減小算法在小數(shù)據(jù)集上受到大的統(tǒng)計誤差的影響,這里可以通過引入高斯核函數(shù)對DPC算法中求取節(jié)點的局部密度方法做出改進(jìn),改進(jìn)后的局部密度計算方法如公式(8)所示.

(8)

其中,rho(u)表示節(jié)點u的局部密度.

3)跟隨距離計算:經(jīng)過步驟2)得到節(jié)點的局部密度后,接下來便可以根據(jù)公式(6)求取節(jié)點的跟隨距離,并根據(jù)跟隨距離選取跟隨節(jié)點.跟隨節(jié)點定義如下:

定義6.跟隨節(jié)點.節(jié)點u的跟隨節(jié)點fol(u)定義為:

(9)

其中,del(u)表示根據(jù)公式(6)計算得到的節(jié)點u的跟隨距離.

4)非重疊社區(qū)生成:首先,計算網(wǎng)絡(luò)節(jié)點局部密度和跟隨距離的平均值;其次,根據(jù)定義(7)求取社區(qū)中心點集合.最后,根據(jù)DPC算法生成社區(qū).為了解決DPC算法不能較好的應(yīng)用到重疊社區(qū)發(fā)現(xiàn)中,在生成社區(qū)的過程中,需要記錄社區(qū)邊界點,后續(xù)步驟可以對社區(qū)邊界點進(jìn)行社區(qū)歸屬判斷來生成重疊社區(qū).社區(qū)中心點定義如下:

定義7.社區(qū)中心點.社區(qū)集合C的中心點CC定義為:

(10)

其中,ui∈V,avg(del(ui))表示網(wǎng)絡(luò)中節(jié)點的平均跟隨距離,avg(rho(ui))表示網(wǎng)絡(luò)中節(jié)點的平均局部密度,λ、γ為調(diào)節(jié)參數(shù).γ·avg(rho(ui))社區(qū)中心點的局部密度閾值,λ·avg(del(ui))為社區(qū)中心點的跟隨距離閾值,?v∈V,只要del(v)和rho(v)分別不小于跟隨距離閾值和局部密度閾值,即可被自動選為社區(qū)中心點.

5)重疊社區(qū)生成:在初步生成非重疊社區(qū)后,接下來需要對社區(qū)邊界點進(jìn)行社區(qū)歸屬判斷來把它們劃分到合適的社區(qū)中.首先,計算社區(qū)邊界點對各社區(qū)的歸屬度大小.其次,計算社區(qū)邊界節(jié)點的社區(qū)歸屬度閾值.最后,比較社區(qū)歸屬度和社區(qū)歸屬度閾值,把邊界點劃分到滿足條件的重疊社區(qū)集合中.社區(qū)歸屬度和歸屬度閾值分別采用公式(11)、公式(12)計算,重疊社區(qū)集合如定義7所示.

(11)

其中,affi(v)表示節(jié)點v對社區(qū)Ci的社區(qū)歸屬度,σ(u,v)表示節(jié)點v和節(jié)點u之間的余弦相似度,d(u)表示節(jié)點u的度.

(12)

其中,affth(v)表示節(jié)點v的社區(qū)歸屬度閾值,CI={i|v∈Ci},表示與節(jié)點v有邊連接的社區(qū),|CI|表示集合CI中元數(shù)數(shù)目,β為調(diào)節(jié)參數(shù),用來度量邊界點的社區(qū)歸屬度均勻分布情況,由定義可知β≥1.

定義8.重疊社區(qū)集合.節(jié)點v所在的重疊社區(qū)集合Soc(v)定義為:

Soc(v)={Ci|affi(v)>affth(v),?i∈[1,|C|]∧v∈Ci}

(13)

3.4 算法實現(xiàn)

根據(jù)上述設(shè)計思想,給出算法的總體實現(xiàn)步驟如下.

算法1.OCDPCB算法

輸入:復(fù)雜網(wǎng)絡(luò)G=(V,E)

輸出:重疊社區(qū)C

1. (Pd,dmax,dmin)=calDist(V); /*節(jié)點間距離計算*/

2. (Rho,dc)= calRho(V,Pd,dmax,dmin);/*局部密度計算*//*跟隨距離計算*/

3. (Nnb,Del,Rl)= calDelta(Rho,Pd,dmax);

/*非重疊社區(qū)生成*/

4. (C,BC)= genNonOveCom((Rho,Rl,Del,Nnb,dc));

5.C=genOveCom(C,BC); /*重疊社區(qū)生成*/

6.outputC;

3.5 節(jié)點間距離計算

計算節(jié)點間的距離時只考慮節(jié)點與直接鄰居、間接鄰居間的距離,距離計算的步驟如函數(shù)1所示.

函數(shù)1.calDist(V)

輸入:網(wǎng)絡(luò)節(jié)點集V

輸出:節(jié)點間距離字典Pd,距離最大值dmax, 距離最小值dmin

1.Pd=empty map;

2. FOR eachv∈V

3. FOR eachu∈DNB(v)

/*向Pd中添加元素<(v,u),d(v,u)>,(v,u)為

Pd的鍵,d(v,u)為Pd的值*/

4.Pd.put(<(v,u),d(v,u)>);

5. FOR eachr∈DNB(u)

6. IFd(v,r)?PdTHEN

7.Pd.put(<(v,r),d(v,r)>);

8. END IF

9. END FOR

10. END FOR

11. END FOR

12.dmax=max{dis|dis=Pd.get((u,v)),u∈V∧v∈V};

13.dmin=min{dis|dis=Pd.get((u,v)),u∈V∧v∈V};

14. outputPd,dmax,dmin;

函數(shù)1主要步驟如下:

1)初始化節(jié)點間距離字典Pd為空;

2)利用公式(7)計算節(jié)點與直接鄰居節(jié)點間的距離,并把該距離添加到距離字典Pd中(第3～4行);

3)利用公式(7)計算節(jié)點與間接鄰居節(jié)點間的距離,并把該距離添加到距離字典Pd中(第5～9行);

4)求出節(jié)點間距離最大值dmax和最小值dmin(第12-13行);

5)輸出距離字典Pd,dmax,dmin(第14行).

3.6 局部密度計算

根據(jù)函數(shù)1計算得到節(jié)點間距離后,繼續(xù)根據(jù)該距離計算節(jié)點的局部密度,節(jié)點局部密度計算的步驟如函數(shù)2所示.

函數(shù)2.calRho(V,Pd,dmax,dmin)

輸入:網(wǎng)絡(luò)節(jié)點集V,節(jié)點間距離字典Pd,距離最大值dmax,距離最小值dmin

輸出:節(jié)點局部密度字典Rho,距離閾值dc

1.Rho=empty map,np=0,nb=0;

/*根據(jù)DPC算法的dc選取規(guī)則,np應(yīng)該在[0.01,0.02]內(nèi)取值*/

2. WHILE(np<0.01‖np>0.02) DO

3. FOR eachdis∈Pd

4. IF(dis.value<=dc) THEN /*dis.value表示字典

元素的值*/

5.nb+=2;

6. END IF

7. END FOR

8.np=nb/|V|2;

9. IF(np>=0.02) THEN

10.dmax=dc;

11.dc=0.5×(dmax+dmin);

12. ElSE IF(np<0.01) THEN

13.dmin=dc;

14.dc=0.5×(dmax+dmin);

15. END IF

16. END WHILE

17. FOR eachu∈V

18.Rho.put()

19. END FOR

20. outputRho,dc;

函數(shù)2主要步驟如下:

1)初始化節(jié)點的局部密度字典Rho為空,網(wǎng)絡(luò)所有節(jié)點的dc-鄰域內(nèi)節(jié)點數(shù)nb及nb與網(wǎng)絡(luò)節(jié)點總數(shù)的比例np為0(第1行);

2)根據(jù)DPC算法中距離閾值的選取規(guī)則計算閾值dc(第2～16行);

3)根據(jù)dc和公式(8)計算網(wǎng)絡(luò)中每個節(jié)點的局部密度(第17～19行);

4)輸出局部密度字典Pd,距離閾值dc(第20行).

3.7 跟隨距離計算

函數(shù)3.calDelta(Rho,Pd,dmax)

輸入:節(jié)點局部密度字典Rho,節(jié)點間距離字典Pd,距離最大值dmax

輸出:節(jié)點跟隨鄰居字典Nnb,節(jié)點跟隨距離字典Del,排序后的局部密度列表Rl

1.Rl=empty list,Nnb=empty map,Del=empty map,NB=Ф;

2. add each element inRhotoRl;

3. sort(Rl); /*對Rl按局部密度大小降序排序*/

4. FOR(0≤i≤|Rl|)

5. IF(i=0) THEN

6.Nnb.put(); / *cp表示Rl中下標(biāo)為i的元素

對應(yīng)的節(jié)點*/

7.Del.put();

8. ELSE

9.NB=DNB(cp)∪INB(cp);

/*根據(jù)公式(6)和定義6求取節(jié)點cp的跟隨距離del(cp)和跟隨鄰居fol(cp)*/

10.Nnb.put();

11.Del.put();

12. END IF

13. ENF FOR

14. outputNnb,Del,Rl;

函數(shù)3主要步驟如下:

1)初始化局部密度列表Rl、節(jié)點跟隨鄰居字典Nnb,跟隨距離字典Del和鄰居節(jié)點集合NB為空(第1行);

2)把Rho中的元素逐個添加到Rl中,并對Rl按局部密度值大小降序排序(第2～3行);

3)根據(jù)公式(6)和定義(6)求取節(jié)點的跟隨鄰居和跟隨距離(第4～13行);

4)輸出節(jié)點跟隨鄰居字典Nnb,跟隨距離字典Del和排序后的局部密度列表Rl(第14行).

3.8 非重疊社區(qū)生成

函數(shù)4.genNonOveCom(Rho,Rl,Del,Nnb,dc)

輸入:節(jié)點局部密度字典Rho,局部密度列表Rl,節(jié)點跟隨距離Del,節(jié)點跟隨鄰居字典Nnb,距離閾值dc

輸出:非重疊社區(qū)C,社區(qū)邊界點BC

1.C= empty map,Cn=empty map,BC=Ф;

2. FOR eachv∈CC/*CC為根據(jù)定義(7)計算的社區(qū)中心*/

3.Cn.put() ;

4. END FOR

5. FOR eachu∈Rl

6. IF(uk?CC) THEN /*uk為Rl中元素u對應(yīng)的節(jié)點*/

7.nnb=Nnb.get(uk);

8.cI=Cn.get(nnb);

9. IF(cI∈Cn.values()) THEN

10.BC=BC∪uk,ifuk∈BCi; /*i表示社區(qū)標(biāo)號*/

11.Cn(uk)=cI;

12. ELSE

13.Cn(uk)=uk;

14. END IF

15. END IF

16. END FOR

17. FOR(eachu∈Cn.keys())

18.cI=Cn.get(u);

19.C.put();

20. END FOR

21. outputC,BC;

函數(shù)4主要步驟如下:

1)初始化非重疊社區(qū)字典C、節(jié)點及其所在社區(qū)標(biāo)號字典Cn和社區(qū)邊界點集合BC為空(第1行);

2)給社區(qū)中心點分配社區(qū)標(biāo)號(第2～4行);

3)根據(jù)DPC算法中節(jié)點分派規(guī)則給社區(qū)非中心點分配社區(qū),并根據(jù)定義(5)計算社區(qū)邊界點(第5～16行);

4)把網(wǎng)絡(luò)中非社區(qū)中心點又沒有找到跟隨節(jié)點的其他節(jié)點中密度最大的作為社區(qū)中心(第13行);

5)把節(jié)點及其所在社區(qū)標(biāo)號字典Cn轉(zhuǎn)換成社區(qū)C(第17～20行);

6)輸出非重疊社區(qū)C,社區(qū)邊界點BC(第21行).

3.9 重疊社區(qū)生成

函數(shù)5.genOveCom(C,BC)

輸入:非重疊社區(qū)C,社區(qū)邊界點BC

輸出:重疊社區(qū)C

1.Aff=empty map ,Oc=empty map ,S=Ф;

2. FOR eachv∈BC;

3. FOR eachi∈CI/*CI表示與節(jié)點v有邊連接的社區(qū)標(biāo)

號集合*/

Aff.put();

4. END FOR

5. IF(β·min(affi(v)

6.affth(v)= min(affi(v));

7. ELSE

8.affth(v)= avg(affth(v));

9. END IF

10. FOR eachi∈Aff.keys()

11. IF(Aff.get(i)≥affth(v)) THEN

12.S=S∪i;

13. END IF

14. END FOR

15.Oc.put();

16. END FOR

17. FOR eachv∈Oc.keys()

18. FOR eachcI∈Oc.get(v)

19.C.put(); /*cI為節(jié)點v的歸屬社

區(qū)標(biāo)號*/

20. END FOR

21. END FOR

22. outputC;

函數(shù)5主要步驟如下:

1)初始化社區(qū)歸屬度字典Aff、社區(qū)邊界點及其歸屬社區(qū)標(biāo)號字典Oc和重疊社區(qū)標(biāo)號集合S為空(第1行);

2)計算社區(qū)邊界點的社區(qū)歸屬度,并添加到社區(qū)歸屬度字典Aff中(第2～4行);

3)根據(jù)公式(12)計算社區(qū)邊界點的社區(qū)歸屬度閾值(5～9行);

4)計算社區(qū)邊界點的歸屬社區(qū)標(biāo)號(第10～15行);

5)把社區(qū)邊界點劃分到相應(yīng)的社區(qū)中(第17～21行);

6)輸出重疊社區(qū)C(第22行).

3.10 復(fù)雜度分析

設(shè)網(wǎng)絡(luò)節(jié)點數(shù)為n,邊數(shù)為m,網(wǎng)絡(luò)的平均度為k,社區(qū)邊界點數(shù)為no,社區(qū)數(shù)目為C,計算距離閾值dc時需要的迭代次數(shù)為I,節(jié)點所屬的平均重疊社區(qū)數(shù)為om.

首先分析算法的時間復(fù)雜度.函數(shù)calDist()中,步驟(2)～步驟(11)計算的是節(jié)點與其直接和間接鄰居的距離,因此其時間復(fù)雜度為O(k2n).步驟(12)～步驟(13)求取距離的最大值、最小值時只需遍歷一次節(jié)點間距離字典,時間復(fù)雜度為O(k2n).所以,函數(shù)calDist()的總時間復(fù)雜度為O(k2n).函數(shù)calRho()中,步驟(2)～步驟(16)在計算距離閾值時假設(shè)需要迭代I次,每次迭代的時間復(fù)雜度為O(k2n),所以計算距離閾值的時間復(fù)雜度為O(k2n·I).步驟(17)～步驟(19)根據(jù)節(jié)點間的距離計算節(jié)點局部密度的時間復(fù)雜度為O(k2n).所以函數(shù)calRho()的總時間復(fù)雜度為O(k2n·I).函數(shù)calDelta()中,步驟(3)對節(jié)點的局部密度排序的時間復(fù)雜度為O(nlogn).步驟(4)～步驟(13)求節(jié)點的跟隨距離的時間復(fù)雜度為O(k2n).所以函數(shù)calDelta()的總時間復(fù)雜度O(n).函數(shù)genNonOveCom()需要存儲節(jié)點及節(jié)點所在的社區(qū)標(biāo)號,空間復(fù)雜度為O(n).函數(shù)genOveCom()需要存儲社區(qū)邊界點及其所在的社區(qū)標(biāo)號,空間復(fù)雜度為O(no).因此,OCDPCB算法總的空間復(fù)雜度為O(k2n+k2n+n+n+k2n+no).在真實網(wǎng)絡(luò)中,通常有k<

4 實驗結(jié)果與分析

為了檢測OCDPCB 算法的性能,分別采用人工數(shù)據(jù)集和真實網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行測試.實驗環(huán)境為一臺配置3.1GHz Pentium CPU,4G內(nèi)存的PC機(jī),操作系統(tǒng)為Windows7 64位.采用多種經(jīng)典的重疊社區(qū)發(fā)現(xiàn)算法進(jìn)行對比,所有算法都是基于Java編程語言實現(xiàn).

4.1 實驗數(shù)據(jù)集

1)人工數(shù)據(jù)集

采用LFR[29]工具生成人工模擬的網(wǎng)絡(luò)數(shù)據(jù)集,生成網(wǎng)絡(luò)數(shù)據(jù)基本參數(shù)信息如表1所示.

表1 人工網(wǎng)絡(luò)參數(shù)
Table 1 Artificial network parameters

參 數(shù)說 明N網(wǎng)絡(luò)節(jié)點數(shù)k節(jié)點平均度maxk節(jié)點最大度minc最大社區(qū)節(jié)點數(shù)目maxc最小社區(qū)節(jié)點數(shù)目on重疊節(jié)點數(shù)目om重疊節(jié)點所屬社區(qū)數(shù)目mu社區(qū)混合參數(shù)

通過設(shè)置不同的on,om和mu參數(shù)值可以生成不同的網(wǎng)絡(luò)結(jié)構(gòu),實驗中所使用的人工網(wǎng)絡(luò)信息如表 2所示.

表2 LFR基準(zhǔn)網(wǎng)絡(luò)信息
Table 2 Information of LFR Benchmarks

IDNkmaxkmincmaxcmuonomS110002050201000.1～0.71003S210002050201000.31002～7S310002050201000.340～2403S44k～24k2050201000.31003

2)真實數(shù)據(jù)集

為了檢測算法在真實網(wǎng)絡(luò)上的性能,選取了9個真實網(wǎng)絡(luò)數(shù)據(jù)集,詳細(xì)信息如表 3 所示.

表3 真實網(wǎng)絡(luò)信息
Table 3 Information of Real NetWorks

名稱節(jié)點數(shù)邊數(shù)平均度聚集系數(shù)Karate[27]34784.590.571Enron subnet[30]619330.326Dolphins[27]621595.130.259Football[27]11561310.660.403Polblogs[11]14901671522.440.694Netscience[11]158927423.450.694Power[27]494165942.670.08CA-GrQc[18]1484512125116.120.53CA-CondMat[18]23133934394.040.634

4.2 實驗方法和評價指標(biāo)

4.2.1 實驗方法

為比較 OCDPCB 算法的性能,選取COPRA 算法[19]、CPM 算法[12]、DEMON算法[16]、DBLINK算法[24]和CSDPC算法[27]作為對比算法.通過比較算法在不同人工數(shù)據(jù)集和真實數(shù)據(jù)集上的實驗結(jié)果,分析OCDPCB 算法的精度和效率.實驗過程中各算法的參數(shù)和CSDPC算法的聚類中心均通過多次實驗取最佳值來設(shè)定,各算法的參數(shù)設(shè)置如表4所示.

表4 算法參數(shù)設(shè)置
Table 4 Algorithm parameter settings

算法名稱參數(shù)設(shè)置COPRAv=2～15CPMk=5～9DEMONe=0.1～0.5DBLINKε=0.2～0.4,Minpts=2～10CSDPC—OCDPCBλ=0.8～1.1,γ=1.4～1.9,β=1.6～3.1

4.2.2 評價指標(biāo)

由于 LFR 基準(zhǔn)網(wǎng)絡(luò)的真實網(wǎng)絡(luò)結(jié)構(gòu)已知,所以采用標(biāo)準(zhǔn)化互信息[29](Normalized Mutual Information,簡稱NMI)作為人工生成網(wǎng)絡(luò)的評價指標(biāo).NMI的定義如下:

(14)

其中,CA為標(biāo)準(zhǔn)社區(qū)劃分的結(jié)果,CB為算法所得到社區(qū)劃分的結(jié)果,矩陣N的行對應(yīng)標(biāo)準(zhǔn)社區(qū)結(jié)果,列對應(yīng)算法得到的社區(qū)檢測結(jié)果,Ni·為第i行的總和,N·j為第j列的總和.當(dāng)算法得到社區(qū)劃分的結(jié)果與標(biāo)準(zhǔn)劃分的結(jié)果越相近時,NMI 的值越接近1.

在真實網(wǎng)絡(luò)中,采用重疊模塊度EQ[31]衡量重疊社區(qū)發(fā)現(xiàn)的質(zhì)量.EQ的定義如下:

(15)

其中,Qx表示結(jié)果社區(qū)中節(jié)點x屬于的社區(qū)數(shù),Axy表示原始網(wǎng)絡(luò)的鄰接矩陣,kx表示節(jié)點x的度,m是原始網(wǎng)絡(luò)的邊數(shù).

4.3 算法參數(shù)影響實驗

該部分主要基于人工網(wǎng)絡(luò)來分析參數(shù)λ、γ和β對算法精度的影響.

4.3.1 參數(shù)λ的影響實驗

為了分析參數(shù)λ對社區(qū)中心點跟隨距離閾值的影響,固定γ=1.8,考慮到當(dāng)λ=0時,生成的社區(qū)的NMI值接近0,所以在實驗中控制λ值在[0.1,2.0]內(nèi)變化,在人工網(wǎng)絡(luò)S1上進(jìn)行實驗,實驗結(jié)果如圖1所示.

圖1 參數(shù)λ的實驗結(jié)果Fig.1 Experimental results of the parameter λ

圖1中對每一個不同的mu值,參數(shù)λ在[0.6,1.4]內(nèi)變化取值時,OCDPCB算法的NMI值大多呈現(xiàn)先增大、接著保持穩(wěn)定、后減小的變化趨勢.而當(dāng)λ在[0.8,1.1]內(nèi)變化取值時,NMI值較為穩(wěn)定,因此,可以認(rèn)為當(dāng)λ在該范圍內(nèi)取值時對OCDPCB算法聚類中心點的跟隨距離閾值沒有明顯影響,從而不會對社區(qū)中心點的選取造成顯著影響而降低社區(qū)發(fā)現(xiàn)的精度,所以λ合適的取值范圍為[0.8,1.1].另外,當(dāng)λ≥1.1時,OCDPCB算法的NMI值在mu≤0.2時較為穩(wěn)定,當(dāng)mu>0.2時,NMI值存在明顯的下滑,是因為當(dāng)mu增大,網(wǎng)絡(luò)結(jié)構(gòu)變復(fù)雜,社區(qū)中心點不易區(qū)分,λ的變化會對社區(qū)發(fā)現(xiàn)結(jié)果造成較大影響.

4.3.2 參數(shù)γ的影響實驗

為了分析參數(shù)γ對社區(qū)中心點局部密度閾值的影響,固定λ=0.9,考慮到當(dāng)γ=0時,生成的社區(qū)的NMI值接近0,所以在實驗中控制λ值在[0.1,2.4]內(nèi)變化,在人工網(wǎng)絡(luò)S1上進(jìn)行實驗,實驗結(jié)果如圖2所示.

圖2 參數(shù)γ的實驗結(jié)果Fig.2 Experimental results of the parameter γ

從圖2可以看出,對于每一個不同的mu值,參數(shù)γ在[0.1,2.4]內(nèi)變化取值時,OCDPCB算法的NMI值均呈現(xiàn)先增大、接著保持穩(wěn)定、后減小的變化趨勢.而當(dāng)γ在[1.4,1.9]內(nèi)變化取值時,NMI值較為穩(wěn)定,因此,可以認(rèn)為當(dāng)γ在該范圍內(nèi)取值時對OCDPCB算法聚類中心點的局部密度閾值沒有明顯影響,從而不會對社區(qū)中心點的選取造成顯著影響而降低社區(qū)發(fā)現(xiàn)的精度.所以γ合適的取值范圍為[1.4,1.9].另外,當(dāng)γ≥1.5時,OCDPCB算法的NMI值在所有mu取不同值的情況下,NMI值均較為平穩(wěn),表明社區(qū)中心點的選取對節(jié)點的局部密度敏感性較弱,是因為在求取節(jié)點的局部密度時改進(jìn)了DPC算法中節(jié)點局部密度的計算方法,改進(jìn)后的局部密度計算方法保證了節(jié)點局部密度取值的多樣性,從而降低了社區(qū)發(fā)現(xiàn)結(jié)果對節(jié)點局部密度的敏感性.由圖1和圖2比較可知,OCDPCB算法對參數(shù)λ的敏感度高于參數(shù)γ.

4.3.3 參數(shù)β的影響

為了分析參數(shù)β對社區(qū)歸屬度閾值的影響,固定λ=0.9,γ=1.8,β值在[1.0,4.9]內(nèi)變化,在人工網(wǎng)絡(luò)S2上進(jìn)行實驗,實驗結(jié)果如圖3所示.

從圖3可看出,對于不同的om值,參數(shù)β在[1.0,4.9]內(nèi)變化取值時,OCDPCB算法的NMI值均呈現(xiàn)先增大、接著保持穩(wěn)定、后減小的變化趨勢,主要是因為當(dāng)β值較小時,社區(qū)歸屬度閾值相對較大,邊界點與大部分有關(guān)聯(lián)社區(qū)的歸屬度小于歸屬度閾值,不能當(dāng)作重疊節(jié)點劃分到這些社區(qū)中,屬過少的社區(qū)降低了社區(qū)發(fā)現(xiàn)的精度.當(dāng)β值較大時,社區(qū)歸屬度閾值相對較小,邊界點與大部分有關(guān)聯(lián)社區(qū)的歸屬度大于歸屬度閾值,從而被當(dāng)作重疊節(jié)點劃分到這些社區(qū)中,隸屬過多的社區(qū)也會降低社區(qū)發(fā)現(xiàn)的精度.而當(dāng)β在[1.8,3.1]內(nèi)變化取值時,NMI值較高且較為穩(wěn)定,因此,可以認(rèn)為當(dāng)β在該范圍內(nèi)取值時,能夠得到較為準(zhǔn)確的社區(qū)歸屬度閾值,OCDPCB算法能根據(jù)該閾值正確的對社區(qū)邊界點進(jìn)行社區(qū)劃分,從而獲得較高的社區(qū)發(fā)現(xiàn)精度.在β相同值的情況下,om值越大,NMI值越低,是因為om增大,網(wǎng)絡(luò)中重疊節(jié)點隸屬的社區(qū)數(shù)增加,不同社區(qū)之間的聯(lián)系變得更加緊密,OCDPCB算法更難準(zhǔn)確識別出社區(qū)結(jié)構(gòu).另外,om值越大,NMI值取得最大值時對應(yīng)的β值越小,是因為om增大,社區(qū)邊界點隸屬的社區(qū)數(shù)目增多,節(jié)點的最大社區(qū)歸屬度和最小社區(qū)歸屬度差值減小,從而取得合適社區(qū)歸屬度閾值時對應(yīng)的β值減小.

圖3 參數(shù)β的實驗結(jié)果Fig.3 Experimental results of the parameter β

4.4 算法精度實驗

4.4.1 人工數(shù)據(jù)集上的實驗結(jié)果

圖4 不同mu值精度實驗Fig.4 Experimental results of accuracy with different mu

圖4為各算法在人工網(wǎng)絡(luò) S1上的實驗結(jié)果.由圖4可知,隨著參數(shù)mu逐漸增大,各算法的NMI值逐漸減小.當(dāng)mu≥0.6時,各算法的NMI值均較低.這主要是因為mu值過大導(dǎo)致社區(qū)間的聯(lián)系較為緊密,社區(qū)結(jié)構(gòu)不明顯,各算法無法準(zhǔn)確識別出網(wǎng)絡(luò)的真實社區(qū).DEMON算法的NMI值在多數(shù)情況下更低,在mu逐漸增大的過程中,NMI值下降趨勢較為顯著,且當(dāng)mu≥0.6時,NMI值接近為0.這是因為DEMON算法需要對整個網(wǎng)絡(luò)每個節(jié)點形成的局部社區(qū)進(jìn)行融合形成最優(yōu)的全局社區(qū),容易形成多個獨立社區(qū),影響算法的精度.另外,DEMON算法在生成局部社的過程中采用了LPA算法,對社區(qū)結(jié)果也會造成不穩(wěn)定.CPM算法的NMI值多數(shù)情況下較低且出現(xiàn)抖動現(xiàn)象,是因為CPM算法是通過擴(kuò)展完全子圖來發(fā)現(xiàn)k-派系社區(qū),適用于社區(qū)內(nèi)部連接較為緊密的網(wǎng)絡(luò).另外,CPM算法無法為不同的網(wǎng)絡(luò)找到一個固定且精確的k值,這會造成算法結(jié)果不穩(wěn)定.COPRA 算法在mu≤0.5時NMI值較大,但當(dāng)mu>0.5時,NMI值急劇下降,因為 COPRA 算法是基于標(biāo)簽傳播,在節(jié)點標(biāo)簽的選擇上具有隨機(jī)性,當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)變復(fù)雜時,較多的節(jié)點無法獲取到正確的社區(qū)標(biāo)簽.CSDPC算法在mu≤0.3時,NMI值較大且下降較緩,但當(dāng)mu>0.3時,NMI值急劇下降,NMI值變化趨勢和OCDPCB算法類似,但OCDPCB算法在多數(shù)情況下獲得了更好的結(jié)果.是因為CSDPC算法和OCDPCB算法均是基于密度峰值聚類原理,在網(wǎng)絡(luò)結(jié)構(gòu)較簡單時,二者能夠準(zhǔn)確的識別出社區(qū)中心點以及其他節(jié)點需要跟隨的節(jié)點,從而找到正確的社區(qū)并分派到其中.但當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)變復(fù)雜時,OCDPCB算法對含有重疊節(jié)點的社區(qū)邊界點進(jìn)行了社區(qū)歸屬判斷,根據(jù)歸屬度把重疊節(jié)點劃分到對應(yīng)的社區(qū)中,進(jìn)一步提高了重疊社區(qū)劃分的準(zhǔn)確性.

圖5 不同om值精度實驗Fig.5 Experimental results of accuracy with different om

圖 5為各算法在人工網(wǎng)絡(luò) S2上的實驗結(jié)果.由圖5可知,隨著參數(shù)om逐漸增大,除CPM算法外,其余五種算法的NMI 值逐漸減小,是因為參數(shù)om增大,網(wǎng)絡(luò)中重疊節(jié)點隸屬的社區(qū)數(shù)增加,此時不同社區(qū)之間的聯(lián)系變得更加緊密,社區(qū)結(jié)構(gòu)變得模糊.CPM算法的NMI值隨著om逐漸增大,出現(xiàn)了抖動現(xiàn)象,是因為CPM算法在生成k-派系社區(qū)時,無法為不同的網(wǎng)絡(luò)找到一個固定且精確的k值,這會造成算法在不同結(jié)構(gòu)的網(wǎng)絡(luò)上通過擴(kuò)展完全子圖獲取社區(qū)的結(jié)果有較大差OCDPCB算法基于密度峰值聚類的原理,各節(jié)點能夠準(zhǔn)確的識別出跟隨節(jié)點,從而選擇加入到對應(yīng)的社區(qū)中;另外,OCDPCB算法對社區(qū)邊界點進(jìn)行了社區(qū)歸屬判斷,而重疊節(jié)點大多是社區(qū)邊界點,因此根據(jù)歸屬度把社區(qū)邊界點劃分到對應(yīng)的社區(qū)中,也能提高重疊社區(qū)劃分的準(zhǔn)確性.

圖6 不同on值精度實驗Fig.6 Experimental results of accuracy with different on

圖6為各算法在人工網(wǎng)絡(luò)S3上的實驗結(jié)果.由圖6可知,隨著參數(shù)on逐漸增大,各算法的NMI值逐漸減小,是因為on增大,網(wǎng)絡(luò)中重疊節(jié)點數(shù)增加,此時不同社區(qū)間的連接邊數(shù)目增多,社區(qū)邊界變得模糊,算法不能準(zhǔn)確確定社區(qū)邊界.除CSDPC算法外,其余五個算法在on≤200時,NMI值下降較為明顯,on>200時,NMI值下降較緩并趨于穩(wěn)定,表明這些算法在高度重疊的網(wǎng)絡(luò)中也能保證一定的社區(qū)劃分能力.在on≥240時,CSDPC算法的NMI值最低并呈下降趨勢,是因為該算法不是重疊社區(qū)發(fā)現(xiàn)算法,只能把節(jié)點劃分到唯一的社區(qū)中,而當(dāng)網(wǎng)絡(luò)中存在較多的重疊節(jié)點時,會導(dǎo)致這些重疊節(jié)點及跟隨這些重疊節(jié)點的其他節(jié)點被誤劃分到對應(yīng)的社區(qū)中.OCDPCB算法在多數(shù)情況下獲得了更好的結(jié)果,是因為OCDPCB算法對社區(qū)邊界點進(jìn)行了社區(qū)歸屬判斷,而重疊節(jié)點大多是社區(qū)邊界點,因此根據(jù)歸屬度把社區(qū)邊界點劃分到對應(yīng)的社區(qū)中,能提高重疊社區(qū)劃分的準(zhǔn)確性.

4.4.2 真實據(jù)集上的實驗結(jié)果

圖7為各算法在9個真實網(wǎng)絡(luò)數(shù)據(jù)集上的實驗結(jié)果.從圖7可以看出,CPM算法和DEMON算法在所有網(wǎng)絡(luò)上的模塊度值較低,在Karate、Enron subnet、Power和CA-CondMat這四個數(shù)據(jù)集上的模塊度值遠(yuǎn)小于其他算法,主要是因為CPM算法和DEMON算法都是基于擴(kuò)展局部社區(qū)來尋求整過網(wǎng)絡(luò)的最優(yōu)社區(qū),適合于稠密型網(wǎng)絡(luò),而以上四個數(shù)據(jù)集所代表的網(wǎng)絡(luò)連接較為稀疏.除了在 Football 網(wǎng)絡(luò)上OCDPCB算法的模塊度略低于COPRA 算法外,在其他多數(shù)網(wǎng)絡(luò)上都能取得更高的模塊度,并且明顯高于其他算法的模塊度,主要是因為OCDPCB算法基于密度峰值聚類的原理,能夠準(zhǔn)確的識別出社區(qū)中心點以及其他節(jié)點的跟隨節(jié)點,從而找到對應(yīng)的跟隨社區(qū).另外,OCDPCB算法對社區(qū)邊界點進(jìn)行了社區(qū)歸屬判斷,根據(jù)歸屬度把邊界節(jié)點中的重疊節(jié)點劃分到多個隸屬的社區(qū)中,這兩種策略提高了社區(qū)劃分的準(zhǔn)確性.CSDPC算法因其空間復(fù)雜度為O(n2),無法運行在較大規(guī)模數(shù)據(jù)集上,所以在CA-GrQc和CA-CondM-at數(shù)據(jù)集上,CSDPC算法的模塊度為空.

圖7 真實數(shù)據(jù)集上的實驗結(jié)果Fig.7 Experiment result on the real data set

4.5 算法擴(kuò)展性實驗

由于CSDPC算法具有較高的空間復(fù)雜度,無法適用于較大規(guī)模網(wǎng)絡(luò),所以該算法的效率實驗在較小規(guī)模的人工數(shù)據(jù)集上進(jìn)行,實驗結(jié)果如圖8(b)所示,其他算法的實驗結(jié)果如由圖8(a)所示.由圖8可知,COPRA算法的運行速度最快,是由于COPRA算法基于LPA算法的原理,運行時間僅依賴于算法的迭代次數(shù),其時間復(fù)雜度和LPA算法一樣,均為線性級別,所以具有較高的效率.DEMON算法、DBLINK算法運行時間較長,但運行時間隨網(wǎng)絡(luò)節(jié)點數(shù)的增加近似線性增長,與這兩種算法的時間復(fù)雜度為線性級別保持一致.CPM算法運行時間在網(wǎng)絡(luò)節(jié)點數(shù)較少時比OCDPCB算法的運行時間略低,但當(dāng)節(jié)點數(shù)逐漸增大時,CPM算法運行時間漸漸高于OCDPCB算法,是因為CPM算法的時間復(fù)雜度是指數(shù)級別,當(dāng)網(wǎng)絡(luò)節(jié)點增大時,CPM算法的運行時間將急劇上升.CSDPC算法的運行時間隨著網(wǎng)絡(luò)節(jié)點數(shù)增大急劇上升,是因為該算法在求取節(jié)點間距離時采用了Dijkstra算法,時間復(fù)雜度為O(n2log(n)).而OCDPCB算法在計算節(jié)點間距離時只考慮了節(jié)點的直接鄰居、間接鄰居,所以時間復(fù)雜度為近似為網(wǎng)絡(luò)邊數(shù)的線性函數(shù),因此,OCDPCB算法能夠適應(yīng)大規(guī)模復(fù)雜網(wǎng)絡(luò).

圖8 算法運行時間對比Fig.8 Comparison of algorithms′ running time

5 總 結(jié)

本文提出了一種基于密度峰值和社區(qū)歸屬度的重疊社區(qū)發(fā)現(xiàn)算法,該算法在計算節(jié)點間距離時只考慮節(jié)點與直接鄰居和間接鄰居的距離,有效的降低了算法的時間復(fù)雜度.另外,定量給出了聚類中心點的局部密度閾值、跟隨距離閾值和局部密度均值、跟隨距離均值之間的計算關(guān)系,通過該計算關(guān)系解決了密度峰值算法中這兩個閾值需要人為指定的問題.最后,把密度峰值算法應(yīng)用到社區(qū)發(fā)現(xiàn)中,并提出社區(qū)歸屬度計算方法,根據(jù)社區(qū)歸屬度對可能存在較多重疊節(jié)點的社區(qū)邊界節(jié)點進(jìn)行社區(qū)歸屬劃分,可以較好的識別出網(wǎng)絡(luò)中的重疊社區(qū).

未來的工作將考慮結(jié)合離群點識別算法,通過離群點識別算法來選取密度峰值算法的聚類中心,以減少參數(shù)對算法的影響.另外,為了使OCDPCB算法能夠適應(yīng)于更大規(guī)模的社區(qū)挖掘,將考慮基于MapReduce模型實現(xiàn)算法的并行化,以適應(yīng)大規(guī)模復(fù)雜網(wǎng)絡(luò)的處理.