潘劍飛，徐麗麗，董一鴻

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

動(dòng)態(tài)社區(qū)演化研究進(jìn)展

潘劍飛，徐麗麗，董一鴻

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

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

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

1 引言

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

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

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

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

2 基本概念

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 基于時(shí)間片的比對(duì)演化

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

3．1．1 頂點(diǎn)比較策略

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

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

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

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

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

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

3．1．2 核心頂點(diǎn)比較策略

參考文獻(xiàn)[9]提出了如何獲取核心頂點(diǎn)的算法，核心頂點(diǎn)表示頂點(diǎn)的權(quán)值相比其他頂點(diǎn)更高，其中頂點(diǎn)的權(quán)值可以由頂點(diǎn)度、PageRank值等指標(biāo)來衡量。該算法和投票策略相似，對(duì)于每個(gè)頂點(diǎn)都有權(quán)去評(píng)估連接它的核心頂點(diǎn)，W（Ni）表示頂點(diǎn)Ni的度，如果W（Ni）的值越大，那么Ni點(diǎn)越重要。當(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ù)值時(shí)，Ni為核心頂點(diǎn)，否則為普通頂點(diǎn)。根據(jù)以上策略獲取到每個(gè)時(shí)間片的核心點(diǎn)，比較相鄰時(shí)間片內(nèi)核心點(diǎn)來確定演化社區(qū)序列。

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

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

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

在t時(shí)間片中的社區(qū)Ct中與t+1時(shí)間片社區(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|時(shí)，社區(qū) Ct

以社區(qū)Ct+1的形式在t+1時(shí)間片持續(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時(shí)間片只有社區(qū)Ct+1一個(gè)社區(qū)與之匹配時(shí)，社區(qū)Ct在t+1時(shí)間片縮減為社區(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時(shí)間片只有社區(qū)Ct+1一個(gè)社區(qū)與之匹配時(shí)，社區(qū)Ct在t+1時(shí)間片增長(zhǎng)為社區(qū)Ct+1；

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

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

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

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

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

3.2 基于時(shí)間片的聚類演化

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

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

3.3 基于時(shí)間片的融合演化

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

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

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

3.4 時(shí)間片策略綜合比較

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

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

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

表1 時(shí)間片處理策略綜合比較

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

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

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

圖3 FICET框架

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4 積極改變

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

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

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

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

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

圖5 消極的改變

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.1 特征選取

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

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

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

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

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

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

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

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

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

5.2 分類預(yù)測(cè)

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

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

6 結(jié)束語

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

參考文獻(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é)院碩士生，主要研究方向?yàn)榇髷?shù)據(jù)、數(shù)據(jù)挖掘。

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

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

2016-12-15；

2017-01-06

董一鴻，dongyihong@nbu.edu.cn

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

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