基于標(biāo)簽傳播的重疊社區(qū)檢測算法

陳 旭 張 俊 曲賢菲 田朝霞

(大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院 遼寧 大連 116026)

0 引 言

現(xiàn)實世界中包括社會科學(xué)、生物信息、計算機等許多領(lǐng)域的網(wǎng)絡(luò)都可以用復(fù)雜網(wǎng)絡(luò)來表示，社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的重要特性[1]，揭示網(wǎng)絡(luò)中存在的社區(qū)結(jié)構(gòu)有利于從網(wǎng)絡(luò)中挖掘出有實際意義的模塊或?qū)哟谓Y(jié)構(gòu)，有助于理解和分析網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和功能特性，具有重要的研究價值。早期對于社區(qū)檢測的研究主要關(guān)注網(wǎng)絡(luò)中非重疊社區(qū)結(jié)構(gòu)，即假設(shè)每個節(jié)點僅屬于單個社區(qū)，而在現(xiàn)實網(wǎng)絡(luò)中，往往存在一些節(jié)點同時屬于多個社區(qū)的情況，即社區(qū)間會存在交叉重疊現(xiàn)象而非彼此獨立，這類社區(qū)結(jié)構(gòu)被稱為重疊社區(qū)[2]。從網(wǎng)絡(luò)中檢測出重疊社區(qū)更具現(xiàn)實意義。

當(dāng)前針對重疊社區(qū)檢測問題提出的算法大致分為基于派系過濾的方法、基于線圖與邊分割的方法、基于局部擴展與優(yōu)化的方法、基于模糊檢測的方法和基于標(biāo)簽傳播的方法等[3]。隨著網(wǎng)絡(luò)數(shù)據(jù)規(guī)模的增長，近線性時間復(fù)雜度的標(biāo)簽傳播算法(Label Propagation Algorithm，LPA)[4]在社區(qū)檢測領(lǐng)域得到很大發(fā)展，Raghavan等[5]提出的RAK算法是首次將LPA算法應(yīng)用到社區(qū)檢測的方法，其基本思想：為每個節(jié)點設(shè)置一個唯一標(biāo)簽，節(jié)點的標(biāo)簽按照該節(jié)點的鄰居節(jié)點中標(biāo)簽頻率最高的標(biāo)簽進行更新，帶有相同標(biāo)簽的節(jié)點被劃分到同一社區(qū)。然而基于LPA的算法雖然簡單高效，但其隨機性造成檢測結(jié)果的不穩(wěn)定，也無法檢測到重疊社區(qū)結(jié)構(gòu)，為此提出了很多基于LPA的改進算法。Gregory[6]在LPA的基礎(chǔ)上提出基于標(biāo)簽傳播的重疊社區(qū)檢測算法(Community Overlap Propagation Algorithm，COPRA)，首次將標(biāo)簽傳播應(yīng)用到重疊社區(qū)檢測，該算法引入歸屬系數(shù)，允許每個節(jié)點保留多個標(biāo)簽實現(xiàn)重疊社區(qū)發(fā)現(xiàn)，但運行結(jié)果同樣存在隨機性的問題，并且需要預(yù)設(shè)節(jié)點所屬的最大社區(qū)數(shù)，該參數(shù)的選擇在真實未知的網(wǎng)絡(luò)中是很難把握的。劉世超等[7]基于COPRA算法改進了網(wǎng)絡(luò)的傳播特性，固定節(jié)點的更新順序提高算法的穩(wěn)定性，同時考慮節(jié)點屬性和歷史標(biāo)簽信息對傳播的影響，提高結(jié)果的準(zhǔn)確性，但仍要預(yù)設(shè)節(jié)點所屬的最大社區(qū)數(shù)；Xie等[8]提出的SLPA算法是基于Speaker-Listener的信息傳播過程。該算法隨機選擇一個節(jié)點作為Listener接收作為Speaker的鄰居發(fā)送的標(biāo)簽，算法根據(jù)成對交互規(guī)則在節(jié)點之間傳播標(biāo)簽。該算法會將歷史標(biāo)簽考慮在內(nèi)，為每個節(jié)點提供內(nèi)存存儲每輪迭代選擇的標(biāo)簽，最后對標(biāo)簽進行后處理輸出重疊社區(qū)。另外SLPA不需要預(yù)先設(shè)置社區(qū)數(shù)量，但在交互規(guī)則上仍然存在隨機性導(dǎo)致算法結(jié)果的不穩(wěn)定。趙雨露等[9]針對SLPA選擇Listener節(jié)點時的隨機性給所有節(jié)點排序更新標(biāo)簽來降低算法結(jié)果的不穩(wěn)定性，但忽略了節(jié)點自身屬性和歷史標(biāo)簽影響力會隨時間衰減的要素。

本文針對現(xiàn)有標(biāo)簽傳播算法存在的一些不足，提出一種新的重疊社區(qū)檢測算法SLPA-TD：計算節(jié)點的影響力，固定節(jié)點標(biāo)簽的更新順序，以此增強算法的穩(wěn)定性；設(shè)計新的標(biāo)簽傳播的Speaker-Listener規(guī)則，考慮節(jié)點標(biāo)簽的影響隨時間衰減，并結(jié)合節(jié)點屬性和鄰域結(jié)構(gòu)信息更新標(biāo)簽，進一步提高檢測結(jié)果的質(zhì)量。

1 算法相關(guān)描述

1.1 相關(guān)定義

定義1重疊度(Overlap Degree,OD)。網(wǎng)絡(luò)圖G=(V,E)，C={C1,C2,…,Ck}是網(wǎng)絡(luò)G中節(jié)點的一個劃分，每個集合Ci代表一個社區(qū)，社區(qū)Ci和Cj的節(jié)點數(shù)分別為|Ci|和|Cj|，則社區(qū)之間的重疊度定義如下：

(1)

若OD(Ci,Cj)=0，則社區(qū)Ci和Cj互不相交；若OD(Ci,Cj)=1，則社區(qū)Ci(Cj)包含于另一個社區(qū)Cj(Ci)之中；若0

定義2重疊社區(qū)。重疊社區(qū)的定義由上述重疊度進一步給出，當(dāng)0

定義3鄰域相似度(Neighborhood Similarity,NS)。

(2)

式中：Γ(X)為節(jié)點X及其鄰居節(jié)點的集合；K(X)為節(jié)點X的度。

定義4屬性相似度(Attribute Similarity,AS)。采用余弦相似度方法比較節(jié)點屬性值計算相似度，該過程與計算文本相似度類似。將節(jié)點的屬性進行詞頻向量化得到節(jié)點X和節(jié)點Y的屬性詞頻向量分別為A=(a1,a2,…,am)和B=(b1,b2,…,bm)，則節(jié)點X和節(jié)點Y的屬性相似度表示為：

(3)

定義5節(jié)點相似度(Similarity,S)。

(4)

節(jié)點間的鄰域相似度越高意味著這兩個節(jié)點共享的鄰居越多，節(jié)點在同一個社區(qū)的概率越大。同理，屬性相似度代表著節(jié)點之間的相關(guān)性，屬性相似度越高，表明兩節(jié)點在同一個社區(qū)的可能性越高[10]。

1.2 節(jié)點影響力排序

本文利用綜合考慮節(jié)點鄰居數(shù)和聚類系數(shù)影響的排序算法ClusterRank[11]計算節(jié)點的影響力，按此排序固定節(jié)點標(biāo)簽的更新順序，從而增強算法的穩(wěn)定性。該算法在有向和無向網(wǎng)絡(luò)都可使用。

本文采用無向版本，節(jié)點i的ClusterRank得分Si定義為：

(5)

f(ci)=10-ci

(6)

式中：ci為節(jié)點i的局部聚類系數(shù)，Γi為節(jié)點i的鄰居節(jié)點的集合，kj表示節(jié)點j的度數(shù)，f(ci)表明節(jié)點i的聚類系數(shù)對信息傳播的影響，由于局部聚類起負面作用，因此f(ci)與ci呈負相關(guān)[12]。

1.3 標(biāo)簽時間衰減

標(biāo)簽時間衰減表示節(jié)點歷史標(biāo)簽的重要性隨時間衰減，這里的隨時間衰減實際是指隨迭代次數(shù)的衰減?；跇?biāo)簽傳播的算法是在一次次的迭代中標(biāo)簽逐漸趨于收斂和穩(wěn)定的過程，也就是說迭代后期比迭代前期節(jié)點存儲的標(biāo)簽更有影響力，因此節(jié)點在最近一次迭代中保存的標(biāo)簽的重要性在該節(jié)點的當(dāng)前標(biāo)簽中是最大的，即節(jié)點歷史標(biāo)簽的重要性隨時間衰減。

本文受牛頓冷卻定律思想的啟發(fā)，即物體的冷卻速度與其當(dāng)前溫度與室溫之間的溫差成正比，將其中包含的指數(shù)衰減的思路應(yīng)用到歷史標(biāo)簽影響隨時間衰減的計算過程中進行標(biāo)簽選擇。

由牛頓冷卻定律的一階微分方程可以推導(dǎo)出溫度和時間的關(guān)系函數(shù)，由此得到溫度隨時間呈指數(shù)衰減的過程，即某溫度的下降速度和該溫度值成比例。將指數(shù)衰減擴展到一般化過程的數(shù)學(xué)公式為：

N(t)=N0·e-αt

(7)

式中：N(t)為某個量N在t時刻的數(shù)值，N0為N在0時刻的初始數(shù)值，即N開始指數(shù)衰減時的最初也是最大值，t為衰減時間，α為衰減常數(shù)，也就是N的衰減速率，通常根據(jù)實際情況自行選擇合適的數(shù)值。

回到本文的歷史標(biāo)簽重要性隨時間衰減問題，在標(biāo)簽更新過程中，每迭代一次，節(jié)點內(nèi)存就添加一個標(biāo)簽，內(nèi)存中的所有標(biāo)簽的重要性在整個迭代周期內(nèi)進行時間衰減，在這里用Score表示標(biāo)簽重要性(Score越大，標(biāo)簽越重要)，在每輪迭代中，計算節(jié)點內(nèi)存中的全部標(biāo)簽的Score，同一節(jié)點內(nèi)存中的相同標(biāo)簽的Score累加作為該標(biāo)簽當(dāng)前對于該節(jié)點的重要性，節(jié)點各標(biāo)簽的Score在迭代更新過程中進行標(biāo)簽選擇時會發(fā)揮作用。

Score=e-λ·Δt

(8)

式中：λ為衰減因子，這里取迭代周期T的倒數(shù)1/T，Δt為時間間隔，以迭代次數(shù)為單位，Δt=T+1-T′，T′為迭代次序。

下面舉例說明，為簡化計算過程，設(shè)迭代周期T為5次，λ為1/5，節(jié)點a內(nèi)存中的標(biāo)簽從第0次迭代(初始化)到第5次迭代依次為[a,b,c,b,d,c]，默認節(jié)點自身id作為初始化標(biāo)簽。

初始化：標(biāo)簽a的Score=e-0.2(5+1-0)≈0.301；內(nèi)存中的標(biāo)簽：(a，0.301)。

第1次迭代：標(biāo)簽b的Score=e-0.2(5+1-1)≈0.368；內(nèi)存中的標(biāo)簽：(a，0.301)，(b，0.368)。

第2次迭代：標(biāo)簽c的Score=e-0.2(5+1-2)≈0.449；內(nèi)存中的標(biāo)簽：(a，0.301)，(b，0.368)，(c，0.449)。

第3次迭代：標(biāo)簽b的Score=e-0.2(5+1-3)≈0.549；內(nèi)存中的標(biāo)簽：(a，0.301)，(b，0.368)，(c，0.449)，(b，0.549)。

第4次迭代：標(biāo)簽d的Score=e-0.2(5+1-4)≈0.670；內(nèi)存中的標(biāo)簽：(a，0.301)，(b，0.368)，(c，0.449)，(b，0.549)，(d，0.670)。

第5次迭代：標(biāo)簽c的Score=e-0.2(5+1-5)≈0.819；內(nèi)存中的標(biāo)簽：(a，0.301)，(b，0.368)，(c，0.449)，(b，0.549)，(d，0.670)，(c，0.819)。

上述過程使得節(jié)點歷史標(biāo)簽的重要性隨時間衰減，不再與最新標(biāo)簽等同，遵循標(biāo)簽重要性隨時間衰減的思想更加合理。

1.4 設(shè)計Speaker-Listener規(guī)則

Speaker-Listener規(guī)則是節(jié)點的標(biāo)簽傳播過程要遵循的規(guī)則，當(dāng)前要更新標(biāo)簽的節(jié)點為Listener，該節(jié)點的鄰居節(jié)點為Speaker。

Speaker-Listener規(guī)則分為Speaker規(guī)則和Listener規(guī)則兩部分。

1) Speaker規(guī)則為Speaker節(jié)點向Listener節(jié)點發(fā)送標(biāo)簽時遵循的傳播規(guī)則，即具體如何選擇自身內(nèi)存的標(biāo)簽進行傳播。本文提出的Speaker規(guī)則如下：

(1) 計算Speaker節(jié)點內(nèi)存中當(dāng)前各標(biāo)簽的Score，并將同一節(jié)點下相同標(biāo)簽的Score累加。

(2) Speaker節(jié)點選擇各自內(nèi)存中Score累計值最大的標(biāo)簽發(fā)送給Listener節(jié)點。

2) Listener規(guī)則為Listener節(jié)點從Speaker節(jié)點發(fā)送的眾多標(biāo)簽中選擇一個標(biāo)簽存儲到自身內(nèi)存所遵循的規(guī)則。本文提出的Listener規(guī)則如下：

(1) Listener節(jié)點將收到的標(biāo)簽中相同標(biāo)簽的Score分別累加，選擇Score最大的標(biāo)簽。

(2) 若Score最大的標(biāo)簽有多個可選，計算出Listener節(jié)點和各個發(fā)送最大Score標(biāo)簽的Speaker節(jié)點的節(jié)點相似度S，選擇與Listener節(jié)點的節(jié)點相似度最大的節(jié)點發(fā)送的標(biāo)簽。

先前大多數(shù)算法的Speaker規(guī)則都是在Speaker節(jié)點內(nèi)存中選擇出現(xiàn)頻率最高的標(biāo)簽發(fā)送給Listener節(jié)點，不但忽略了歷史標(biāo)簽的時間衰減影響，還很容易出現(xiàn)標(biāo)簽頻率相同而隨機選擇的狀況，考慮到時間衰減的影響后可以很好地避免這樣的情況發(fā)生。另外，加入了節(jié)點相似度的Listener規(guī)則進一步降低了算法在標(biāo)簽選擇過程的隨機性。

1.5 迭代次數(shù)和閾值

基于SLPA的算法一般采用固定迭代次數(shù)的方式結(jié)束算法，經(jīng)驗表明[8]，當(dāng)T>20時，算法的輸出相對穩(wěn)定，與網(wǎng)絡(luò)的大小與結(jié)構(gòu)無關(guān)。當(dāng)然，如果條件允許，適當(dāng)增加迭代次數(shù)更能保證輸出結(jié)果的穩(wěn)定。閾值r用來篩選算法結(jié)束后得到的節(jié)點內(nèi)存的標(biāo)簽，比較節(jié)點內(nèi)存各標(biāo)簽比重與閾值r，刪除比重小于閾值r的標(biāo)簽，帶有多個標(biāo)簽的節(jié)點即為重疊節(jié)點，表明該節(jié)點同時屬于多個社區(qū)。由于本文側(cè)重于重疊社區(qū)的檢測，閾值r的取值范圍設(shè)為[0,0.5]，當(dāng)r超過0.5時，該算法輸出非重疊社區(qū)。閾值r取值越小產(chǎn)生的社區(qū)數(shù)越多，可以根據(jù)實際情況進行調(diào)整。

1.6 SLPA-TD算法

SLPA-TD算法偽代碼如算法1所示。

算法1SLPA-TD

輸入: T, r

輸出: overlapping communities

1. Initialization:

2. for i=1:n

3. Nodes(i).memory[0]=i

4.Si=Nodes(i).clusterRank()

5. sortSiin descending order

6. Updating labels:

7. for t=1:T

8. for each node i in updating order

9. Listener=Nodes(i)

10. Speakers=Nodes(i).getNeibs()

11. LabelList={}

12. for j in Speakers

13. l=Speakers(j).speakerRule()

14. LabelList.addLabel(l)

15. label=Listener.listenerRule()

16. Nodes(i).memory[t]=label

17. Post-processing:

18. for i=1:n

19. remove labels in Nodes(i).memory with probability

20. Output overlapping communities

該算法共分為三個部分：節(jié)點初始化，為每個節(jié)點分配內(nèi)存儲存標(biāo)簽，用節(jié)點自身id作為初始化標(biāo)簽存入節(jié)點內(nèi)存，用ClusterRank算法計算節(jié)點影響力，由大到小作為節(jié)點標(biāo)簽更新順序；開始標(biāo)簽更新過程，直到達到最大迭代次數(shù)T：按更新順序選擇一個節(jié)點作為Listener，分配一個臨時內(nèi)存存放該節(jié)點在其鄰居節(jié)點(即Speaker)接收到的標(biāo)簽，每個Speaker節(jié)點按照Speaker規(guī)則在其內(nèi)存中選擇一個標(biāo)簽發(fā)送給Listener節(jié)點，Listener節(jié)點在接收的多個標(biāo)簽中按照Listener規(guī)則選擇一個標(biāo)簽存入自身內(nèi)存中；根據(jù)閾值r處理節(jié)點內(nèi)存中的標(biāo)簽，刪除小于閾值的標(biāo)簽，將具有相同標(biāo)簽的節(jié)點劃分到同一社區(qū)，輸出重疊社區(qū)。

1.7 算法時間復(fù)雜度

設(shè)網(wǎng)絡(luò)有n個節(jié)點和m條邊，迭代次數(shù)為T(用戶設(shè)置，本文T=50)：節(jié)點內(nèi)存的標(biāo)簽初始化需要O(n)；計算節(jié)點影響力和排序得到節(jié)點的標(biāo)簽更新順序需要O(nlogn)；標(biāo)簽傳播更新過程需要O(Tm)；處理標(biāo)簽和劃分社區(qū)需要O(Tn)；因此算法整體的時間復(fù)雜度為O(nlogn)。

2 實驗與評估

本文分別在基準(zhǔn)數(shù)據(jù)集和真實數(shù)據(jù)集上進行實驗，對于已知社區(qū)結(jié)構(gòu)的基準(zhǔn)網(wǎng)絡(luò)上的實驗，采用標(biāo)準(zhǔn)互信息(Normalized Mutual Information,NMI)作為評估指標(biāo)，而在真實數(shù)據(jù)集上的實驗使用擴展模塊度(Extended Modularity,EQ)來檢驗算法結(jié)果。選擇經(jīng)典的重疊社區(qū)檢測算法SLPA算法和基于SLPA的改進算法SLPA-CM與本文算法進行比較，驗證本文算法的有效性和準(zhǔn)確性。

本文的實驗配置為Windows 7操作系統(tǒng)、Intel(R) Core(TM) i5- 4590 3.30 GHz處理器和8.00 GB內(nèi)存，所有的算法都由Python實現(xiàn)。

2.1 評估指標(biāo)

(1) 標(biāo)準(zhǔn)互信息(NMI)。標(biāo)準(zhǔn)互信息是適用于已知網(wǎng)絡(luò)社區(qū)真實結(jié)構(gòu)的經(jīng)典評估指標(biāo)，是由Lancichinetti等[14]基于先前非重疊指標(biāo)NMI[13]提出的用于衡量重疊社區(qū)檢測結(jié)果的擴展NMI，該指標(biāo)實際是在比較檢測結(jié)果和真實結(jié)構(gòu)的相似度。NMI值介于0到1之間，值越大表示檢測結(jié)果和真實結(jié)構(gòu)越接近。

(9)

式中：X、Y分別代表用于比較的兩種劃分C1和C2，H(X|Y)norm為X相對于Y的標(biāo)準(zhǔn)化條件熵。

(2) 擴展模塊度(EQ)。對于網(wǎng)絡(luò)結(jié)構(gòu)未知的真實數(shù)據(jù)集，本文采用Shen等[15]提出的擴展模塊度EQ進行評價，EQ是模塊度Q[16]的擴展，是常用的用于網(wǎng)絡(luò)結(jié)構(gòu)未知的重疊社區(qū)檢測的評估指標(biāo)。EQ值范圍為[0,1]，EQ值越大表明社區(qū)劃分質(zhì)量越好。當(dāng)網(wǎng)絡(luò)中無重疊時，EQ退化為Q。

(10)

2.2 基準(zhǔn)數(shù)據(jù)集實驗

表1 兩種基準(zhǔn)網(wǎng)絡(luò)LFR1和LFR2的主要參數(shù)

本文比較的3個算法SLPA、SLPA-CM、SLPA-TD的參數(shù)設(shè)置：T=50，r=(0.05,0.5)，其中對于參數(shù)r取值不確定的情況，每次增加0.05，選擇使得NMI值取最大的數(shù)值作為參數(shù)r的取值；SLPA-CM控制最大社區(qū)節(jié)點數(shù)的參數(shù)按文獻[9]設(shè)置Maxc=0.4n。

圖1和圖2為各算法的NMI值分別在網(wǎng)絡(luò)的On=10%和On=50%的情況下隨Om變化的對比圖。各NMI值為3個算法運行20次的平均值。

圖1 On =10%時的NMI值

圖2 On =50%時的NMI值

如圖1和圖2所示，當(dāng)On從10%變?yōu)?0%時各算法的NMI值呈顯著下降趨勢，并且無論是在網(wǎng)絡(luò)的On=10%還是On=50%的情況下，3個算法的NMI值都隨Om的增加而降低，這說明隨著網(wǎng)絡(luò)重疊節(jié)點數(shù)量的增加和重疊程度的加深，社區(qū)檢測的難度也加大了。總體看來，本文算法下的NMI值始終高于SLPA算法和SLPA-CM算法，其在Om各個取值下的NMI表現(xiàn)與SLPA算法和SLPA-CM算法比較平均提高了15%和10%，驗證了本文算法的有效性，同時表明考慮到歷史標(biāo)簽影響力隨時間衰減的該算法能夠進一步提高檢測結(jié)果的質(zhì)量。

2.3 真實數(shù)據(jù)集實驗

本文選取了5個不同規(guī)模的真實數(shù)據(jù)集進行實驗，表2為各個數(shù)據(jù)集的基本信息。

表2 真實數(shù)據(jù)集基本信息

本文所有實驗均是在無向網(wǎng)絡(luò)中進行，個別算法要求數(shù)據(jù)集節(jié)點帶有屬性，故以上為處理后的數(shù)據(jù)集，其中一些數(shù)據(jù)集的節(jié)點屬性信息無法獲取，當(dāng)需要計算節(jié)點相似度時只考慮其結(jié)構(gòu)相似度。

圖3為各個算法在5個真實網(wǎng)絡(luò)上劃分重疊社區(qū)得到的EM值，各算法的參數(shù)設(shè)置同基準(zhǔn)網(wǎng)絡(luò)實驗時一樣，EM值為各算法運行20次的平均值。從圖中可以看到SLPA-TD算法的劃分結(jié)果最好，其EM值始終高于其他兩個算法，平均提高了17%和9%。尤其是在帶有節(jié)點屬性的兩個數(shù)據(jù)集上的表現(xiàn)，考慮了節(jié)點相似度的SLPA-TD算法的優(yōu)勢更加明顯。

圖3 真實網(wǎng)絡(luò)劃分結(jié)果的EM值

3 結(jié) 語

本文基于標(biāo)簽傳播的思想，針對現(xiàn)有標(biāo)簽傳播算法存在的一些不足進行改進，提出一種新的重疊社區(qū)檢測算法SLPA-TD，計算節(jié)點的影響力固定節(jié)點標(biāo)簽的更新順序，設(shè)計新的節(jié)點標(biāo)簽的傳播規(guī)則，考慮節(jié)點歷史標(biāo)簽隨時間衰減的影響，結(jié)合節(jié)點相似度更新標(biāo)簽。實驗驗證了本文算法的有效性，與之前算法相比，不僅大大降低結(jié)果的隨機性，還提高了社區(qū)劃分的質(zhì)量，尤其是在具有節(jié)點屬性信息的網(wǎng)絡(luò)上。但這些僅是該算法在靜態(tài)網(wǎng)絡(luò)中的表現(xiàn)，未來工作會考慮將該算法應(yīng)用到動態(tài)網(wǎng)絡(luò)上。