基于鏈路變化的增量式動態網絡社團檢測模型

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

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

0 引 言

復雜網絡指將自然界中存在的大量復雜系統抽象為由節點和邊形成的網絡。大量研究表明，結構性和動態性是復雜網絡的本質特性。結構性體現為社團，是指復雜網絡中的節點呈現出以簇為特征的聚集狀態，簇內節點聯系緊密，簇間節點聯系松散。動態性則指節點會持續地加入和離開網絡，并且節點間鏈接的強度在不斷變化，導致網絡中的社團結構也隨時間發生演化[1]。檢測隨時間演化的動態社團結構有助于揭示網絡的組織原則和功能特性，理解網絡演化的動力學過程，具有十分重要的理論和應用價值。

演化聚類法是動態網絡社團檢測的兩種主要研究方法之一，總體思想是以歷史時刻網絡社團劃分為基礎，根據當前時刻網絡的變化進行社團結構的調整。目前存在的主要問題包括：初始社團劃分不精確，以及隨時間推進或社團突變導致的累計誤差。

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

1 相關研究

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

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

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

2 問題描述

動態社團發現所研究的對象是動態網絡。動態網絡G={G1,G2,…,GTOTAL} 是由TOTAL個時刻的網絡組成的序列。表1給出了基本符號及其定義。

表1 基本符號

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

3 LID

3.1 總體思想

本文設計的動態網絡社團檢測模型主要包含靜態社團檢測和動態社團檢測兩個算法，其中靜態社團檢測采用GN算法。具體步驟如下：

(1)利用GN算法檢測t=1時網絡Gt的靜態網絡社團結構，獲取初始的社團集合CR1。

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

3.2 LID模型設計

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

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

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

(1)

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

(2)

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

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 增量無關社團NCt， 是指相對于t-1時刻，內部增加邊或者外部刪除邊的社團。定義為

NCt=CR′t-RCt

(4)

定義6 網絡變化度VAR(CRt-1,CR′t)

(5)

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

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

(6)

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

LLD模型的具體描述如下：

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

輸出：CRt

(1)CRt={}；

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

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

2)CRt=NCt；

3)通過GN算法計算RCt的社團結構CRtemp，CRt=CRt+CRtemp；

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

(4)通過GN算法計算t時刻的社團結構CRt；

(5)結束。

4 實驗分析

為了定量驗證本文所提模型的可行性和有效性，在真實網絡和人工合成網絡環境下與有代表性的動態社團檢測算法分別進行了綜合評測。

4.1 評價指標與對比算法

采用的量化指標如下：

(1)模塊度

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

(7)

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

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

給定網絡中真實社團CRT及其劃分結果CR， 構建 |CRT|*|CR| 的混淆矩陣N， 其中每一行對應一個真實社團，每一列對應一個發現社團，Nij表示真實社團i和發現社團j重合的節點個數，Ni·和N·j分別即為矩陣第i行元素和第j列元素之和， |N| 為矩陣中的節點個數，則NMI(CRT,CR) 為CRT和CR兩個劃分的相似性[13]，定義為

(8)

NMI的取值范圍是[0,1]，取值越大說明算法得到的網絡結構和實際網絡結構越匹配，算法的準確率越高。

綜上可知模塊度通過刻畫社團內部節點之間的緊湊程度來度量社團結構的顯著性，而NMI用來描述發現的社團結構與真實社團結構之間的相似性，即社團劃分結果的準確度。

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

4.2 LID算法評測

采用真實網絡和人工合成網絡兩類數據集驗證動態社團劃分的效果，數據集的基本屬性見表2。

表2 動態測試網絡的基本屬性

(1)人工合成網絡

采用文獻[10]的方法生成兩組結構已知的人工動態網絡SYN-FIX和SYN-VAR。

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

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

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

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

圖1 在人工合成網絡上社團檢測結果對比

(2)真實網絡

Enron郵件數據集是Enron公司內部的郵件聯系網絡[8]，是高級管理人員之間的通信記錄。由于在2001年內發生了標志性的事件(公司申請破產保護)，導致網絡發生突變，為了驗證這一事件對社團結構的影響，本文實驗截選時間跨度為2001年1月至2001年12月的數據集，以月為單位對應得到12個網絡快照。

由于真實網絡社團結構未知，我們采用了和QCA同樣的方法得到Enron網絡的社團結構[12]，并以此作為計算NMI的基準。圖2對比了LID和FacetNet在Enron上社團發現結果的模塊度Q值和NMI。

圖2 LID和FacetNet在Enron網絡上社團檢測結果對比

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

上述實驗結果表明，LID能較好地探測到動態網絡各個時間片的社團結構，且能有效應對現有動態網絡社團劃分中存在的累積效應和網絡突變的問題。

5 結束語

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

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