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

蘇思行，陳碧連，曹浪財

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

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

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

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

1 背景知識

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

1.1 符號定義

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

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

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

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

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

V,y∈U,u≠y}.

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

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

(1)

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

(2)

1.2 二分網絡中的傳統(tǒng)動態(tài)距離模型

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

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

模式1：直接連接節(jié)點的影響.

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

ID(u,v)=

(3)

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

模式2：專屬鄰居節(jié)點的影響.

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

ρ(x,u)=

(4)

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

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

(5)

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

2 二分網絡中的增強動態(tài)距離模型

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

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

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

(6)

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

2.2 Ego-Leader和它的特征

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

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

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

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

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

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

2.3 交互模式

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

模式3直接連接節(jié)點的影響.

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

模式4專屬鄰居節(jié)點的影響.

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

σ(x,u)=

(7)

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

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

(8)

最后，綜合考慮這兩種交互模式，節(jié)點u和節(jié)點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，最后得到每個節(jié)點的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|為邊數.而后，計算每個節(jié)點的Ego-Leader，時間復雜度為O(2·|E|).最后，每次交互的時間復雜度是O(N·|E|),其中N是兩個相連節(jié)點的專屬鄰居節(jié)點的平均數，動態(tài)交互過程的時間復雜度為O(T·N·|E|),T表示時間步長.因此，算法的時間復雜度為O(T·N·|E|).

3 實驗結果及分析

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

3.1 實驗準備

3.1.1 數據集介紹

在對比實驗中，本文使用http:∥konect.cc/networks/上的8個常見的無標簽公開數據集，這8個公開數據集的節(jié)點數、邊數以及節(jié)點的平均度在表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是網絡的鄰接矩陣，如果節(jié)點i和節(jié)點j之間有邊，則Ai,j=1,否則Ai,j=0；deg(i)表示節(jié)點i的度數；ci表示節(jié)點i所處的社團，如果節(jié)點i和節(jié)點j被分配到同一個社團，則δ(ci,cj)=1,否則δ(ci,cj)=0.該指標的范圍在0到1之間，值越大，說明社團檢測算法的性能越好.

3.2 實驗結果分析

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

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

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

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

表2 各算法的模塊度比較

4 結 論

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

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