基于鏈路變化的增量式動態(tài)網(wǎng)絡(luò)社團檢測模型

馮 健，陳少劍，付立東，史丹丹

(1.西安科技大學 計算機科學與技術(shù)學院，陜西 西安 710054；2.成都天軟信息技術(shù)有限公司 寬頻通信開發(fā)中心，四川 成都 610041)

0 引 言

復(fù)雜網(wǎng)絡(luò)指將自然界中存在的大量復(fù)雜系統(tǒng)抽象為由節(jié)點和邊形成的網(wǎng)絡(luò)。大量研究表明，結(jié)構(gòu)性和動態(tài)性是復(fù)雜網(wǎng)絡(luò)的本質(zhì)特性。結(jié)構(gòu)性體現(xiàn)為社團，是指復(fù)雜網(wǎng)絡(luò)中的節(jié)點呈現(xiàn)出以簇為特征的聚集狀態(tài)，簇內(nèi)節(jié)點聯(lián)系緊密，簇間節(jié)點聯(lián)系松散。動態(tài)性則指節(jié)點會持續(xù)地加入和離開網(wǎng)絡(luò)，并且節(jié)點間鏈接的強度在不斷變化，導(dǎo)致網(wǎng)絡(luò)中的社團結(jié)構(gòu)也隨時間發(fā)生演化[1]。檢測隨時間演化的動態(tài)社團結(jié)構(gòu)有助于揭示網(wǎng)絡(luò)的組織原則和功能特性，理解網(wǎng)絡(luò)演化的動力學過程，具有十分重要的理論和應(yīng)用價值。

演化聚類法是動態(tài)網(wǎng)絡(luò)社團檢測的兩種主要研究方法之一，總體思想是以歷史時刻網(wǎng)絡(luò)社團劃分為基礎(chǔ)，根據(jù)當前時刻網(wǎng)絡(luò)的變化進行社團結(jié)構(gòu)的調(diào)整。目前存在的主要問題包括：初始社團劃分不精確，以及隨時間推進或社團突變導(dǎo)致的累計誤差。

為了解決這些問題，提出了一個改進的增量式動態(tài)網(wǎng)絡(luò)社團結(jié)構(gòu)檢測模型LID(link increment based dynamic community detection method)。該模型除初始時刻、社團結(jié)構(gòu)劇烈變化的時刻以及累積誤差超過一定范圍的時刻對全部節(jié)點進行計算外，其它時刻充分利用已知的社團劃分結(jié)果進行補充計算，降低了算法的總體復(fù)雜度；同時有效解決了緊鄰時刻社團結(jié)構(gòu)劇烈變化的問題和累積誤差的問題，對社團結(jié)構(gòu)的變化具有較高的敏銳性。

1 相關(guān)研究

復(fù)雜網(wǎng)絡(luò)中社團檢測的研究起源于社會學的研究工作者Newman和Girvan等對靜態(tài)社團的檢測。最經(jīng)典的算法是Newman等提出的基于分裂的GN算法，其基本思想是不斷地找到介數(shù)中心性最大的邊，通過將其刪除來形成社團[2]；Newman等提出的快速算法FN通過計算社團的模塊度增量進行社團結(jié)構(gòu)劃分[2]。其它有代表性的方法包括譜聚類算法[3]、層次聚類算法[4]等，已形成較為成熟的理論體系。

國內(nèi)外獲取動態(tài)網(wǎng)絡(luò)社團結(jié)構(gòu)的算法可分為兩大類：獨立聚類法和演化聚類法。兩類算法都將要分析的網(wǎng)絡(luò)按時間分段，且都以每個時間片段為單位展開研究。早期的獨立聚類法通常利用靜態(tài)社團發(fā)現(xiàn)算法得到各個孤立網(wǎng)絡(luò)快照的社團結(jié)構(gòu)，然后在相鄰時間片段間探索社團之間的變化。如Wang等對每個時間片段的網(wǎng)絡(luò)進行矩陣分解得到社團結(jié)構(gòu)[5]，Yu等根據(jù)三方?jīng)Q策理論發(fā)現(xiàn)重疊社團[6]。在這些研究中，社團檢測和社團演化分別在兩個階段進行，每個時刻單獨進行的社團劃分增加了冗余計算量，且忽略了不同時刻的影響關(guān)系。演化聚類法又分為進化式聚類和增量式聚類。進化聚類基于動態(tài)網(wǎng)絡(luò)變化緩慢的基本特征，在對每個時刻的網(wǎng)絡(luò)進行聚類時，既要使聚類結(jié)果與當前時刻網(wǎng)絡(luò)的靜態(tài)快照盡量一致，又要與歷史時刻的網(wǎng)絡(luò)結(jié)構(gòu)差異較小。例如，F(xiàn)acetnet在獲得初始社團結(jié)構(gòu)后通過非負矩陣分解結(jié)構(gòu)對其進行演化[7]，文獻[8]提出一種映射的方法定位成員和社團的關(guān)系，Li等則解決了多目標演化的問題[9]；而增量聚類通常在前一時刻網(wǎng)絡(luò)的社團結(jié)構(gòu)上，基于當前時刻網(wǎng)絡(luò)的變化更新社團結(jié)構(gòu)。例如，Sun等通過濾除不變子圖提高社團檢測的效率[10]；此外，還有其它研究將經(jīng)典算法改進為增量聚類方法，如OLCPM通過局部社團更新檢測重疊社團[11]；DSBM算法首先通過隨機塊模型生成初始社區(qū)劃分，然后通過節(jié)點在每個時刻的期望值，利用貝葉斯方法調(diào)整節(jié)點的社團歸屬[12]。這類方法采用動態(tài)更新策略，能充分利用前次檢測的結(jié)果，因此運算效率較高；但隨著時間的推移，由于累積效應(yīng)使得聚類精度降低。另外，演化聚類算法大都需要人為設(shè)定社團數(shù)目，且假設(shè)社團數(shù)目在演化過程中不發(fā)生變化，這限制了算法的應(yīng)用和推廣。

綜上，針對現(xiàn)有動態(tài)社團檢測方法存在的問題，擬尋找一種高效的演化聚類社團檢測算法，在保證聚類精度的同時，既能夠滿足社會網(wǎng)絡(luò)在演化過程中變化較平穩(wěn)的特性，又能夠及時發(fā)現(xiàn)演化過程中出現(xiàn)的突發(fā)事件。

2 問題描述

動態(tài)社團發(fā)現(xiàn)所研究的對象是動態(tài)網(wǎng)絡(luò)。動態(tài)網(wǎng)絡(luò)G={G1,G2,…,GTOTAL} 是由TOTAL個時刻的網(wǎng)絡(luò)組成的序列。表1給出了基本符號及其定義。

表1 基本符號

全文中 |x| 表示取x的個數(shù)，如 |CRt| 表示t時刻Gt劃分出的社團個數(shù)。

3 LID

3.1 總體思想

本文設(shè)計的動態(tài)網(wǎng)絡(luò)社團檢測模型主要包含靜態(tài)社團檢測和動態(tài)社團檢測兩個算法，其中靜態(tài)社團檢測采用GN算法。具體步驟如下：

(1)利用GN算法檢測t=1時網(wǎng)絡(luò)Gt的靜態(tài)網(wǎng)絡(luò)社團結(jié)構(gòu)，獲取初始的社團集合CR1。

(2)對t>1時刻的網(wǎng)絡(luò)Gt， 如果相對于t-1時刻的網(wǎng)絡(luò)發(fā)生了突變，則通過GN算法得到當前時刻的社團集合CRt； 否則，根據(jù)相鄰時刻之間網(wǎng)絡(luò)的增量相關(guān)節(jié)點及變化鏈路，通過動態(tài)社團檢測算法對網(wǎng)絡(luò)社團進行局部調(diào)整得到CRt； 判定動態(tài)社團檢測算法劃分結(jié)果的穩(wěn)定性，若累積誤差過大，則利用GN算法重新進行社團劃分；記錄該時刻的CRt。

3.2 LID模型設(shè)計

LID的出發(fā)點是充分利用前一時刻的社團劃分結(jié)果合理高效地發(fā)現(xiàn)當前時刻的社團結(jié)構(gòu)，并克服相鄰時刻社團結(jié)構(gòu)發(fā)生劇變以及增量聚類帶來的累積誤差持續(xù)增大的問題。算法的基本思想是，在初始時刻、社團結(jié)構(gòu)劇烈變化的時刻以及累積誤差超過一定范圍的時刻，采用GN算法進行社團劃分；其它時刻則在前一時刻社團結(jié)構(gòu)的基礎(chǔ)上，根據(jù)鏈路變化僅對社團結(jié)構(gòu)發(fā)生變化的社團進行調(diào)整。獲得當前時刻的網(wǎng)絡(luò)結(jié)構(gòu)后，計算其網(wǎng)絡(luò)結(jié)構(gòu)穩(wěn)定性，判定結(jié)果是否有效。

具體地，在對社團結(jié)構(gòu)進行增量調(diào)整時，將t-1時刻的社團結(jié)構(gòu)CRt-1中在t時刻依然存在的點構(gòu)成的集合記為CR′t。 若t-1時刻的社團個數(shù)為m， 在t時刻把所有新加入的點先放入新社團C′t,m+1， 則將CR′t和C′t,m+1合并即得到Gt的初始聚類結(jié)果 {C′t,1,C′t,2,…,C′t,m,C′t,m+1} 作為t時刻的預(yù)備社團。相比于Gt-1，Gt加入或刪除了一些節(jié)點和邊。如果把節(jié)點的變化映射為邊的變化，則節(jié)點的增加可以看做是與該節(jié)點相連的邊的增加，節(jié)點的刪除可以看作是與該節(jié)點相連的邊的刪除。這些邊的變化又可以分為預(yù)備社團內(nèi)部的變化和預(yù)備社團與其它社團間邊的變化兩種。若在預(yù)備社團內(nèi)部增加邊，或在預(yù)備社團與其它社團之間刪除邊，則社團結(jié)構(gòu)不發(fā)生變化，但得到增強，這樣的社團稱為增量無關(guān)社團；反之若在預(yù)備社團內(nèi)部刪除邊或外部增加邊時，社團結(jié)構(gòu)發(fā)生改變，社團結(jié)構(gòu)被削弱，這樣的社團稱為增量相關(guān)社團。在增量聚類時僅需對增量相關(guān)社團進行調(diào)整。

定義2 社團Ct,i內(nèi)部邊的數(shù)量IN(Ct,i)

(1)

定義3 社團Ct,i外部邊的數(shù)量OUT(Ct,i)

(2)

定義4 增量相關(guān)社團RCt， 是指相對于t-1時刻，內(nèi)部刪除邊或者外部增加邊的社團集合。定義為

RCt={Ct-1,i|IN(Ct-1,i)-IN(C′t,i)>0∨
OUT(C′t,i)-OUT(Ct-1,i)>0, 1≤i≤m}+{C′t,m+1}

(3)

定義5 增量無關(guān)社團NCt， 是指相對于t-1時刻，內(nèi)部增加邊或者外部刪除邊的社團。定義為

NCt=CR′t-RCt

(4)

定義6 網(wǎng)絡(luò)變化度VAR(CRt-1,CR′t)

(5)

式中： |E′t,m+1| 為t時刻新增點的邊數(shù)。這個定義通過網(wǎng)絡(luò)中邊的變化情況來衡量前后兩個時刻網(wǎng)絡(luò)的整體波動情況。在LID算法中通過判斷該值是否超過閾值γ來判定網(wǎng)絡(luò)在t時刻是否發(fā)生劇變。通過實驗發(fā)現(xiàn)γ=0.6較為適宜。

定義7 社團穩(wěn)定度STB(CRt-1,CRt)

(6)

該定義通過相鄰時刻各社團重合節(jié)點數(shù)之和與兩個時刻節(jié)點總數(shù)的比值，反映了相鄰時刻社團集合的包含程度。該值越大，社團演化越穩(wěn)定；反之，社團演化越劇烈。通過實驗發(fā)現(xiàn)取閾值ω=0.7較為合適。

LLD模型的具體描述如下：

輸入：Gt-1,CRt-1,Gt,γ,ω,m

輸出：CRt

(1)CRt={}；

(3)若VAR(CRt-1,CR′t)>γ， 轉(zhuǎn)至(4)；否則：

1)找到CR′t中的增量無關(guān)社團NCt和增量相關(guān)社團RCt；

2)CRt=NCt；

3)通過GN算法計算RCt的社團結(jié)構(gòu)CRtemp，CRt=CRt+CRtemp；

4)若STB(CRt-1,CRt)<ω， 轉(zhuǎn)至(4)；否則轉(zhuǎn)至(5)；

(4)通過GN算法計算t時刻的社團結(jié)構(gòu)CRt；

(5)結(jié)束。

4 實驗分析

為了定量驗證本文所提模型的可行性和有效性，在真實網(wǎng)絡(luò)和人工合成網(wǎng)絡(luò)環(huán)境下與有代表性的動態(tài)社團檢測算法分別進行了綜合評測。

4.1 評價指標與對比算法

采用的量化指標如下：

(1)模塊度

模塊度Q是由Newman和Girvan提出的一種用于評價劃分結(jié)果的重要指標[9]，計算的是每一社團內(nèi)任意兩點連邊與否和隨機連邊概率的差異。定義為

(7)

式中：M為網(wǎng)絡(luò)G的邊數(shù)總和，Aij為節(jié)點i和節(jié)點j的鄰接矩陣；Ci和Cj分別是i和j所屬的社團，當Ci=Cj時，δ(Ci,Cj)=1； 否則，δ(Ci,Cj)=0。 模塊度的取值范圍是[-1,1]，值越大表示網(wǎng)絡(luò)的社團化程度越高，相應(yīng)地，認為社團發(fā)現(xiàn)算法性能越好。

(2)標準化互信息(normalized mutual information，NMI)

給定網(wǎng)絡(luò)中真實社團CRT及其劃分結(jié)果CR， 構(gòu)建 |CRT|*|CR| 的混淆矩陣N， 其中每一行對應(yīng)一個真實社團，每一列對應(yīng)一個發(fā)現(xiàn)社團，Nij表示真實社團i和發(fā)現(xiàn)社團j重合的節(jié)點個數(shù)，Ni·和N·j分別即為矩陣第i行元素和第j列元素之和， |N| 為矩陣中的節(jié)點個數(shù)，則NMI(CRT,CR) 為CRT和CR兩個劃分的相似性[13]，定義為

(8)

NMI的取值范圍是[0,1]，取值越大說明算法得到的網(wǎng)絡(luò)結(jié)構(gòu)和實際網(wǎng)絡(luò)結(jié)構(gòu)越匹配，算法的準確率越高。

綜上可知模塊度通過刻畫社團內(nèi)部節(jié)點之間的緊湊程度來度量社團結(jié)構(gòu)的顯著性，而NMI用來描述發(fā)現(xiàn)的社團結(jié)構(gòu)與真實社團結(jié)構(gòu)之間的相似性，即社團劃分結(jié)果的準確度。

實驗對比的方法為FacetNet[7]和DSBM[12]。其中FacetNet是一種典型的進化聚類方法，利用非負矩陣分解架構(gòu)同時分析社團和它們的演化，而DSBM則是增量聚類方法，首先通過隨機塊模型生成初始社團劃分，然后在每個時刻對節(jié)點進行期望值計算，再通過貝葉斯方法對節(jié)點的社團劃分進行調(diào)整等。FacetNet方法中，設(shè)置alpha=0.8。 實驗環(huán)境是主頻為3.2 GHz，內(nèi)存大小為16 GB的Intel Core i5處理器，程序運行環(huán)境為Matlab 2015b。

4.2 LID算法評測

采用真實網(wǎng)絡(luò)和人工合成網(wǎng)絡(luò)兩類數(shù)據(jù)集驗證動態(tài)社團劃分的效果，數(shù)據(jù)集的基本屬性見表2。

表2 動態(tài)測試網(wǎng)絡(luò)的基本屬性

(1)人工合成網(wǎng)絡(luò)

采用文獻[10]的方法生成兩組結(jié)構(gòu)已知的人工動態(tài)網(wǎng)絡(luò)SYN-FIX和SYN-VAR。

SYN-FIX的大部分時刻社團數(shù)目固定。由10個時刻網(wǎng)絡(luò)構(gòu)成，每個時刻都包含4個內(nèi)含32個節(jié)點的社團。為了模擬社團的動態(tài)變化，從第2個時刻開始，將每個社團中的3個節(jié)點隨機放入其它社團。這些新加入的節(jié)點以較高概率和當前社團中的其它節(jié)點建立連接，以較低概率與其它社團節(jié)點建立連接。通過調(diào)節(jié)社團內(nèi)部和社團外部連接的概率，保證平均節(jié)點度為16。

SYN-VAR也是由10個時刻組成，但每個時刻的社團數(shù)目都在發(fā)生變化。最初時刻網(wǎng)絡(luò)包含256個節(jié)點，分成類似均勻的4個社團。從第2時刻開始，從每個社團中選擇8個節(jié)點并生成一個新的32個節(jié)點社團，這個過程持續(xù)5個時刻，然后節(jié)點數(shù)目逐步恢復(fù)到最初的社團。因此，10個時刻的網(wǎng)絡(luò)社團數(shù)目依次為4,5,6,7,8,8,7,6,5,4。

引入e參數(shù)控制動態(tài)網(wǎng)絡(luò)中的噪聲比例，它表示一個節(jié)點和其它社團中節(jié)點連邊數(shù)平均值。我們進行了e=3和e=5兩組實驗，由于實驗結(jié)果相似，限于篇幅，以下僅對e=3的情況進行分析。圖1對比了LID、FacetNet、DSBM在SYN-FIX以及SYN-VAR上社團檢測結(jié)果的模塊度Q值和NMI。

從圖1可以看出，對于結(jié)構(gòu)變化較平滑的網(wǎng)絡(luò)SYN-FIX，相比FacetNet和DSBM，LID得到的社團結(jié)構(gòu)具有最好的Q值和NMI值。而SYN-VAR網(wǎng)絡(luò)結(jié)構(gòu)變化較大，LID除了在初始時刻NMI值低于DSBM，其它時刻取得最好的結(jié)果。這說明該方法能較好地探測各時間片的社團結(jié)構(gòu)。另外，觀察3種方法在上述兩種數(shù)據(jù)集上的Q值和NMI的變化趨勢也能發(fā)現(xiàn)，LID的社團檢測結(jié)果比較穩(wěn)定，F(xiàn)acetNet次之，DSBM隨時間片的增加性能衰減嚴重。這是因為FacetNet是進化式方法，對任一時刻的網(wǎng)絡(luò)社團劃分都需要重新計算，這使得其社團劃分的質(zhì)量較高。同時雖然也保持網(wǎng)絡(luò)結(jié)構(gòu)變化的短時平滑性，但總體NMI值變化較頻繁，不夠穩(wěn)定。而DSBM屬于增量式方法，最初時刻社團采用靜態(tài)劃分算法，社團劃分質(zhì)量較高；但隨著時間推移，累積誤差使得社團劃分結(jié)果與真實社團結(jié)構(gòu)的偏離逐漸增大，導(dǎo)致嚴重的性能衰減，甚至不能有效區(qū)分社團；而LID克服了上述方法的缺點，在進行增量分析之前考慮了網(wǎng)絡(luò)突變、在增量分析之后考慮了社團劃分結(jié)果的穩(wěn)定性，且在增量計算過程中僅對增量相關(guān)社團進行調(diào)整，不像DSBM那樣調(diào)整幅度較大，這就使得LID能更好地處理網(wǎng)絡(luò)變化，并有效化解累積誤差。還有一點值得注意，那就是FacetNet和DSBM在計算時需要事先確定社團個數(shù)，而LID能自動識別社團個數(shù)。

圖1 在人工合成網(wǎng)絡(luò)上社團檢測結(jié)果對比

(2)真實網(wǎng)絡(luò)

Enron郵件數(shù)據(jù)集是Enron公司內(nèi)部的郵件聯(lián)系網(wǎng)絡(luò)[8]，是高級管理人員之間的通信記錄。由于在2001年內(nèi)發(fā)生了標志性的事件(公司申請破產(chǎn)保護)，導(dǎo)致網(wǎng)絡(luò)發(fā)生突變，為了驗證這一事件對社團結(jié)構(gòu)的影響，本文實驗截選時間跨度為2001年1月至2001年12月的數(shù)據(jù)集，以月為單位對應(yīng)得到12個網(wǎng)絡(luò)快照。

由于真實網(wǎng)絡(luò)社團結(jié)構(gòu)未知，我們采用了和QCA同樣的方法得到Enron網(wǎng)絡(luò)的社團結(jié)構(gòu)[12]，并以此作為計算NMI的基準。圖2對比了LID和FacetNet在Enron上社團發(fā)現(xiàn)結(jié)果的模塊度Q值和NMI。

圖2 LID和FacetNet在Enron網(wǎng)絡(luò)上社團檢測結(jié)果對比

從圖2看出FacetNet的Q值在不同的時刻變化劇烈，NMI值則隨時間推移有明顯下降。這是由于FacetNet基于網(wǎng)絡(luò)平穩(wěn)發(fā)展的假設(shè)，通過非負矩陣分解來分析社團以及其變化，沒有應(yīng)對網(wǎng)絡(luò)動蕩的方案。而實際上，由于Enron公司在2001年12月申請破產(chǎn)保護，導(dǎo)致2001年內(nèi)郵件網(wǎng)絡(luò)各時間段社團結(jié)構(gòu)不穩(wěn)定，更在12月份發(fā)生突變。LID的Q值和NMI均好于FacetNet，說明它能很好地發(fā)現(xiàn)此類真實網(wǎng)絡(luò)的社團結(jié)構(gòu)。特別地，由于考慮了網(wǎng)絡(luò)突變的情況，使得在對2001年12月這個時間片的網(wǎng)絡(luò)進行分析時發(fā)現(xiàn)其發(fā)生了網(wǎng)絡(luò)突變，因此重新采用GN算法計算社團結(jié)構(gòu)，得到了準確的結(jié)果。

上述實驗結(jié)果表明，LID能較好地探測到動態(tài)網(wǎng)絡(luò)各個時間片的社團結(jié)構(gòu)，且能有效應(yīng)對現(xiàn)有動態(tài)網(wǎng)絡(luò)社團劃分中存在的累積效應(yīng)和網(wǎng)絡(luò)突變的問題。

5 結(jié)束語

針對已有動態(tài)網(wǎng)絡(luò)社團檢測方法不能很好地解決網(wǎng)絡(luò)突變和累計誤差的問題，提出了LID模型，根據(jù)鏈路變化實現(xiàn)增量式動態(tài)社團檢測。在初始時刻和必要時刻，LID基于節(jié)點重要性進行靜態(tài)社團發(fā)現(xiàn)，其它時序則依據(jù)鏈路變化實現(xiàn)增量式動態(tài)社團發(fā)現(xiàn)。特別地，提出將重要節(jié)點作為社團初始聚類中心的思想，也克服了演化聚類中進化式和增量式動態(tài)社團發(fā)現(xiàn)的固有缺陷。通過在多個數(shù)據(jù)集中的對比實驗結(jié)果表明，LID能較好地探測到動態(tài)網(wǎng)絡(luò)各個時間片的社團結(jié)構(gòu)，且能應(yīng)對網(wǎng)絡(luò)突變和累積誤差的問題，比經(jīng)典的FacetNet和DSBM更穩(wěn)定。

為了提升應(yīng)用價值，未來還一些問題值得深入探討。例如，①如何對算法進行并行化以加快算法的速度，使得其能夠適用于超大規(guī)模的網(wǎng)絡(luò)；②當前算法僅根據(jù)網(wǎng)絡(luò)的拓撲圖進行結(jié)構(gòu)挖掘，而忽略了個體對社團形成的作用。如何對除結(jié)構(gòu)外的其它因素進行分析將是下一步工作的重點。