基于標簽傳播的重疊社區檢測算法

陳 旭 張 俊 曲賢菲 田朝霞

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

0 引 言

現實世界中包括社會科學、生物信息、計算機等許多領域的網絡都可以用復雜網絡來表示，社區結構是復雜網絡的重要特性[1]，揭示網絡中存在的社區結構有利于從網絡中挖掘出有實際意義的模塊或層次結構，有助于理解和分析網絡的拓撲結構和功能特性，具有重要的研究價值。早期對于社區檢測的研究主要關注網絡中非重疊社區結構，即假設每個節點僅屬于單個社區，而在現實網絡中，往往存在一些節點同時屬于多個社區的情況，即社區間會存在交叉重疊現象而非彼此獨立，這類社區結構被稱為重疊社區[2]。從網絡中檢測出重疊社區更具現實意義。

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

本文針對現有標簽傳播算法存在的一些不足，提出一種新的重疊社區檢測算法SLPA-TD：計算節點的影響力，固定節點標簽的更新順序，以此增強算法的穩定性；設計新的標簽傳播的Speaker-Listener規則，考慮節點標簽的影響隨時間衰減，并結合節點屬性和鄰域結構信息更新標簽，進一步提高檢測結果的質量。

1 算法相關描述

1.1 相關定義

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

(1)

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

定義2重疊社區。重疊社區的定義由上述重疊度進一步給出，當0

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

(2)

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

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

(3)

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

(4)

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

1.2 節點影響力排序

本文利用綜合考慮節點鄰居數和聚類系數影響的排序算法ClusterRank[11]計算節點的影響力，按此排序固定節點標簽的更新順序，從而增強算法的穩定性。該算法在有向和無向網絡都可使用。

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

(5)

f(ci)=10-ci

(6)

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

1.3 標簽時間衰減

標簽時間衰減表示節點歷史標簽的重要性隨時間衰減，這里的隨時間衰減實際是指隨迭代次數的衰減?；跇撕瀭鞑サ乃惴ㄊ窃谝淮未蔚牡袠撕炛饾u趨于收斂和穩定的過程，也就是說迭代后期比迭代前期節點存儲的標簽更有影響力，因此節點在最近一次迭代中保存的標簽的重要性在該節點的當前標簽中是最大的，即節點歷史標簽的重要性隨時間衰減。

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

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

N(t)=N0·e-αt

(7)

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

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

Score=e-λ·Δt

(8)

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

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

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

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

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

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

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

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

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

1.4 設計Speaker-Listener規則

Speaker-Listener規則是節點的標簽傳播過程要遵循的規則，當前要更新標簽的節點為Listener，該節點的鄰居節點為Speaker。

Speaker-Listener規則分為Speaker規則和Listener規則兩部分。

1) Speaker規則為Speaker節點向Listener節點發送標簽時遵循的傳播規則，即具體如何選擇自身內存的標簽進行傳播。本文提出的Speaker規則如下：

(1) 計算Speaker節點內存中當前各標簽的Score，并將同一節點下相同標簽的Score累加。

(2) Speaker節點選擇各自內存中Score累計值最大的標簽發送給Listener節點。

2) Listener規則為Listener節點從Speaker節點發送的眾多標簽中選擇一個標簽存儲到自身內存所遵循的規則。本文提出的Listener規則如下：

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

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

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

1.5 迭代次數和閾值

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

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

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

1.7 算法時間復雜度

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

2 實驗與評估

本文分別在基準數據集和真實數據集上進行實驗，對于已知社區結構的基準網絡上的實驗，采用標準互信息(Normalized Mutual Information,NMI)作為評估指標，而在真實數據集上的實驗使用擴展模塊度(Extended Modularity,EQ)來檢驗算法結果。選擇經典的重疊社區檢測算法SLPA算法和基于SLPA的改進算法SLPA-CM與本文算法進行比較，驗證本文算法的有效性和準確性。

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

2.1 評估指標

(1) 標準互信息(NMI)。標準互信息是適用于已知網絡社區真實結構的經典評估指標，是由Lancichinetti等[14]基于先前非重疊指標NMI[13]提出的用于衡量重疊社區檢測結果的擴展NMI，該指標實際是在比較檢測結果和真實結構的相似度。NMI值介于0到1之間，值越大表示檢測結果和真實結構越接近。

(9)

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

(2) 擴展模塊度(EQ)。對于網絡結構未知的真實數據集，本文采用Shen等[15]提出的擴展模塊度EQ進行評價，EQ是模塊度Q[16]的擴展，是常用的用于網絡結構未知的重疊社區檢測的評估指標。EQ值范圍為[0,1]，EQ值越大表明社區劃分質量越好。當網絡中無重疊時，EQ退化為Q。

(10)

2.2 基準數據集實驗

表1 兩種基準網絡LFR1和LFR2的主要參數

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

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

圖1 On =10%時的NMI值

圖2 On =50%時的NMI值

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

2.3 真實數據集實驗

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

表2 真實數據集基本信息

本文所有實驗均是在無向網絡中進行，個別算法要求數據集節點帶有屬性，故以上為處理后的數據集，其中一些數據集的節點屬性信息無法獲取，當需要計算節點相似度時只考慮其結構相似度。

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

圖3 真實網絡劃分結果的EM值

3 結 語

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