動態(tài)社區(qū)演化研究進展

潘劍飛，徐麗麗，董一鴻

（寧波大學(xué)信息科學(xué)與工程學(xué)院，浙江 寧波 315211）

動態(tài)社區(qū)演化研究進展

潘劍飛，徐麗麗，董一鴻

（寧波大學(xué)信息科學(xué)與工程學(xué)院，浙江 寧波 315211）

社區(qū)結(jié)構(gòu)是社會網(wǎng)絡(luò)普遍存在的拓?fù)涮匦灾?。挖掘社會網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)、探測并預(yù)測社區(qū)結(jié)構(gòu)的變化是社會網(wǎng)絡(luò)研究中重要的研究課題。主要從時間片處理和動態(tài)增量的策略對動態(tài)社區(qū)演化進行闡述，時間片處理策略介紹了時間片的對比演化、聚類演化、融合演化的研究方法；動態(tài)增量策略描述了核心社區(qū)、聚類、指標(biāo)的動態(tài)演化的研究方法；最后對社區(qū)演化預(yù)測的框架進行了歸納總結(jié)。

動態(tài)社區(qū)挖掘；動態(tài)社區(qū)演化；動態(tài)社區(qū)演化預(yù)測

1 引言

社會網(wǎng)絡(luò)是邊與點的連接組成的圖，通過對社會網(wǎng)絡(luò)的研究，發(fā)現(xiàn)社會網(wǎng)絡(luò)呈現(xiàn)一種內(nèi)部頂點連接緊密、外部頂點連接松散[1]的結(jié)構(gòu)，即社區(qū)結(jié)構(gòu)。社區(qū)結(jié)構(gòu)對深入理解和研究社會網(wǎng)絡(luò)的性質(zhì)具有很重要的意義，因此社區(qū)研究將成為真實社會網(wǎng)絡(luò)分析的一個重要的研究方向。

自2002年Girvan和Newman提出GN算法思想[2]以來，國內(nèi)外掀起了社區(qū)研究的熱潮，各學(xué)科領(lǐng)域 （如生物、物理、計算機等）的研究者都帶來了很多算法思想，并廣泛應(yīng)用于實際的生活中以解決各個方面的具體問題。隨著互聯(lián)網(wǎng)的快速發(fā)展，更多的人加入互聯(lián)網(wǎng)中，新浪、微博和微信等交互平臺很受廣大用戶的歡迎，用戶交互形成的社交網(wǎng)絡(luò)存在著顯著的社區(qū)結(jié)構(gòu)，研究社區(qū)結(jié)構(gòu)能夠進一步確定用戶的社交動態(tài)。同時以社區(qū)結(jié)構(gòu)的形式發(fā)現(xiàn)數(shù)據(jù)內(nèi)在的聯(lián)系，對提高網(wǎng)絡(luò)管理質(zhì)量提供輔助決策意見，發(fā)現(xiàn)社區(qū)內(nèi)的隱含子群結(jié)構(gòu)特征，發(fā)現(xiàn)未來的用戶流動、用戶需求和商品推薦的研究都有很好的指引作用。

當(dāng)前對社區(qū)結(jié)構(gòu)的研究主要集中針對于靜態(tài)網(wǎng)絡(luò)中的挖掘算法設(shè)計，隨著研究的深入，研究者開始關(guān)注復(fù)雜動態(tài)網(wǎng)絡(luò)中演化社區(qū)結(jié)構(gòu)的識別分析。社區(qū)結(jié)構(gòu)識別也正經(jīng)歷從靜態(tài)研究向動態(tài)演化分析的轉(zhuǎn)變，動態(tài)網(wǎng)絡(luò)演化社區(qū)結(jié)構(gòu)識別的研究逐步成為研究的熱點。

動態(tài)社區(qū)演化的研究過程可分為時間片處理社區(qū)演化和動態(tài)增量社區(qū)演化。時間片處理社區(qū)演化是以時間片為單位，對時間片進行分離、聚類或融合處理，并對其進行時間片社區(qū)發(fā)現(xiàn)和相似度比較或差距比較兩個過程，該做法增加了冗余計算量，同時有些比較策略沒有合理的依據(jù)。動態(tài)增量社區(qū)演化解決了時間片可能存在的硬劃分問題，通過點邊的變化判定前一次社區(qū)的變化，能細(xì)化到每個社區(qū)的演化過程，更具合理性和判定社區(qū)動態(tài)社區(qū)變化的準(zhǔn)確性。本文最后引出了社區(qū)演化的衍生品社區(qū)演化預(yù)測的框架，概括地論述了整個動態(tài)社區(qū)演化研究的主體內(nèi)容。

2 基本概念

定義1 （時間片）動態(tài)網(wǎng)絡(luò)Gt:t+n按時間段分，可表示為{Gt,Gt+1,…,Gt+n}，Gt=（Vt,Et）為 t時間段的網(wǎng)絡(luò)。

定義2 （時間片社區(qū)）對每個時間段的網(wǎng)絡(luò)Gt=（Vt, Et）,t=1,2,3,…進行社區(qū)發(fā)現(xiàn)得 Gt={Ct1,Ct2,…,Ctn},Ctn表示在t時間段的網(wǎng)絡(luò)中發(fā)現(xiàn)的第n個社區(qū)。

定義3 （動態(tài)網(wǎng)絡(luò)[3]）在t時刻到t+n時刻的動態(tài)網(wǎng)絡(luò) Gt:t+n可表示為{Ct,ΔCt+1,…,ΔCt+n},Gt=（Vt,Et）表示 t時刻頂點集合為Vt、邊的集合為Et的網(wǎng)絡(luò)。ΔGt+1表示在t+1時刻的更新子圖，即Gt+ΔGt+1=Gt+1。

定義4 （動態(tài)社區(qū)[3]）在t時刻到t+n時刻的動態(tài)社區(qū) Ct:t+n可表示為{Ct,ΔCt+1,…,ΔCt+n},Ct表示從 t時刻網(wǎng)絡(luò) Gt中挖掘的社區(qū)。ΔCt+1表示在t+1時刻的更新子社區(qū)，即Ct+ ΔCt+1=Ct+1。

定義 5 （社區(qū)演化事件[4]）對復(fù)雜動態(tài)網(wǎng)絡(luò)而言，當(dāng)網(wǎng)絡(luò)動態(tài)變化時，網(wǎng)絡(luò)中的社區(qū)可能隨時間推進而發(fā)生持續(xù)、縮減、增長、分離、融合、消失、生成等事件，這些事件將導(dǎo)致社區(qū)的結(jié)構(gòu)形態(tài)發(fā)生動態(tài)變化，以下對各個事件進行介紹：

· 持續(xù)事件表示隨時間推進過程中對應(yīng)的社區(qū)變化很小，社區(qū)變化范圍一般小于5%，如圖1（a）所示；

· 縮減事件表示隨時間推進過程中對應(yīng)的社區(qū)規(guī)模變小，社區(qū)變化范圍一般為5%～20%，如圖1（b）所示：

· 增長事件表示隨時間推進過程中對應(yīng)的社區(qū)規(guī)模變大，社區(qū)變化范圍一般為5%～20%，如圖1（c）所示；

·分離事件表示隨時間推進過程中，社區(qū)分成多個部分，包括等量分離和不等量分離兩種方式，如圖1（d）和圖1（e）所示；

·消失事件表示隨時間推進過程中，對應(yīng)的社區(qū)結(jié)構(gòu)消失，如圖1（f）所示；

·融合事件表示隨時間推進過程中，多個社區(qū)發(fā)生融合成一個社區(qū)，包括等量融合和不等量融合兩種方式，如圖1（g）和圖1（h）所示；

·生成事件表示隨時間推進過程中，新的社區(qū)結(jié)構(gòu)出現(xiàn)，如圖1（i）所示。

圖1 社區(qū)演化事件

3 時間片處理社區(qū)演化

時間片處理社區(qū)演化是指社區(qū)數(shù)據(jù)按時間段獲取形成動態(tài)時間片數(shù)據(jù)，然后以整個時間片為研究單位，對時間片進行分離、聚類或融合等處理后，用靜態(tài)社區(qū)發(fā)現(xiàn)算法或靜態(tài)聚類思想分離出對應(yīng)的社區(qū)，并探索相鄰時間片內(nèi)社區(qū)之間的變化，如圖2所示。

目前時間片分解社區(qū)演化的基本策略有3種：基于時間片的比對演化、基于時間片的聚類演化、基于時間片的融合演化。

圖2 時間片分解社區(qū)

3.1 基于時間片的比對演化

基于時間片的比對演化的思想相對比較簡單，是基于靜態(tài)社區(qū)發(fā)現(xiàn)算法進行的改進，即動態(tài)社區(qū)發(fā)現(xiàn)算法上并沒有本質(zhì)的提高，研究目標(biāo)從算法研究轉(zhuǎn)為比較策略上的改進。其思想是：首先對整個網(wǎng)絡(luò)進行時間片處理，然后針對每個時間片，用已存在的靜態(tài)社區(qū)發(fā)現(xiàn)算法（LPA算法[5]、FCM算法[6]、LMF算法[7]等）進行社區(qū)發(fā)現(xiàn)，然后用相似性比較策略對相鄰時間片社區(qū)進行社區(qū)比較，發(fā)現(xiàn)社區(qū)變化的過程并判定內(nèi)在的演變事件。

3．1．1 頂點比較策略

[8]提出在t時間片社區(qū)Ct與t+1時間片社區(qū)Ct+1間，頂點變化衡量相似性的比較標(biāo)準(zhǔn)為：

基于此比較標(biāo)準(zhǔn)，結(jié)合元社區(qū)和二分匹配的方法得到社區(qū)演化序列和演化事件。

· 如果在t+1時間片存在社區(qū)Ctk+1與t時間片的社區(qū)Cti匹配，則社區(qū)Cti在t+1時間片存活，社區(qū)Ctk+1將被添加到Cti對應(yīng)的元社區(qū)中。

·當(dāng)t+1時間片的社區(qū)不斷進入，分別對每個社區(qū)用最大相似度二分匹配與t時間片的社區(qū)進行匹配，如果t+1時間片的社區(qū)與所有 t時間片社區(qū)都沒有匹配，則認(rèn)為該社區(qū)是在t+1時間片新形成的社區(qū)，對它建立一個新的元社區(qū)。

在二分匹配過程的同時，t時間片社區(qū)Ct與t+1時間片社區(qū)Ct+1的匹配情況確定演化事件，同時匹配過程中建立的元社區(qū)，每個元社區(qū)表示為演化的社區(qū)序列。

上述比較分析方法的不足在于判定相似度條件上，其將每個頂點等同看待，這在實際的網(wǎng)絡(luò)條件下是不合理的，每個社區(qū)而言頂點應(yīng)當(dāng)有重要程度之分。

3．1．2 核心頂點比較策略

參考文獻(xiàn)[9]提出了如何獲取核心頂點的算法，核心頂點表示頂點的權(quán)值相比其他頂點更高，其中頂點的權(quán)值可以由頂點度、PageRank值等指標(biāo)來衡量。該算法和投票策略相似，對于每個頂點都有權(quán)去評估連接它的核心頂點，W（Ni）表示頂點Ni的度，如果W（Ni）的值越大，那么Ni點越重要。當(dāng)W（Ni）≥W（Nj）,Ni的核心值Cen(Ni)應(yīng)該增大|W（Ni）-W（Nj）|的值，否則Ni的核心值Cen(Ni)應(yīng)該減少|(zhì)W（Ni）-W（Nj）|的值，通過一輪投票后，當(dāng)Cen(Ni)的值為非負(fù)值時，Ni為核心頂點，否則為普通頂點。根據(jù)以上策略獲取到每個時間片的核心點，比較相鄰時間片內(nèi)核心點來確定演化社區(qū)序列。

上述比較分析方法的不足在于只考慮社區(qū)中的核心點的變化，這種核心點的比較策略沒有充分的依據(jù)說明方法的有效性，同時沒有從整體的角度去考慮社區(qū)的演化。

3．1．3 頂點數(shù)量與重要程度比較策略

參考文獻(xiàn)[4]給出了一種更合理的方法即GED算法，該算法根據(jù)演化過程中社區(qū)頂點數(shù)量和頂點重要程度共同的變化衡量相似性。社區(qū)頂點的重要程度可以根據(jù)PageRank的思路進行初始化：

在t時間片中的社區(qū)Ct中與t+1時間片社區(qū)Ct+1的相似度可由I（Ct,Ct+1）和I（Ct+1,Ct）共同來衡量，I（Ct,Ct+1）表示為：

社區(qū)演化的事件可以由I（Ct,Ct+1）、I（Ct+1,Ct）和社區(qū)的規(guī)模變化共同來決定：

· 當(dāng)I（Ct+1,Ct）≥α，I（Ct+1,Ct）≥β，|Ct|=|Ct+1|時，社區(qū) Ct

以社區(qū)Ct+1的形式在t+1時間片持續(xù)；

· 當(dāng)I（Ct+1,Ct）≥α，I（Ct+1,Ct）≥β，|Ct|＞|Gt+1|或者 I（Ct+1, Ct）≥α，I（Ct+1,Ct）≥β，|Ct|≥|Ct+1|，并且社區(qū)Ct在t+1時間片只有社區(qū)Ct+1一個社區(qū)與之匹配時，社區(qū)Ct在t+1時間片縮減為社區(qū)Ct+1；

· 當(dāng)I（Ct,Ct+1）≥α，I（Ct+1,Ct）≥β，|Ct|＜|Ct+1|或者，I（Ct,Ct+1）≥α，I（Ct+1,Ct）＜β，|Ct|＜|Ct+1|，并且社區(qū)Ct在t+1時間片只有社區(qū)Ct+1一個社區(qū)與之匹配時，社區(qū)Ct在t+1時間片增長為社區(qū)Ct+1；

· 當(dāng)I（Ct,Ct+1）≥α，I（Ct+1,Ct）≥β，|Ct|≥|Ct+1|并且社區(qū)Ct在t+1時間片不止社區(qū)Ct+1一個社區(qū)與之匹配時，社區(qū)Ct在t+1時間片分離；

· 當(dāng)I（Ct,Ct+1）≥α，I（Ct+1,Ct）＜β，|Ct|≤|Ct+1|并且社區(qū)Ct+1在t+1時間片不止社區(qū)Ct一個社區(qū)與之匹配時，社區(qū)Ct在t+1時間片融合；

· 當(dāng)在t+1時間片的每一個社區(qū)Ct+1，I（Ct,Ct+1）＜10%，I（Ct+1,Ct）＜10%時，社區(qū)Ct在t+1時間片消失；

· 當(dāng)在t時間片的每一個社區(qū)Ct，I（Ct,Ct+1）＜10%，I（Ct+1,Ct）＜10%時，社區(qū)Ct+1在t+1時間片生成。

GED算法從頂點數(shù)量和頂點重要程度共同來比較兩個時間片社區(qū)相似度，在實際運用中的合理性和實用性。

3.2 基于時間片的聚類演化

基于時間片聚類的演化是在靜態(tài)聚類分析算法的基礎(chǔ)上，提出了一個動態(tài)演化聚類思想。參考文獻(xiàn)[10]中提出社區(qū)在相鄰時間片間的變化應(yīng)該不大，對此在考察t時間片內(nèi)的社區(qū)Ct時，既要滿足當(dāng)前t時間片內(nèi)在的結(jié)構(gòu)，同時用t-1時間片來規(guī)整t時間片的社區(qū)，并且提出一種衡量t時間片社區(qū)Ct質(zhì)量的標(biāo)準(zhǔn)，可以表示為：

其中，CS用于衡量t時間片內(nèi)社區(qū)發(fā)現(xiàn)是否符合當(dāng)前社區(qū)內(nèi)部的交互，CT用于衡量t時間片的社區(qū)和t-1時間片的社區(qū)結(jié)構(gòu)的差異，并用KL散度來刻畫兩者的損失。此方法的思想雖然是時間片處理的策略，但是在發(fā)現(xiàn)社區(qū)的結(jié)構(gòu)時提出了用歷史社區(qū)結(jié)構(gòu)來做參考的思想，更具合理性，更符合時間序列的思想。但是，社區(qū)結(jié)構(gòu)的差異和發(fā)現(xiàn)過程是不斷地對矩陣進行迭代計算過程，整個過程時間復(fù)雜度很高，并不符合現(xiàn)實生活中真實的大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)。在參考文獻(xiàn)[11]中也提出了此思想，但是文獻(xiàn)屬于非重疊社區(qū)發(fā)現(xiàn)并且局限在規(guī)模不可變化的動態(tài)社區(qū)變化的過程中。

3.3 基于時間片的融合演化

基于時間片融合的演化是將相鄰時間片的網(wǎng)絡(luò)數(shù)據(jù)進行融合，并對融合后的數(shù)據(jù)進行靜態(tài)社區(qū)發(fā)現(xiàn)后，與前一時間片的社區(qū)結(jié)構(gòu)進行相似性比較和判定歸屬分離出當(dāng)前時刻的社區(qū)結(jié)構(gòu)。

參考文獻(xiàn)[12,13]中使用到派系過濾算法，該算法用于重疊最大團社區(qū)發(fā)現(xiàn)的經(jīng)典算法（CPM算法），通過判斷k完全圖的相互重疊可達(dá)性來對最大團進行發(fā)現(xiàn)，在參考文獻(xiàn)[14]中提出考慮社區(qū)應(yīng)該考慮其內(nèi)部的結(jié)構(gòu)分布，因此，從內(nèi)部結(jié)構(gòu)方面來考慮用此方法進行社區(qū)發(fā)現(xiàn)，更符合現(xiàn)實的網(wǎng)絡(luò)數(shù)據(jù)的結(jié)構(gòu)分布，并且社區(qū)的凝聚程度相對其他策略更高，但是隨著 k的增大，發(fā)現(xiàn)社區(qū)的時間復(fù)雜度將急劇增加。時間片融合的重疊最大團社區(qū)發(fā)現(xiàn)的思想是：首先將相鄰時間的網(wǎng)絡(luò)Gt和Gt+1合并成為中間網(wǎng)絡(luò)Gt,t+1，然后對Gt,t+1網(wǎng)絡(luò)用CPM算法進行社區(qū)發(fā)現(xiàn)，結(jié)合已存在網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，用頂點的Jaccard相似度進行相似度比較，根據(jù)比較結(jié)果分離出Gt+1的社區(qū)結(jié)構(gòu)。其頂點的相似度比較如下：

其方法在社區(qū)發(fā)現(xiàn)CPM有一定優(yōu)勢的同時，融合后分離的策略考慮了歷史社區(qū)的結(jié)構(gòu)分布，并不是時間片單獨處理策略，解決了時間片孤立處理的硬分割問題。但是假設(shè)兩個時間片間的社區(qū)變化不是很大的情況下，每次都要進行社區(qū)發(fā)現(xiàn)，無形中增加了社區(qū)演化發(fā)現(xiàn)過程中的時間復(fù)雜度。

3.4 時間片策略綜合比較

時間片的比對演化、聚類演化、融合演化都屬于時間片處理的社區(qū)演化策略，時間片的比對演化思想，在時間片處理方面過于粗糙，直接將其時間片分離，相鄰時間片社區(qū)劃分之間可能呈現(xiàn)顯著的結(jié)構(gòu)變化，屬于硬分割問題。時間片的聚類演化思想，當(dāng)前時間片社區(qū)的劃分依據(jù)當(dāng)前時刻社區(qū)情況和歷史時間片社區(qū)的劃分來決定，根據(jù)社區(qū)在相鄰時間片變化不是很大的原理，該考慮和歷史時間片社區(qū)的情況的差異最小化的思想具有合理性。時間片的融合演化進行相鄰時間片融合然后對重疊社區(qū)進行發(fā)現(xiàn)雖然解決了硬分割的問題，但是這3個策略不屬于真正的動態(tài)社區(qū)演化，對每個時間片處理復(fù)雜度高，甚至還得用些相似度比較獲取社區(qū)演化序列，然而比較策略標(biāo)準(zhǔn)不一，沒有合理的依據(jù)。時間片處理社區(qū)演化策略綜合比較見表1，其中n表示網(wǎng)絡(luò)頂點的數(shù)目，e表示網(wǎng)絡(luò)邊的數(shù)目，m表示社區(qū)的數(shù)目，d表示網(wǎng)絡(luò)的度（頂點度的均值）。

4 動態(tài)增量社區(qū)演化

動態(tài)增量社區(qū)演化是指根據(jù)初始時刻網(wǎng)絡(luò)的社區(qū)，隨時間的變化更新社區(qū)結(jié)構(gòu)，從而發(fā)現(xiàn)動態(tài)社區(qū)演化序列和事件。相比于時間片處理的社區(qū)演化，動態(tài)增量的社區(qū)演化充分利用了前次識別的結(jié)果，在前次的結(jié)果上進行動態(tài)判定，真正實現(xiàn)了動態(tài)識別和演化。

表1 時間片處理策略綜合比較

4.1 基于核心社區(qū)的動態(tài)演化

基于核心社區(qū)的動態(tài)演化的思想在于首先判定核心點組成的核心社區(qū)的動態(tài)變化，然后擴展為整個網(wǎng)絡(luò)的社區(qū)變化。

參考文獻(xiàn) [15]中提出追蹤社區(qū)演化的統(tǒng)一框架——FICET（fast increment community evolution tracking，快速增量社區(qū)演化跟蹤）框架，整個社區(qū)演化過程既考慮當(dāng)前社區(qū)結(jié)構(gòu)的合理性，又考慮了當(dāng)前社區(qū)結(jié)構(gòu)和歷史社區(qū)結(jié)構(gòu)的銜接性；同時，追蹤社區(qū)演化針對核心社區(qū)的增點、增邊、減點和減邊的4種變化的研究，既能保證高效率演化也能快速跟蹤社區(qū)演化的過程。整個框架如圖3所示。

圖3 FICET框架

整個框架的思想主要分為兩個步驟：社區(qū)的發(fā)現(xiàn)和核心社區(qū)動態(tài)增量演化擴展。社區(qū)發(fā)現(xiàn)是動態(tài)增量演化的基礎(chǔ)，隨后的演化都是在此基礎(chǔ)上的。社區(qū)發(fā)現(xiàn)分為3個步驟。

步驟 1 通過改變后的PageRank（modified weighted pagerank，MP）算法，發(fā)現(xiàn)網(wǎng)絡(luò)的核心點、連接邊組成核心的子圖。利用改進后的MP算法求PageRank值：

步驟 2 對核心的子圖，運用高層聚類（high-level clustering,HC）算法發(fā)現(xiàn)核心的社區(qū)集。其中HC算法中引入適應(yīng)度函數(shù)來作為核心社區(qū)形成標(biāo)準(zhǔn)：

步驟3 對核心的社區(qū)集，運用擴展（core community expanding，EC）算法擴展為整個網(wǎng)絡(luò)的社區(qū)。其中EC算法引入頂點和各個核心社區(qū)間親密度的概念，以頂點和各個核心社區(qū)間的大小來硬分割社區(qū)。頂點和核心社區(qū)的親密度為：

社區(qū)發(fā)現(xiàn)后，將經(jīng)歷核心社區(qū)動態(tài)增量演化擴展的過程，增量演化運用增量 （incremental community evolution, IC）算法對前一時刻的核心社區(qū)進行增量變化來發(fā)現(xiàn)當(dāng)前核心社區(qū)。同時引入社區(qū)結(jié)構(gòu)穩(wěn)定參數(shù)（community structure stability，CSM）來防止數(shù)據(jù)漂移的情況。擴展過程和社區(qū)發(fā)現(xiàn)的擴展過程一致。其中，IC算法考慮核心頂點集和對應(yīng)的邊集的變化：

其中，Vdel表示在t+1時刻消失的頂點，Vnew表示在t+1時刻新增加的頂點，Edel表示在t+1時刻消失的邊，Enew表示在t+1時刻新增加的邊。針對每一種增點、增邊、減點和減邊的變化來動態(tài)判定社區(qū)可能發(fā)生的變化。增點、增邊可能導(dǎo)致社區(qū)的增長和社區(qū)的融合事件，減點、減邊可能導(dǎo)致縮減和消失事件。

快速增量社區(qū)演化跟蹤框架體現(xiàn)了動態(tài)增量社區(qū)演化的本質(zhì)思想由t時刻核心點的社區(qū)來指導(dǎo)t+1時刻核心社區(qū)的發(fā)現(xiàn)和核心社區(qū)演化，然后對演化后核心社區(qū)通過擴展算法來獲取整個網(wǎng)絡(luò)內(nèi)的社區(qū)結(jié)構(gòu)。追蹤社區(qū)演化針對核心點社區(qū)的動態(tài)變化，既能保證演化的準(zhǔn)確性，也能快速跟蹤社區(qū)演化的過程。但是，核心社區(qū)擴展的過程采用的是頂點強硬社區(qū)分配，不能對重疊社區(qū)進行發(fā)現(xiàn)，同時社區(qū)結(jié)構(gòu)穩(wěn)定參數(shù)不夠合理。

4.2 基于聚類的動態(tài)演化

基于聚類的動態(tài)演化思想在于將靜態(tài)聚類的思想和概念運用在動態(tài)更新社區(qū)和演化事件跟蹤的過程。

參考文獻(xiàn) [16]中基于靜態(tài)密度聚類思想提出了DENGRAPH的算法。動態(tài)演化的過程，考慮積極的改變和消極的改變兩個方面。積極的改變?yōu)榭紤]新的核心頂點、新的邊界頂點、新的鄰接頂點添加時導(dǎo)致原本社區(qū)的變化。

·新的核心頂點，考察是否與已存在的社區(qū)存在連接，如果存在，將其添加到連接社區(qū)中，否則形成新的社區(qū)。

·新的邊界頂點，考察邊界頂點是否與社區(qū)中的核心頂點密度可達(dá)，如果可達(dá)，將其添加在社區(qū)中，否則作為孤立點處理。

·新的鄰接頂點，將其添加到鄰接的社區(qū)，并且更新社區(qū)內(nèi)的強度。

積極的改變可產(chǎn)生社區(qū)的生成、增長和融合事件，如圖4所示。

圖4 積極改變

消極的改變?yōu)榭紤]核心頂點、鄰邊頂點、邊界頂點和核心頂點的邊，核心頂點間邊消失時導(dǎo)致原本社區(qū)的變化。

· 核心頂點的消失，考慮核心頂點周圍的頂點，判斷其與其他核心頂點的可達(dá)性來決定原本頂點的歸屬社區(qū)。

· 鄰接頂點的消失，當(dāng)鄰邊頂點為邊界頂點時，更新社區(qū)的強度。

· 邊界頂點和核心頂點的邊消失，原本的邊界頂點可能將不可達(dá)，邊界頂點將成為孤立點。

· 連接核心頂點邊的消失，兩個核心頂點將不可達(dá)，可能產(chǎn)生社區(qū)間的分離事件發(fā)生消極的改變可產(chǎn)生社區(qū)的消失、縮減和分離的事件，如圖5所示。

圖5 消極的改變

采用聚類的思想進行動態(tài)社區(qū)演化發(fā)現(xiàn)，方法簡易，能根據(jù)靜態(tài)聚類對應(yīng)的參數(shù)和頂點變化來判定社區(qū)的變化和對應(yīng)的社區(qū)事件更具合理性，而且能細(xì)化到每個細(xì)節(jié)的變化可能導(dǎo)致的社區(qū)演變事件。

4.3 基于指標(biāo)的動態(tài)演化

基于指標(biāo)的動態(tài)演化的思想主要在于通過點、邊社區(qū)內(nèi)和社區(qū)間的變化，設(shè)定頂點的指標(biāo)判定頂點歸屬社區(qū)，從而衡量社區(qū)的動態(tài)演化過程。

參考文獻(xiàn)[17]中根據(jù)增點、增邊、減點、減邊和對于頂點是否歸屬同一個社區(qū)，建立候選的頂點集后判定社區(qū)演化的強度，如果強度大于閾值時，該時刻社區(qū)重新進行社區(qū)發(fā)現(xiàn)，否則根據(jù)候選集中頂點在相鄰社區(qū)內(nèi)頂點和鄰接頂點的永久度大小，動態(tài)更新頂點的歸屬社區(qū)，從而動態(tài)更新社區(qū)。其社區(qū)的演化強度可表示為：

社區(qū)演化強度本質(zhì)而言就是不斷累加社區(qū)點邊變化的強度，如果變化強度超過一定范圍就認(rèn)為社區(qū)演化可能產(chǎn)生數(shù)據(jù)漂移現(xiàn)象，應(yīng)當(dāng)重新進行社區(qū)發(fā)現(xiàn)的過程來防止社區(qū)演化異常，這是演化事件累積指標(biāo)，并不能明確指出當(dāng)前是否已經(jīng)發(fā)現(xiàn)偏移情況。其頂點的永久度可表示為：

頂點的永久度考慮兩個方面：一個方面是社區(qū)頂點的社區(qū)內(nèi)連接和社區(qū)外連接比，另一個方面是社區(qū)內(nèi)部結(jié)構(gòu)的結(jié)構(gòu)有效度。

參考文獻(xiàn)[17]用頂點的歸屬社區(qū)變化來合理地確定整個動態(tài)過程，但是，并沒有發(fā)現(xiàn)整個社區(qū)演化的事件，并且頂點的永久度和社區(qū)發(fā)現(xiàn)過程也是引用參考文獻(xiàn)[18]的思想。

參考文獻(xiàn)[19]根據(jù)增加、減少離群頂點，增加、減少邊，頂點從一個社區(qū)轉(zhuǎn)移到另一個社區(qū)的5種變化，判斷頂點的社區(qū)成員度的變化，從而判定頂點的歸屬社區(qū)，進而實現(xiàn)動態(tài)社區(qū)發(fā)現(xiàn)。

4.4 動態(tài)增量策略綜合比較

動態(tài)增量社區(qū)演化分為核心社區(qū)的動態(tài)演化、聚類的動態(tài)演化、指標(biāo)的動態(tài)演化3個部分，其區(qū)別在于核心社區(qū)的動態(tài)演化主要通過核心社區(qū)和擴展判定社區(qū)的演化，在時間復(fù)雜度上要優(yōu)于其他策略，但是從探索社區(qū)變化的細(xì)節(jié)和探索演化事件的準(zhǔn)確性方面，聚類和指標(biāo)的動態(tài)變化要高一些，但是依據(jù)參考文獻(xiàn)[14]中的思想，3種策略欠考慮社區(qū)內(nèi)部的結(jié)構(gòu)方面，本質(zhì)以邊作為研究對象，把所有的邊同等看待，在實際的網(wǎng)絡(luò)中表現(xiàn)的社區(qū)結(jié)構(gòu)并不明顯。動態(tài)增量社區(qū)演化策略綜合比較見表2，其中α為兩個時刻間的變化事件轉(zhuǎn)為頂點的變化比率。

5 社區(qū)演化預(yù)測

社區(qū)演化預(yù)測是歷史動態(tài)社區(qū)演化事件判定之后衍生出的新的研究熱潮，在已知歷史社區(qū)本身的特征和歷史社區(qū)演化事件的基礎(chǔ)上，如何探究接下來社區(qū)會發(fā)生怎么樣的演化事件，即社區(qū)演化預(yù)測。社區(qū)演化預(yù)測的思路具有代表性的是Stanislaw提出的參考文獻(xiàn)[20]，其他文獻(xiàn)在社區(qū)演化的思路方面和 Stanislaw大體一致，主要還是在時間片處理社區(qū)演化的基礎(chǔ)上衍生的課題，如參考文獻(xiàn)[21]預(yù)測演化事件的出發(fā)點在于不同的網(wǎng)絡(luò)，對不同時間片運用不同的靜態(tài)社區(qū)發(fā)現(xiàn)算法將導(dǎo)致最終不同的社區(qū)演化事件的預(yù)測準(zhǔn)確性。參考文獻(xiàn)[22]預(yù)測演化的周期，本質(zhì)而言就是判定下一時間片社區(qū)是否消失，從而確定社區(qū)演化周期。Stanislaw提出的社區(qū)演化預(yù)測思路如圖 6所示。

社區(qū)演化預(yù)測思想主要包括以下3個方面：

· 根據(jù)以上動態(tài)社區(qū)演化判定演化序列中兩社區(qū)間的演化事件；

·發(fā)現(xiàn)社區(qū)內(nèi)部的特征、社區(qū)間的特征和演化序列中兩個時間段的特征變化；

· 運用合理的機器學(xué)習(xí)方法進行分類預(yù)測。

5.1 特征選取

參考文獻(xiàn)[20]中的特征選擇主要是從社區(qū)整體特征、點特征、點特征量統(tǒng)計計算3個角度，社區(qū)整體特征包括社區(qū)的大小、社區(qū)內(nèi)點與點之間的連接密度、社區(qū)內(nèi)部的凝聚度、社區(qū)核心頂點、社區(qū)邊的相互作用；點特征包括點的入度、出度，連接頂點的最短路徑，點對應(yīng)的特征向量，頂點與其他社區(qū)內(nèi)頂點距離和；點特征量統(tǒng)計計算包括對點的所有特征進行求和、最小值、最大值、均值等運算。社區(qū)內(nèi)點與點之間的連接密度為：

表2 動態(tài)增量策略綜合比較

圖6 社區(qū)演化預(yù)測思路

當(dāng)頂點與頂點之間存在連接時，a(i,j)為1。社區(qū)內(nèi)部的凝聚力為：

其中，w(i,j)表示頂點i與頂點j組成邊的權(quán)值，n表示在社區(qū)內(nèi)的頂點數(shù)，N表示整個網(wǎng)絡(luò)內(nèi)的頂點數(shù)。社區(qū)邊的相互作用為：

其中，m表示整個網(wǎng)絡(luò)中的邊的數(shù)目，當(dāng)頂點i與頂點j之間存在連接時，a(i,j)為1。

參考文獻(xiàn)[21]中的特征選擇包括社區(qū)內(nèi)部的特征、社區(qū)間的特征和演化序列中兩個時間段的特征變化，社區(qū)內(nèi)部特征包括核心點的比例、核心點的度、核心點的凝聚度、核心點的特征向量；社區(qū)間的特征包括社區(qū)的大小、社區(qū)的凝聚度、社區(qū)聚類有效性、社區(qū)內(nèi)連接度、社區(qū)的度的均值、社區(qū)特征向量的均值；演化過程中兩個時間段的特征變化為以社區(qū)角度來考察對應(yīng)社區(qū)特征的變化。其社區(qū)聚類有效性為：

其中，#△表示在社區(qū)內(nèi)組成的三角形的數(shù)目，#Triples表示整個網(wǎng)絡(luò)中三角形的數(shù)目。社區(qū)內(nèi)連接度為：

其中，sh(u,v)表示社區(qū)內(nèi)兩點間組成的最短路徑。

5.2 分類預(yù)測

參考文獻(xiàn)[20]中獲取社區(qū)的特征后首先進行特征歸一化及篩選，然后運用了機器學(xué)習(xí)的分類算法 J48、RandomForest、AdaBoost、Bagging、Logistic進行訓(xùn)練，對數(shù)據(jù)集進行十折交叉驗證，得到預(yù)測模型，然后用模型對對應(yīng)時間片的社區(qū)進行預(yù)測。參考文獻(xiàn)[22]中提出了對每種事件分開進行訓(xùn)練，分別對每種事件進行判定預(yù)測準(zhǔn)確性，同時調(diào)用了weka的api對特征進行優(yōu)化選取和降維，分析社區(qū)特征對最終預(yù)測的重要程度。

由于社區(qū)網(wǎng)絡(luò)的復(fù)雜性、基于時間片硬分割分離的社區(qū)發(fā)現(xiàn)和相似度定義社區(qū)歷史演化事件的不合理性，發(fā)現(xiàn)社區(qū)事件會出現(xiàn)嚴(yán)重的偏移情況，社區(qū)消失的事件比其他社區(qū)事件要多很多，參考文獻(xiàn)[21]中提出了針對每個事件的進行weka中的SMOTE采樣，使訓(xùn)練樣本每個事件的訓(xùn)練樣本數(shù)目達(dá)到均值，然后對每個機器學(xué)習(xí)分類算法進行訓(xùn)練，這種策略沒有合理的依據(jù)，同時對于以上預(yù)測方法，都是將每個時間片的社區(qū)特征歸結(jié)在一起進行訓(xùn)練，沒有對每個時間片社區(qū)演化序列作為訓(xùn)練的對象，無形中缺少了社區(qū)演化序列間的時間特征。

6 結(jié)束語

介紹了動態(tài)社區(qū)演化的研究現(xiàn)狀和社區(qū)演化預(yù)測的相關(guān)工作。動態(tài)社區(qū)演化主要對當(dāng)今現(xiàn)存的主流的時間片處理策略和動態(tài)增量演化策略進行闡述，但是現(xiàn)今研究動態(tài)社區(qū)演化還處在單機處理階段。隨著大數(shù)據(jù)時代的來臨，更多的研究人員將對社區(qū)的動態(tài)演化過程進行分布式處理，提高整個演化計算的效率。同時，動態(tài)社區(qū)演化衍生出的社區(qū)演化預(yù)測還處于剛起步階段，沒有成熟的理論架構(gòu)基礎(chǔ)，如何建立有效預(yù)測模型和統(tǒng)一演化預(yù)測過程將成為未來的研究趨勢。

參考文獻(xiàn)：

[1]WANG L,CHENG X Q.Dynamic community online social network discovery and evolution [J].Chinese Journalof Computers,2015,38(2):219-237.

[2]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of sciences of United States of America,2002,99(12):7821-7826.

[3]PEI L,LAKSHMANAN L V S,MILIOS E E.Incremental cluster evolution tracking from highly dynamic network data[C]//IEEE International Conference on Data Engineering,March 31-April 4, 2014,Chicago,USA.New Jersey:IEEE Press,2014:3-14.

[4]BRóDKA P,SAGANOWSKIS,KAZIENKOP.GED:the method for group evolution discovery in social networks[J]. Social Network Analysis and Mining,2013,3(1):1-14.

[5]WU T,CHEN L,GUAN Y,et al.LPA based hierarchical community detection [C]//IEEE International Conference on Computational Science and Engineering,August 22-24,2014, Vancouver,Canada.New Jersey:IEEE Press,2014:185-191.

[6]ZHANG S,WANG R,ZHANG X.Identification of overlapping community structure in complex networks using fuzzy C-means clustering [J].Physics A:StatisticalMechanics and its Applications,2007,374(1):483-490.

[7]LANCICHINETTI A,FORTUNATO S,KERTéSZ J.Detecting the overlapping and hierarchical community structure of complex networks[J].New Journal of Physics,2009,11(3):19-44.

[8]TAKAFFOLI M,SANGI F,FAGNAN J.Community evolution mining in dynamic social networks[J].Procedia-Social and Behavioral Sciences,2011,22(22):49-58.

[9]WANG Y,WU B,DU N.Community evolution of social network: feature,algorithm and model[J].Physics,2008(3):31-46.

[10]LIN Y R,CHIY,ZHU S.Facetnet:aframework for analyzing communities and their evolutions in dynamic networks [C]//17th International Conference on World Wide Web,April 21-25,2008,Beijing,China.New York:ACM Press,2008:685-694.

[11]CHAKRABARTI D,KUMAR R,TOMKINS A.Evolutionary clustering[C]//12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,August 5-8,2011, Philadelphia,PA,USA.New Jersey:IEEE Press,2011:332-337.

[12]PALLA G,VICSEK T.Quantifying social group evolution[J]. Nature,2007,446(7136):664-7.

[13]PALLA G,BARABáSI A,VICSEK T.Community dynamics in socialnetworks [C]//SPIE 4th InternationalSymposium on Fluctuations and Noise,International Society for Optics and Photonics,July 2-August 10,2007,San Diego,USA.New Jersey:IEEE Press,2007:273-287.

[14]PRAT P,REZ A,DOMINGUEZ-SAL D,et al.Put three and three together:triangle-driven community detection [J].ACM Transactions on Knowledge Discovery from Data,2016,10(3): 1-42.

[15]LIU Y,GAO H,KANG X.Fast community discovery and its evolution tracking in time-evolving social networks[C]//IEEE International Conference on Data Mining Workshop,November 14-17,2015,Atlantic,NJ,USA.New Jersey:IEEE Press, 2015:13-20.

[16]FALKOWSKI T,BARTH A.Studying community dynamics with an incremental graph mining algorithm[C]//Learning from the Past& Charting the Future ofthe Discipline Americas Conference on Information Systems,August 14-17,2008,Toronto, Canada.New Jersey:IEEE Press,2008.

[17]LI X,WU B,GUO Q,et al.Dynamic community detection algorithm based on incremental identification [C]//IEEE International Conference on Data Mining Workshop,March 3-11, 2015,Toronto,Canoda,New Jersey:IEEE Press,2015:900-907.

[18]CHAKRABORTY T,SRINIVASAN S,GANGULY N.On the permanence ofverticesin network communities[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,August 24-27,2014,New York,NY,USA.New York:ACM Press,2014:1396-1405.

[19]LI J,HUANG L,BAI T.CDBIA:A dynamic community detection method based on incremental analysis [C]//International Conference on Systems and Informatics,May 19-21,2012,Yantai, China.New Jersey:IEEE Press,2012:2224-2228.

[20]SAGANOWSKI,STANISLAW.Predicting community evolution in social networks[J].Entropy,2015,17(5):3053-3096.

[21]SHAHRIM,GUNASHEKARS,DOMARVSMV,etal. Predictive analysis of temporal and overlapping community structures in social media [C]//International Conference Companion on World Wide Web,April 11-15,2016,Montreal, Canada.New Jersey:IEEE Press,2016.

[22]TAKAFFOLI M,RABBANY R,ZAIANE O R.Community evolution prediction in dynamic social networks[C]//IEEE/ACM InternationalConference on Advancesin SocialNetworks Analysis and Mining,August 17-20,2014,Beijing,China.New Jersey:IEEE Press,2014:9-16.

Research progress of dynamic community evolution

PAN Jianfei,XU Lili,DONG Yihong
Faculty of Electrical Engineering and Computer Science,Ningbo University,Ningbo 315211,China

Community structure is one of the topological characteristics of social network.It is an important research topic in social network research to explore the structure of community,detect and predict the change of community structure.The evolution of dynamic community was discussed from time slicing processing and dynamic increment strategies.The time slice processing strategy introduced the comparative evolution of the time slice,the clustering evolution of the time slice,and the fusion evolution of the time slice.The dynamic increment strategy described the dynamic evolution of the core community,the dynamic evolution of the cluster and the dynamic evolution of the index.Finally,the framework of community evolution prediction was summarized.

dynamic community mining,dynamic community evolution,dynamic community evolution prediction

TP391

A

10.11959/j.issn.1000-0801.2017026

潘劍飛（1991-），男，寧波大學(xué)信息科學(xué)與工程學(xué)院碩士生，主要研究方向為大數(shù)據(jù)、數(shù)據(jù)挖掘。

徐麗麗（1993-），女，寧波大學(xué)信息科學(xué)與工程學(xué)院碩士生，主要研究方向為大數(shù)據(jù)、數(shù)據(jù)挖掘。

董一鴻（1969-），男，博士，寧波大學(xué)信息科學(xué)與工程學(xué)院教授，主要研究方向為大數(shù)據(jù)、數(shù)據(jù)挖掘和人工智能。

2016-12-15；

2017-01-06

董一鴻，dongyihong@nbu.edu.cn

浙江省自然科學(xué)基金資助項目（No.LY16F020003）

Foundation Item:Zhejiang Provincial Natural Science Foundation of China(No.LY16F020003）