基于多目標演化聚類的大規(guī)模動態(tài)網(wǎng)絡(luò)社區(qū)檢測

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

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

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

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

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

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

1) 提出基于最近未來參考的演化聚類框架，提高初始聚類準確性，保證動態(tài)網(wǎng)絡(luò)社區(qū)檢測的可靠性.

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

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

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

1 相關(guān)工作

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

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

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

針對現(xiàn)有同類算法存在的以上問題，本文提出一種基于多目標演化聚類的動態(tài)網(wǎng)絡(luò)社區(qū)檢測算法DYN-MODPSO，既提高了效率，又保證了結(jié)果的有效性.

2 基本概念及問題定義

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

2.1 基本概念

動態(tài)網(wǎng)絡(luò)社區(qū)檢測主要涉及2個基本概念，一個是對某個社區(qū)劃分好壞的評估，另一個是對不同社區(qū)劃分相似性的評估.以下分別描述這2個概念.

(1)

(2)

(3)

(4)

2.2 問題定義

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

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

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

3.1 MRDPSO總體描述

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

算法1. MRDPSO.

輸入：靜態(tài)網(wǎng)絡(luò)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 編碼方式

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

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

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

3.2.2 初始化粒子群位置

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

Fig. 1 Community division of the network圖1 網(wǎng)絡(luò)的社區(qū)劃分

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

Fig. 3 The encoding scheme and the corresponding community division圖3 編碼方式與對應(yīng)的社區(qū)劃分

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

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

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

算法2.RRM(p).

輸入：編碼p;

輸出：p所對應(yīng)的唯一編碼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是將給定的編碼標準化，使其成為能唯一表示該編碼所對應(yīng)社區(qū)劃分的形式.算法RRM步驟如算法1所示.RRM的本質(zhì)是對節(jié)點所屬的社區(qū)標號進行調(diào)整.在每個編碼p中，規(guī)定節(jié)點1所屬社區(qū)的標號為1，即u[1]=1(行①～②).從節(jié)點2開始，依次對節(jié)點的社區(qū)標號進行調(diào)整：如果節(jié)點i與前面的節(jié)點j處于相同社區(qū)，那么u[i]=u[j]，否則如果節(jié)點i與前面的每個節(jié)點都不在一個社區(qū)，那么將當前最大的社區(qū)標號值加1，作為u[i]的社區(qū)標號(行③～).

3.3 粒子群搜索

(5)

(6)

3.4 干擾算子和交叉算子

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

3.4.1 多個體交叉算子MICO

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

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

如圖4所示，若M=5，則隨機選出5個位置向量x1,x2,x3,x4,x5,對它們進行多個體交叉操作，產(chǎn)生的新位置向量記為x.現(xiàn)在對基因位x[3]進行賦值，可以看出x1～x5的第3個基因值中的社區(qū)標號2出現(xiàn)次數(shù)最多，則令x[3]的基因值為2.以此類推，x的所有基因位都按照這個規(guī)律賦值，最終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會產(chǎn)生冗余個體，故本文在此基礎(chǔ)上加入了字符串去冗余策略，提出改進的干擾算子NBM+來增強解的多樣性，避免算法陷入局部最優(yōu).

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

4 算法DYN-MODPSO

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

4.1 算法總體描述

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

算法3. DYN-MODPSO.

輸入：動態(tài)圖N={N1,N2,…,NT},時刻T，最大迭代次數(shù)genmax;

輸出：Nt的聚類結(jié)果Ct.

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

④ end if

⑤ fort=3 toTdo

⑦ while (gen≤genmax)

⑧ fori=1,2,…,popdo

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

4.2 基準聚類校正

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

4.3 多目標演化聚類

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

5 實驗結(jié)果與分析

5.1 實驗環(huán)境配置

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

5.2 實驗所用數(shù)據(jù)集

本文使用Youtube,LiveJournal,DBLP，F(xiàn)lickr這4個真實數(shù)據(jù)集和人工數(shù)據(jù)集進行實驗[21-22].其中，Youtube是用戶到用戶的鏈接關(guān)系網(wǎng);DBLP是作者合作關(guān)系網(wǎng);LiveJournal是在線社交關(guān)系網(wǎng);Flickr是一個分享網(wǎng)站的組員關(guān)系網(wǎng).

人工數(shù)據(jù)集使用文獻[21]中的算法生成.數(shù)據(jù)集Dz(z=3,4,5,6),其中z表示不同社區(qū)之間的邊平均數(shù).z越大，社團間的連邊越多，社團內(nèi)的邊越少，社團結(jié)構(gòu)越不明顯.數(shù)據(jù)集統(tǒng)計信息如表1、表2所示.

Table 1 Real Datasets表1 真實數(shù)據(jù)集

Table 2 Synthetic Datasets表2 合成數(shù)據(jù)集

5.3 實驗結(jié)果及分析

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

5.3.1 NMI值比較

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

NMI的值越接近1，算法的檢測結(jié)果越接近真實的社區(qū)劃分.如圖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值都穩(wěn)定在0.9,明顯高于DYN-MOGA,Kim-Han和IBEA.當z=6時，DYN-MOGA，

Fig. 5 NMI value of the synthetic dataset圖5 人工數(shù)據(jù)集的NMI值

Kim-Han，IBEA的NMI值已經(jīng)接近0.6,而DYN-MODPSO仍穩(wěn)定在0.85.

由此可以看出，當網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)明顯時，4個算法都能檢測到動態(tài)網(wǎng)絡(luò)中準確的社區(qū)結(jié)構(gòu).當動態(tài)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)變得模糊，4個算法的社區(qū)檢測能力均下降，但是DYN-MODPSO依然可以檢測到相對準確的社區(qū)結(jié)構(gòu).故算法DYN-MODPSO的檢測能力都優(yōu)于DYN-MOGA，Kim-Han，IBEA，并且穩(wěn)定性較強.

5.3.2 模塊度比較

由于真實數(shù)據(jù)集的社區(qū)劃分未知，所以用衡量社區(qū)劃分質(zhì)量的模塊度函數(shù)來對實驗結(jié)果進行評估.模塊度值越大，結(jié)果越接近真實的社區(qū)結(jié)構(gòu).模塊度函數(shù)記作Q，定義為社區(qū)內(nèi)實際的邊數(shù)與隨機連接情況下社區(qū)內(nèi)期望的邊數(shù)之差.函數(shù)Q的計算公式如下：

(7)

其中，A是網(wǎng)絡(luò)的鄰接矩陣，m是網(wǎng)絡(luò)的總邊數(shù)，ki表示節(jié)點i的度，ci表示節(jié)點i所在的社區(qū)標號.如果i=j,則δ(i,j)=1，否則δ(i,j)=0.

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

5.3.3 運行時間比較

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

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

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

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

5.3.4 收斂性比較

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

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

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

6 總結(jié)與展望

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

通過實驗可以看出，在社區(qū)檢測的性能方面，算法DYN-MRDPSO比DYN-MOGA和Kim-Han能檢測到更準確的社區(qū)結(jié)構(gòu)，是有效的.在社區(qū)檢測的準確性方面，算法DYN-MODPSO的社區(qū)劃分準確性高于DYN-MOGA和Kim-Han，且具有較優(yōu)的穩(wěn)定性.故算法DYN-MODPSO是有應(yīng)用意義的，可以用于動態(tài)網(wǎng)絡(luò)社區(qū)檢測.