二分網絡中基于增強動態距離模型的社團檢測算法

蘇思行，陳碧連，曹浪財

(廈門大學航空航天學院，廈門市大數據智能分析與決策重點實驗室，福建廈門361005)

現實生活中真實網絡的一個基本組成部分是它們的底層社團[1].通常，一個社團被認為是內部緊密相連的一組節點，而不同社團之間的外部鏈接是稀疏連接的.一個網絡可能包含多個社團，社團檢測任務旨在網絡中找到所有這些社團，也稱為圖聚類[2].

當前，許多研究主要集中在只包含一種節點類型的單模網絡上.人們提出了許多方法來應對不同假設下識別單模網絡的情況，如非負矩陣分解[3]、標簽傳播[4]和模塊度優化[5]等.然而，真實世界的網絡通常包含多種類型的節點，最簡單的情況是包含兩種不同類型節點的二分網絡[6].投影方法是一個簡單的解決方法，即將二分網絡轉換為單模網絡，然后使用現有的社團檢測方法[7].因為只有一種類型的節點被應用，而另一種類型的節點在投影后丟失，投影方法可能會導致信息不完整的問題[8]，所以，學者開發了各種方法來在社團劃分之后維護兩種類型的節點.Barber[6]首先提出了一個二分模塊度，然后開發了BRIM模型，將節點的兩個獨立部分歸納為模結構.但是，因為高模塊度分數不能準確地檢測到小社團，二分網絡的模塊度在分辨率問題[9]上存在局限性.于是，Sun等[10]將單模網絡中的傳統動態距離模型Attractor[11]擴展到二分網絡中，提出二分網絡的傳統動態距離模型BiAttractor，能夠準確地檢測到小社團.但是，BiAttractor的敏感參數λ的微小變化可能會導致由此產生的群落結構的巨大差異，使得模型的魯棒性差.

為了解決這個問題，本文提出一種新的局部非對稱邊緣聚類系數(local asymmetric edge clustering coefficient，LAECC)，將自我中心(Ego-Leader)[12]從單模網絡擴展到二分網絡，計算專屬鄰居節點對距離的影響，以此用來擺脫敏感參數λ.在此基礎上，基于Ego-Leader，本文在二分網絡中設計了一個增強的動態距離模型E-BiAttractor，并提出了相應的社團檢測算法.與傳統動態距離模型相比，E-BiAttractor模型具有更好的性能和魯棒性.

1 背景知識

在本節中，首先介紹本文會用到的二分網絡符號定義.而后，介紹一種能夠在二分網絡中檢測社團的傳統動態距離模型BiAttractor[10].

1.1 符號定義

設G=(U,V,E)是一個無向無權的二分圖，其中U和V代表兩組不同類型的節點.在二分網絡中，同一類型(U或V)的節點之間沒有邊連接.

定義1(節點u的鄰居節點集合)節點u的鄰居節點集合N(u)表示如下：

N(u)={v|u∈U,v∈V,(u,v)∈E}.

定義2(節點u的二階鄰居節點集合)節點u的二階鄰居節點集合NN(u)表示如下：

NN(u)={y|x∈N(u),y∈N(x),u∈U,x∈

V,y∈U,u≠y}.

定義3(專屬鄰居節點集合)對于邊e(u,v)而言，節點u的專屬鄰居節點集合定義為NE(u)=N(u)-{v}.

定義4(Jaccard距離)使用流行的Jaccard距離[13]來量化兩個同類型節點u和節點x之間的距離，定義如下：

(1)

定義5(局部Jaccard距離)由于二分網絡的性質[10]，不同類型節點之間沒有公共鄰居， Sun等[10]提出能夠計算二分網絡中直接相連的不同類型節點之間距離的局部Jaccard距離，定義如下：

(2)

1.2 二分網絡中的傳統動態距離模型

Sun等[10]提出一種能夠在二分網絡中檢測社團的傳統動態距離模型BiAttractor，它通過檢查節點之間距離的變化(即動態距離)，來發現二分網絡中的社團.其基本思想是每個節點與其鄰居節點交互，最終形成穩定分布，即同一社團的節點彼此靠近，不同社團的節點彼此遠離.

BiAttractor有兩種不同的交互模式，包括直接連接節點對距離的影響和專屬鄰居節點對距離的影響.

模式1：直接連接節點的影響.

在動態交互過程中，直接連接節點的影響ID(u,v)使節點u和節點v之間的距離減小，定義如下：

ID(u,v)=

(3)

其中，f(·)是一個耦合函數，可用正弦函數sin(·)來計算[10]，deg(u)表示節點u的度數.

模式2：專屬鄰居節點的影響.

在動態交互過程中，每個專屬鄰居節點會吸引與它相連的節點(節點u或節點v)向自身移動.通過引入一個參數λ來判斷節點u的專屬鄰居節點x會對節點u和節點v之間的距離產生積極影響還是消極影響.定義如下：

ρ(x,u)=

(4)

在上式中，ρ(x,u)表示節點u的專屬鄰居集NE(u)里的節點x將會對距離d(u,v)產生積極影響還是消極影響，參數λ的取值推薦為[0.2,0.8][11].

專屬鄰居節點的影響IE(u,v)的定義如下：

(5)

最后，節點u和節點v之間的距離d(u,v)隨時間的變化如下所示：

2 二分網絡中的增強動態距離模型

2.1 局部非對稱邊緣聚類系數

Cai等[12]在單模網絡中提出非對稱邊緣聚類系數(asymmetric edge clustering coefficient，AECC).對于連接節點u和節點v的邊e(u,v),AECC定義為：

為了將AECC從單模網絡擴展到二分網絡，本文提出LAECC.直接相連的節點u對節點v的LAECC定義為：

(6)

其中，N(x)表示節點x的鄰居節點集合，NE(u)表示節點u的專屬鄰居節點集合.CLAECC(u,v)首先計算NE(u)里每個節點對節點v的CAECC之和，再除以節點u的專屬鄰居節點個數|NE(u)|.需要注意的是，節點u對節點v的CLAECC不等于節點v對節點u的CLAECC，即CLAECC(u,v)≠CLAECC(v,u).

2.2 Ego-Leader和它的特征

一個節點的Ego-Leader由一個或多個LAECC最大的鄰居節點組成，任何一個節點的Ego-Leader包含的節點數永遠不會超過該節點的鄰居數.從節點的鄰居集合中選擇具有最大LAECC的節點來形成它的Ego-Leader，當多個鄰居節點對該節點具有相同的最大LAECC時，這幾個鄰居節點都會被選取.因此，本文利用LAECC來尋找二分網絡中任意節點的Ego-Leader.

判斷節點u的專屬鄰居節點x對節點u和節點v之間距離的影響時，本質是判斷節點x和節點v是否相似[11].Cai等[12]提出，當節點u的專屬鄰居節點x和節點v的Ego-Leader有共同節點時，認為節點x和節點v是相似的.

因此，若節點x和節點v的Ego-Leader有共同節點，則節點x作為節點u的專屬鄰居節點，會對節點u和節點v的距離d(u,v)產生積極影響，使得節點u和節點v的距離在交互過程中減小.相反，若節點x和節點v的Ego-Leader沒有共同節點，則節點x作為節點u的專屬鄰居節點，會對節點u和節點v的距離d(u,v)產生消極影響，使得節點u和v的距離在交互過程中增大.

除此之外，Ego-Leader還具有以下重要特征：

1) Ego-Leader是不對稱的.節點u在節點v的Ego-Leader中，不代表節點v也在節點u的Ego-Leader中.

2) Ego-Leader是局部和靜態的.一個節點的Ego-Leader由其鄰域集合中LAECC值最大的節點組成.也就是說，任何Ego-Leader都只適用于一個節點，它的活動范圍是該節點的鄰居節點集合.因此，Ego-Leader強烈依賴于網絡拓撲結構.因為網絡拓撲結構是靜態的，所以節點的Ego-Leader也是靜態的，不會發生任何變化[14].

2.3 交互模式

E-BiAttractor和BiAttractor一樣，只討論兩種交互模式，直接連接節點對距離的影響和專屬鄰居節點對距離的影響.

模式3直接連接節點的影響.

與BiAttractor的模式1相同.由式(3)可知，在動態交互過程中，因為節點u和節點v是相連的，所以節點u和節點v會相互靠近，直接連接節點的影響ID(u,v)使節點u和節點v之間的距離減小.

模式4專屬鄰居節點的影響.

為了提高模型的魯棒性，同時說明專屬鄰居節點對距離產生的是積極影響還是消極影響，本文利用能夠應用于二分網絡的LAECC，計算每個節點的Ego-Leader，來代替內聚參數λ.對于e(u,v),節點x屬于節點u的專屬鄰居節點集合NE(u),通過判斷節點x的Ego-Leader和節點v的Ego-Leader是否有重疊部分，以此來判斷節點x和節點v是否相似.定義如下：

σ(x,u)=

(7)

其中，Ego(x)表示節點x的最高LAECC的鄰居節點集合.函數σ(x,u)不僅表示了節點u的專屬鄰居節點x對距離的影響方向(積極或消極)，而且還表示了這種影響的強度.如果節點u的專屬鄰居節點x與節點v的Ego-Leader有公共節點，那么節點u到它的專屬鄰居節點x的移動會導致d(u,v)的減小，即節點u的專屬鄰居節點x對距離會產生積極影響；相反，如果節點u的專屬鄰居節點x與節點v的Ego-Leader沒有公共節點，那么節點u到它的專屬鄰居節點x的移動會導致d(u,v)的增加，即節點u的專屬鄰居節點x對距離會產生消極影響.

結合函數σ(x,u),專屬鄰居節點對距離的影響IE定義如下：

(8)

最后，綜合考慮這兩種交互模式，節點u和節點v之間的距離d(u,v)隨時間的變化如下所示：

(9)

2.4 算法流程

基于E-BiAttractor的社團檢測算法流程如下所示：

算法：基于E-BiAttractor的社團檢測算法

輸入：無向無權的二分圖G=(U,V,E).

輸出：二分圖G的k個社團C1,C2,…,Ck.

1) 開始時間(t=0)，對于每條邊e(u,v)∈E,利用式(2)計算每條邊的初始距離.同時，利用式(6)計算每條邊的兩個LAECC，最后得到每個節點的Ego-Leader.

2) 對于每條邊e(u,v)∈E,如果t時刻e(u,v)的距離dt(u,v)大于0且小于1，則利用式(3),(7),(8),(9)計算出t+1時刻e(u,v)的新距離dt+1(u,v)；如果t時刻e(u,v)的距離dt(u,v)小于0或大于1，則這條邊達到收斂，跳過這條邊.

3) 重復步驟2)直到所有邊都收斂.

4) 刪除距離大于1的邊，檢測出網絡的群落結構，得到社團C1,C2,…,Ck.

2.5 時間復雜性

算法的時間復雜度分為三部分.首先，計算每條邊的初始距離，時間復雜度為O(|E|),其中|E|為邊數.而后，計算每個節點的Ego-Leader，時間復雜度為O(2·|E|).最后，每次交互的時間復雜度是O(N·|E|),其中N是兩個相連節點的專屬鄰居節點的平均數，動態交互過程的時間復雜度為O(T·N·|E|),T表示時間步長.因此，算法的時間復雜度為O(T·N·|E|).

3 實驗結果及分析

本節首先介紹實驗準備(數據集、對比算法和評價指標)，而后將基于E-BiAttractor模型的社團檢測算法與另外3種算法在8個公開數據集上進行對比實驗，通過對實驗結果的分析，驗證基于E-BiAttractor模型的社團檢測算法的有效性.

3.1 實驗準備

3.1.1 數據集介紹

在對比實驗中，本文使用http:∥konect.cc/networks/上的8個常見的無標簽公開數據集，這8個公開數據集的節點數、邊數以及節點的平均度在表1中詳細給出.

表1 數據集的簡要信息

3.1.2 對比算法介紹

為了對基于E-BiAttractor模型的社團檢測算法的性能有個客觀認識，將它與基于BiAttractor的社團檢測算法[10]、基于Adaptive Brim的社團檢測算法[6]和基于LP Brim的社團檢測算法[15]這3種算法進行比較.實驗中，將BiAttractor需要用到的參數λ設為0.8.

3.1.3 評價指標介紹

因為所有網絡都是無標簽的，本文采用模塊度(modularity)[16]來衡量檢測出來的社團質量.其定義為：

(10)

其中：m表示網絡中的邊數；A是網絡的鄰接矩陣，如果節點i和節點j之間有邊，則Ai,j=1,否則Ai,j=0；deg(i)表示節點i的度數；ci表示節點i所處的社團，如果節點i和節點j被分配到同一個社團，則δ(ci,cj)=1,否則δ(ci,cj)=0.該指標的范圍在0到1之間，值越大，說明社團檢測算法的性能越好.

3.2 實驗結果分析

表2描述的是各個模型在各個數據集上的模塊度表現情況.實驗結果中的評價指標用粗體表示最好的結果，下劃線表示次好的結果.從表2中可以得到如下結論：

1) E-BiAttractor在這8個數據集中，有5個數據集(Nahwiki、Zawiki、Towiki、Cvwiki、Crime)取得最好的結果，有兩個數據集(Fywiki、Iawiki)取得次好的結果，說明E-BiAttractor較之其他3種算法，能夠更有效的區分社團；

2) 在這8個數據集中，E-BiAttractor都取得了比BiAttractor更好的結果，而且E-BiAttractor不需要修改參數，說明通過引入Ego-Leader，E-BiAttractor較之BiAttractor具有更好的魯棒性.

綜上所述，本文提出的E-BiAttractor通過LAECC尋找出各節點正確的Ego-Leader，借此來判斷兩個節點是否相似，使得E-BiAttractor免于調參，并適用于絕大部分網絡，具有更好的魯棒性，因此在區分社團上有更優異的表現.

表2 各算法的模塊度比較

4 結 論

動態距離模型是一種成熟的社團檢測方法，可以有效地區分社團，進而實現社團內部緊密連接、社團之間稀疏連接的目的.二分網絡中的社團檢測算法相比于單模網絡中的社團檢測算法更加富有挑戰性.

本文提出一種在二分網絡中基于Ego-Leader進行社團檢測的增強動態距離模型E-BiAttractor，它利用LEACC得到Ego-Leader，通過分析節點間的Ego-Leader，來提升動態距離模型在二分網絡中的魯棒性和有效性.在8個數據集中進行對比實驗，實驗結果表明，本文提出的算法與其他3種社團檢測算法相比，模塊度都有一定程度的提升，模型具有更高的精度，且沒有參數，具有很高的魯棒性.