基于多目標演化聚類的大規模動態網絡社區檢測

李 赫 印 瑩 李 源 趙宇海 王國仁

(東北大學計算機科學與工程學院 沈陽 110819)

真實世界中，網絡的節點和邊通常會隨時間動態地變化，這導致了網絡中的社團結構也會隨著時間發生改變.從2005年開始，對靜態網絡缺失的動態特征的研究逐漸成為了研究者們關注的熱點[1].動態網絡可以表示成由各個時刻靜態網絡組成的快照序列，動態網絡社區檢測的目的就是準確地挖掘出每一時刻快照的社區結構，從而可以分析社區結構隨著時間的演變過程，這是無法通過靜態網絡社區檢測洞察的.

動態網絡社區檢測有廣泛的應用.在基因網絡分析方面，動態網絡社區檢測能揭示特征基因集隨時間的變化過程;在電商數據分析方面，動態網絡社區檢測能發現用戶的偏好變化情況;在社交網絡數據分析方面，動態網絡社區檢測能找出興趣團體，預測團體可能參加的活動.此外，在新聞標題內容分析、論文作者合作關系分析、金融股市分析等方面，動態網絡社區檢測也有著廣泛的應用.隨著社區檢測技術的發展，動態網絡社區檢測將會在越來越多的實際網絡中得到應用，并發揮巨大的作用.

演化聚類框架是動態社區檢測的主流方法之一，其基本思想是在第一時刻網絡快照社區檢測的基礎上，根據社區結構的時間平滑性，用前一時刻的社區檢測結果指導當前時刻的社區劃分，以提高動態網絡社區檢測的效率.為了避免噪音等因素的影響，保證動態社區檢測的準確性，許多文獻把演化聚類框架引入到動態網絡社區中來.但是，演化聚類存在以下2個問題： 1)在有效性方面，若初始社區結構檢測不準確，會導致后續社區結構檢測的“結果漂移”和“誤差累積”問題，即上一個結果不準確將導致下一個聚類不準確，并導致這種不準確性愈演愈烈;2)在效率方面，基于模塊度優化的社區檢測方法是NP難的[2]，許多精確算法無法在合理的時間內解決該問題.

針對以上問題，本文提出一種基于改進演化聚類框架和離散粒子群算法的多目標動態社區檢測方法，本文的主要貢獻有4個方面：

1) 提出基于最近未來參考的演化聚類框架，提高初始聚類準確性，保證動態網絡社區檢測的可靠性.

2) 離散粒子群優化算法與基于精英策略的非支配排序遺傳算法(NSGA-Ⅱ)結合，并基于演化聚類框架，利用前一時刻社區劃分結果來快速指導粒子群算法搜索當前快照中的社團結構.

3) 提出基于去冗余策略的隨機游走初始個體生成算法DIGRW，對粒子群的位置進行初始化，提高了初始粒子群的個體多樣性和個體精度.

4) 提出多個體交叉算子，增強算法的局部搜索能力，提高算法的收斂速度.

1 相關工作

由于動態網絡社區檢測能揭示靜態網絡檢測無法洞察的社區結構隨時間變化的規律，所以，自動態網絡社區檢測這一概念出現以來，一系列針對該問題的相關算法被先后提出.如Sarkar等人[3]提出利用數據挖掘技術分析動態網絡的方法——基于潛在空間模型的動態網絡社區檢測方法.Cordeiro等人[4]提出一種基于本地模塊度優化的動態社區自適應發現算法. Li等人[5]提出了一種基于增量識別的聚類方法來解決動態網絡社區檢測問題. Lander等人[6]提出多目標圖挖掘算法，用來在復雜動態網絡中挖掘和檢測社區結構.Ma等人[7]提出進化非負矩陣因子分解算法來發現動態網絡中社區的演變規律.

由于基于模塊度優化的社區檢測方法是經典NP難問題，上述精確算法在處理大規模動態網絡社區檢測時面臨很大挑戰.與精確算法相比，演化算法在處理大數據過程中具有較明顯的優勢[8].特別地，由于演化算法具有高度伸縮性、靈活性、全局優化等能力，并在特征選擇時可同時實現針對多目標的優化，因此演化聚類算法在動態網絡分析領域中逐漸嶄露頭角.

Chakrabarti等人[9]首次提出演化聚類框架，該框架指出動態網絡具有時間平滑性，即相鄰時刻動態網絡前后變化差距不大.Kim等人[10]為了提高效率，進一步提出基于演化聚類框架的動態網絡社區檢測方法，即粒子和密度的演化聚類方法來分析動態網絡的社區結構.Pizzuti等人[11]提出經典的DYN-MOGA算法.首次將多目標優化方法和演化聚類框架結合用于動態網絡社區檢測，使算法具有隱并行性，既保證了當前時刻社區劃分質量，又保證了當前時刻社區劃分與前一時刻社區劃分的相似度較大.這些算法將演化聚類和演化算法結合，用于動態網絡社區檢測，在處理大規模網絡效率上有所提高，但有效性仍存在問題.

針對現有同類算法存在的以上問題，本文提出一種基于多目標演化聚類的動態網絡社區檢測算法DYN-MODPSO，既提高了效率，又保證了結果的有效性.

2 基本概念及問題定義

本節主要描述算法執行過程中涉及的基本概念，并對要解決的主要問題給出具體定義.

2.1 基本概念

動態網絡社區檢測主要涉及2個基本概念，一個是對某個社區劃分好壞的評估，另一個是對不同社區劃分相似性的評估.以下分別描述這2個概念.

(1)

(2)

(3)

(4)

2.2 問題定義

動態網絡可以建模為圖N={N1,N2,…,NT}的形式，其中T表示時刻，Ni表示時刻i的網絡快照.社區是一系列的節點集合，這些集合內部節點具有強關聯關系，集合間的節點具有弱關聯關系.動態網絡社區檢測就是要找出不同時刻網絡快照中存在的真實社區結構.為了定量地衡量社區結構劃分好壞，本文采用社區分數CS來評估社區劃分質量，用歸一化互信息函數NMI來評估2種社區劃分的相似性.

3 基于改進粒子群的社區檢測算法MRDPSO

基于模塊度的動態社區檢測是NP難問題，因此本文提出將粒子群優化算法和演化聚類框架相結合的有效解決方法.傳統粒子群算法主要用于處理靜態網絡數據，不能和演化聚類框架相結合.本文對文獻[11]提出的離散粒子群算法進行了改進，提出了算法MRDPSO(multi-results discrete particle swarm optimization).MRDPSO與現有的粒子群算法不同，主要從3個方面進行了改進：1)改進了粒子群算法的輸出，可以輸出多個最優解，避免了最優解的遺漏問題;2)用基于去冗余的隨機游走初始群體生成方法初始化粒子群，提高粒子群中個體多樣性并保證個體初始精度;3)提出多個體交叉算子(multi-individuals crossover operator, MICO)及改進的干擾算子NBM+(neighbor based mutation)，增強算法的局部搜索能力.

3.1 MRDPSO總體描述

MRDPSO偽代碼如算法1所示.MRDPSO框架由3個主要部分構成： 1)初始化階段，利用基于去冗余策略的隨機游走初始群體生成算法DIGRW初始化粒子群的位置信息，保證了初始種群個體具有一定精度和多樣性，避免算法陷入早熟(行①～④);2)搜索階段，對多目標粒子群社區檢測方法進行改進，使得粒子群的全局最優位置都保留下來，使算法能夠適應動態社區檢測的需求(行⑤～);3)突變階段，提出多個體交叉算子MICO(行)及改進的干擾算子NBM+(行⑨)，使得粒子群在向全局最優解靠近的同時，能夠在小范圍的精英粒子群體中進行局部搜索，提高算法發現全局最優解的效率.3.2～3.4節將對這3個主要步驟分別進行描述.

算法1. MRDPSO.

輸入：靜態網絡G={V,E};

① 粒子群位置初始化：利用DIGRW得到所有粒子的位置P={x1,x2,…,xpop};

② 粒子群速度初始化：初始化所有粒子速度V={v1,v2,…,vpop}，令vi=0,其中i=1,2,…,pop;

⑤ 迭代，t=0;

⑥ fori=1,2,…,popdo

3.2 粒子群初始化

3.2.1 編碼方式

在用演化計算進行社區檢測的過程中，每個個體作為一種社區劃分方案，都以編碼的方式存在.目前的編碼方式主要有字符串編碼方式和位鄰接編碼方式[13].

圖1(a)為一個原始網絡；圖1(b)為原始網絡的3個子圖，每個子圖表示一個社區.圖2的位鄰接編碼對應圖1(b)所示的劃分，圖2中字符串編碼為位鄰接編碼的解碼.在位鄰接編碼方式中，如果節點i的基因值是j，則節點i與節點j位于相同社區;在字符串編碼方式中，如果節點i的基因值為k，則節點i在標號為k的社區中.

如圖2所示，基于位鄰接的編碼方式先轉換成字符串編碼，然后再解碼成社區劃分C={C1,C2,C3}的集合形式.所以位鄰接編碼方式解碼困難、效率低，故本文采用直觀、高效的字符串編碼方式.

3.2.2 初始化粒子群位置

如果初始粒子群有過多的冗余個體，就不能保證初始種群個體有較強的多樣性.如圖3所示.

Fig. 1 Community division of the network圖1 網絡的社區劃分

Fig. 2 The encoding scheme圖2 編碼方式

Fig. 3 The encoding scheme and the corresponding community division圖3 編碼方式與對應的社區劃分

圖3(a)中2種不同的字符串編碼均對應如圖3(b)所示的劃分，因此圖3中的2種字符串編碼稱為冗余編碼.過多的冗余個體很容易導致算法陷入局部最優，或者算法的收斂速度降低.

針對這一問題，本文提出基于去冗余策略的隨機游走初始群體生成算法DIGRW(different individual generation based on random walk).算法DIGRW大致過程有4個步驟：1)用基于隨機行走的初始群體生成算法生成一個粒子位置p;2)用字符串去冗余方法(redundancy removal method, RRM)將個體p唯一化;3)若個體不重復，保留到種群中，否則刪除;4)當種群個數達到上限時，停止生成個體.后2個步驟比較直觀，以下主要對DIGRW算法的前2步加以描述.

隨機游走初始化社區劃分的理論基礎是：根據社區的連接屬性，即社區內的連接密度遠大于社區外的連接密度，那么如果起始節點和目的節點位于同一社區，則會有更多經過k步到達目的節點的路徑存在;反之，經過k步到達目的節點概率很小.基于隨機游走的初始化社區劃分基本過程為：1)隨機選定一個目的節點n，計算每個節點經過k步到n的概率;2)將所有節點依照概率值降序排列，在排序后的節點中找出二分分列點，使得模塊度函數Q增加最大;3)如果不存在使函數Q增大的分裂點，遞歸終止，否則分裂點將當前網絡分裂成2個子網絡，并分別對其遞歸執行上述操作.

算法2.RRM(p).

輸入：編碼p;

輸出：p所對應的唯一編碼u.

①u[1]=1;

② max=u[1];

③ for inti=0,1,…,|p|-1 do

④ for intj=0,1,…,ido

⑤ if(p[i]≠p[j])

⑥ continue;

⑦ else

⑧u[i]=u[j];

⑨ break;

⑩ end if

字符串去冗余策略RRM是將給定的編碼標準化，使其成為能唯一表示該編碼所對應社區劃分的形式.算法RRM步驟如算法1所示.RRM的本質是對節點所屬的社區標號進行調整.在每個編碼p中，規定節點1所屬社區的標號為1，即u[1]=1(行①～②).從節點2開始，依次對節點的社區標號進行調整：如果節點i與前面的節點j處于相同社區，那么u[i]=u[j]，否則如果節點i與前面的每個節點都不在一個社區，那么將當前最大的社區標號值加1，作為u[i]的社區標號(行③～).

3.3 粒子群搜索

(5)

(6)

3.4 干擾算子和交叉算子

粒子群優化算法可以通過結合遺傳操作中的交叉和變異操作來保留最優粒子，增強種群多樣性和增加跳出局部最優區域的能力.本研究中分別提出一種新的交叉算子MICO和一種新的干擾算子NBM+來實現粒子群優化過程中的個體交叉和變異操作.以下分別對這2個算子進行介紹.

3.4.1 多個體交叉算子MICO

傳統交叉算子僅是針對2個父代個體，與此不同，本文提出一種新的多個體交叉算子.受聚類融合算法平衡多個聚類結果獲得更準確結果的思想啟發[14-17]，本文將遺傳算法中傳統2個父代個體交叉算子擴展成多個體交叉算子，提出多個體交叉算子MICO.

MICO交叉操作過程有3個：1)從所有粒子的歷史最優位置pbest中隨機挑選出M個位置;2)設交叉產生的新位置為x，將x[i]賦值為M個位置中第i個元素上出現次數最多的社區標號,如果有多個出現最多的社區標號，則隨機選一個賦值;3)交叉完成，產生新位置x，對x采用去冗余策略RRM去冗余.

如圖4所示，若M=5，則隨機選出5個位置向量x1,x2,x3,x4,x5,對它們進行多個體交叉操作，產生的新位置向量記為x.現在對基因位x[3]進行賦值，可以看出x1～x5的第3個基因值中的社區標號2出現次數最多，則令x[3]的基因值為2.以此類推，x的所有基因位都按照這個規律賦值，最終x=(1,1,2,1,2,3,3,3).

Fig.4 Search operation based on elitist-crossover圖4 精英交叉搜索算子

3.4.2 干擾算子NBM+

為了提高粒子群算法的局部搜索能力，文獻[14]提出干擾算子NBM.然而，NBM會產生冗余個體，故本文在此基礎上加入了字符串去冗余策略，提出改進的干擾算子NBM+來增強解的多樣性，避免算法陷入局部最優.

NBM+的過程有3步：1)生成一個[0,1]之間的隨機數m;2)判斷m與突變概率pm之間的關系，若m

4 算法DYN-MODPSO

算法MODPSO處理的是單時間片上靜態網絡聚類問題，本節基于前面提出的單快照社區檢測算法MRDPSO，進一步提出基于演化聚類框架的動態網絡社區檢測算法DYN-MODPSO(multi-objective discrete particle swarm optimization for dynamic network)來處理動態網絡社區檢測問題.

4.1 算法總體描述

DYN-MODPSO偽代碼如算法3所示.

算法3. DYN-MODPSO.

輸入：動態圖N={N1,N2,…,NT},時刻T，最大迭代次數genmax;

輸出：Nt的聚類結果Ct.

① while(t==1‖t==2)

④ end if

⑤ fort=3 toTdo

⑦ while (gen≤genmax)

⑧ fori=1,2,…,popdo

算法3由2個主要部分構成：1)基準聚類校正，此階段分別用MRDPSO處理動態網絡中的前2張快照，通過計算不同快照中社區劃分的相似性，基于時間平滑性原理對初始社區的檢測結果進行校正，避免因快照1聚類結果不準導致快照2聚類結果不準的問題(行①～④);2)多目標演化聚類.此階段在基準聚類校正的基礎上，將多目標優化算法NSGA-Ⅱ與MRDPSO融合，處理后續快照的社區檢測問題(行⑤～).以下各節將對這2個主要步驟分別進行描述.

4.2 基準聚類校正

前面改進的粒子群算法MRDPSO在與演化聚類結合處理動態社區檢測的過程中，仍然會產生“結果漂移”和“誤差累積”的問題.為解決該問題，本文提出基于最近未來參考策略的基準聚類校正方法，保證初始聚類結果的準確性，從而提高動態社區檢測結果的有效性.

4.3 多目標演化聚類

對poplist采用多目標優化算法NSGA-Ⅱ中的非支配排序和擁擠距離排序[18-20]，根據動態網絡社區的時間平滑性，選出社區劃分質量好，同時又與前一張快照劃分最相似的解作為當前快照的劃分結果(行～).依照這樣的規律，DYN-MODPSO對每一張動態圖快照都進行關聯性地處理，直到處理完最后一個動態圖快照NT,輸出最優社區劃分方案CT，算法結束(行～).粒子群的非支配排序過程，就是粒子通過兩兩比較CS與NMI后，按照適應度值從大到小進行的排序過程.粒子群的擁擠距離排序過程，就是在同一個支配等級中，即適應度值相同的條件下，選擇互不相似的粒子排在前面，將比較與前面粒子比較相似的粒子排在后面，這樣能夠避免得到的解扎堆聚集，從而保證解的多樣性.

5 實驗結果與分析

5.1 實驗環境配置

本文分別用人工網絡和真實世界網絡對算法進行了測試，對比算法是DYN-MOGA,Kim-Han,IBEA.本實驗所用的軟硬件環境如下：Red Hat 64位操作系統，16核CPU，主頻1.9 GHz，16 GB內存，2 TB硬盤;Eclipse版本為4.5.0，Java版本為1.8.0.

5.2 實驗所用數據集

本文使用Youtube,LiveJournal,DBLP，Flickr這4個真實數據集和人工數據集進行實驗[21-22].其中，Youtube是用戶到用戶的鏈接關系網;DBLP是作者合作關系網;LiveJournal是在線社交關系網;Flickr是一個分享網站的組員關系網.

人工數據集使用文獻[21]中的算法生成.數據集Dz(z=3,4,5,6),其中z表示不同社區之間的邊平均數.z越大，社團間的連邊越多，社團內的邊越少，社團結構越不明顯.數據集統計信息如表1、表2所示.

Table 1 Real Datasets表1 真實數據集

Table 2 Synthetic Datasets表2 合成數據集

5.3 實驗結果及分析

實驗結果主要從NMI值、模塊度、運行時間和收斂性4個方面驗證算法的有效性.以下分別給出算法DYN-MODPSO在這4個指標下的度量結果.

5.3.1 NMI值比較

由于人工網絡的社區劃分已經確定，所以本文選擇第2節介紹的歸一化互信息函數NMI作為指標，來評估這3個算法的社區劃分結果和標準社區劃分的相似性，從而檢測算法的準確性.圖5所示的是算法對人工網絡10張快照檢測結果的NMI值.

NMI的值越接近1，算法的檢測結果越接近真實的社區劃分.如圖5所示，當z=3時，DYN-MODPSO的NMI值接近1，而DYN-MOGA和Kim-Han的NMI值分別在0.95和0.9上下浮動,IBEA的值初始接近0.95，隨著時間的推移，它的NMI值逐漸下降，在時間片T=10時低于0.9.當z=4，5時，4個算法的NMI值都下降，但是DYN-MODPSO的NMI值都穩定在0.9,明顯高于DYN-MOGA,Kim-Han和IBEA.當z=6時，DYN-MOGA，

Fig. 5 NMI value of the synthetic dataset圖5 人工數據集的NMI值

Kim-Han，IBEA的NMI值已經接近0.6,而DYN-MODPSO仍穩定在0.85.

由此可以看出，當網絡社區結構明顯時，4個算法都能檢測到動態網絡中準確的社區結構.當動態網絡社區結構變得模糊，4個算法的社區檢測能力均下降，但是DYN-MODPSO依然可以檢測到相對準確的社區結構.故算法DYN-MODPSO的檢測能力都優于DYN-MOGA，Kim-Han，IBEA，并且穩定性較強.

5.3.2 模塊度比較

由于真實數據集的社區劃分未知，所以用衡量社區劃分質量的模塊度函數來對實驗結果進行評估.模塊度值越大，結果越接近真實的社區結構.模塊度函數記作Q，定義為社區內實際的邊數與隨機連接情況下社區內期望的邊數之差.函數Q的計算公式如下：

(7)

其中，A是網絡的鄰接矩陣，m是網絡的總邊數，ki表示節點i的度，ci表示節點i所在的社區標號.如果i=j,則δ(i,j)=1，否則δ(i,j)=0.

本文選擇數據集的前5張快照，記錄它們的模塊度，如圖6所示.從圖6中可以看出DYN-MODPSO的模塊度大于DYN-MOGA，Kim-Han，IBEA.如圖6(a)(b)，4個算法的模塊度都很高，DYN-MODPSO穩定在0.65上下，隨著數據集規模變大，如圖6(c)(d)，4個算法的模塊度均減少，但是DYN-MODPSO的模塊度值仍然在0.53上下.所以，DYN-MODPSO準確性很高，并且適合處理大數據網絡圖.

5.3.3 運行時間比較

Fig. 6 The modular comparison of four real datasets圖6 4個真實數據集的模塊度比較

Fig. 7 Runtime comparison of the two algorithms圖7 算法運行時間對比

圖7所示的是算法的運行時間對比圖.算法在人工數據集上的平均運行時間如圖7(a)所示，可以看出DYN-MODPSO的運行時間小于DYN-MOGA.當z=3，4時，算法DYN-MODPSO和DYN-MOGA的運行時間相差不大.當z=5,6時，網絡中的社團結構變得模糊，此時DYN-MOGA的運行時間比DYN-MOGA將近縮短了一半.

算法在4個真實數據的平均運行時間如圖7(b)所示，DYN-MOGA的運行時間比DYN-MRDPSO長，而且數據集越大，運行時間差越大，如圖7所示DYN-MOGA在LiveJournal數據集的運行時間是DYN-MRDPSO的2倍多.所以DYN-MRDPSO是更高效的動態社區檢測演化算法，更適合處理大規模數據.

5.3.4 收斂性比較

在社區檢測方法中，DYN-MRDPSO和DYN-MOGA都是演化算法.收斂性是評估演化算法的一個指標.在不斷地迭代過程中，種群中不斷優化最優解，當達到一定迭代次數時，最優解趨于穩定，不會隨著迭代次數的增加而變化，這時算法收斂.

本文記錄了DYN-MRDPSO和DYN-MOGA收斂時的最小迭代次數，如圖8所示.DYN-MRDPSO的迭代次數遠小于DYN-MOGA，說明DYN-MRDPSO具有更高的執行效率.因為DYN-MRDPSO利用DIGRW來初始化種群，使種群在一定程度上接近最優解，而DYN-MOGA的初始種群是隨機生成的，所以算法的迭代次數比DYN-MRDPSO多許多.

Fig. 8 Convergence comparison of algorithms圖8 算法收斂性對比

6 總結與展望

本文提出一個參考最近未來的演化聚類框架，并將其引入粒子群社區檢測方法中，提出了DYN-MODPSO算法.為了加快粒子群算法的收斂速度，本文對隨機行走社區劃分方法做了改進，提出了基于去冗余策略的隨機行走初始個體生成算法，來初始化粒子群，使得粒子具有一定的精度和多樣性.在粒子群的搜索過程中，本文引入多目標優化算法NSGA-Ⅱ來同時優化NMI和CS這2個社區劃分適應度函數，并加入干擾算子和多個體交叉算子來加強算法的局部搜索能力.

通過實驗可以看出，在社區檢測的性能方面，算法DYN-MRDPSO比DYN-MOGA和Kim-Han能檢測到更準確的社區結構，是有效的.在社區檢測的準確性方面，算法DYN-MODPSO的社區劃分準確性高于DYN-MOGA和Kim-Han，且具有較優的穩定性.故算法DYN-MODPSO是有應用意義的，可以用于動態網絡社區檢測.