動態社區演化研究進展

潘劍飛，徐麗麗，董一鴻

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

動態社區演化研究進展

潘劍飛，徐麗麗，董一鴻

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

社區結構是社會網絡普遍存在的拓撲特性之一。挖掘社會網絡中的社區結構、探測并預測社區結構的變化是社會網絡研究中重要的研究課題。主要從時間片處理和動態增量的策略對動態社區演化進行闡述，時間片處理策略介紹了時間片的對比演化、聚類演化、融合演化的研究方法；動態增量策略描述了核心社區、聚類、指標的動態演化的研究方法；最后對社區演化預測的框架進行了歸納總結。

動態社區挖掘；動態社區演化；動態社區演化預測

1 引言

社會網絡是邊與點的連接組成的圖，通過對社會網絡的研究，發現社會網絡呈現一種內部頂點連接緊密、外部頂點連接松散[1]的結構，即社區結構。社區結構對深入理解和研究社會網絡的性質具有很重要的意義，因此社區研究將成為真實社會網絡分析的一個重要的研究方向。

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

當前對社區結構的研究主要集中針對于靜態網絡中的挖掘算法設計，隨著研究的深入，研究者開始關注復雜動態網絡中演化社區結構的識別分析。社區結構識別也正經歷從靜態研究向動態演化分析的轉變，動態網絡演化社區結構識別的研究逐步成為研究的熱點。

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

2 基本概念

定義1 （時間片）動態網絡Gt:t+n按時間段分，可表示為{Gt,Gt+1,…,Gt+n}，Gt=（Vt,Et）為 t時間段的網絡。

定義2 （時間片社區）對每個時間段的網絡Gt=（Vt, Et）,t=1,2,3,…進行社區發現得 Gt={Ct1,Ct2,…,Ctn},Ctn表示在t時間段的網絡中發現的第n個社區。

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

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

定義 5 （社區演化事件[4]）對復雜動態網絡而言，當網絡動態變化時，網絡中的社區可能隨時間推進而發生持續、縮減、增長、分離、融合、消失、生成等事件，這些事件將導致社區的結構形態發生動態變化，以下對各個事件進行介紹：

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

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

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

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

·消失事件表示隨時間推進過程中，對應的社區結構消失，如圖1（f）所示；

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

·生成事件表示隨時間推進過程中，新的社區結構出現，如圖1（i）所示。

圖1 社區演化事件

3 時間片處理社區演化

時間片處理社區演化是指社區數據按時間段獲取形成動態時間片數據，然后以整個時間片為研究單位，對時間片進行分離、聚類或融合等處理后，用靜態社區發現算法或靜態聚類思想分離出對應的社區，并探索相鄰時間片內社區之間的變化，如圖2所示。

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

圖2 時間片分解社區

3.1 基于時間片的比對演化

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

3．1．1 頂點比較策略

[8]提出在t時間片社區Ct與t+1時間片社區Ct+1間，頂點變化衡量相似性的比較標準為：

基于此比較標準，結合元社區和二分匹配的方法得到社區演化序列和演化事件。

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

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

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

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

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

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

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

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

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

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

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

· 當I（Ct+1,Ct）≥α，I（Ct+1,Ct）≥β，|Ct|=|Ct+1|時，社區 Ct

以社區Ct+1的形式在t+1時間片持續；

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

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

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

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

· 當在t+1時間片的每一個社區Ct+1，I（Ct,Ct+1）＜10%，I（Ct+1,Ct）＜10%時，社區Ct在t+1時間片消失；

· 當在t時間片的每一個社區Ct，I（Ct,Ct+1）＜10%，I（Ct+1,Ct）＜10%時，社區Ct+1在t+1時間片生成。

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

3.2 基于時間片的聚類演化

基于時間片聚類的演化是在靜態聚類分析算法的基礎上，提出了一個動態演化聚類思想。參考文獻[10]中提出社區在相鄰時間片間的變化應該不大，對此在考察t時間片內的社區Ct時，既要滿足當前t時間片內在的結構，同時用t-1時間片來規整t時間片的社區，并且提出一種衡量t時間片社區Ct質量的標準，可以表示為：

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

3.3 基于時間片的融合演化

基于時間片融合的演化是將相鄰時間片的網絡數據進行融合，并對融合后的數據進行靜態社區發現后，與前一時間片的社區結構進行相似性比較和判定歸屬分離出當前時刻的社區結構。

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

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

3.4 時間片策略綜合比較

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

4 動態增量社區演化

動態增量社區演化是指根據初始時刻網絡的社區，隨時間的變化更新社區結構，從而發現動態社區演化序列和事件。相比于時間片處理的社區演化，動態增量的社區演化充分利用了前次識別的結果，在前次的結果上進行動態判定，真正實現了動態識別和演化。

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

4.1 基于核心社區的動態演化

基于核心社區的動態演化的思想在于首先判定核心點組成的核心社區的動態變化，然后擴展為整個網絡的社區變化。

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

圖3 FICET框架

整個框架的思想主要分為兩個步驟：社區的發現和核心社區動態增量演化擴展。社區發現是動態增量演化的基礎，隨后的演化都是在此基礎上的。社區發現分為3個步驟。

步驟 1 通過改變后的PageRank（modified weighted pagerank，MP）算法，發現網絡的核心點、連接邊組成核心的子圖。利用改進后的MP算法求PageRank值：

步驟 2 對核心的子圖，運用高層聚類（high-level clustering,HC）算法發現核心的社區集。其中HC算法中引入適應度函數來作為核心社區形成標準：

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

社區發現后，將經歷核心社區動態增量演化擴展的過程，增量演化運用增量 （incremental community evolution, IC）算法對前一時刻的核心社區進行增量變化來發現當前核心社區。同時引入社區結構穩定參數（community structure stability，CSM）來防止數據漂移的情況。擴展過程和社區發現的擴展過程一致。其中，IC算法考慮核心頂點集和對應的邊集的變化：

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

快速增量社區演化跟蹤框架體現了動態增量社區演化的本質思想由t時刻核心點的社區來指導t+1時刻核心社區的發現和核心社區演化，然后對演化后核心社區通過擴展算法來獲取整個網絡內的社區結構。追蹤社區演化針對核心點社區的動態變化，既能保證演化的準確性，也能快速跟蹤社區演化的過程。但是，核心社區擴展的過程采用的是頂點強硬社區分配，不能對重疊社區進行發現，同時社區結構穩定參數不夠合理。

4.2 基于聚類的動態演化

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

參考文獻 [16]中基于靜態密度聚類思想提出了DENGRAPH的算法。動態演化的過程，考慮積極的改變和消極的改變兩個方面。積極的改變為考慮新的核心頂點、新的邊界頂點、新的鄰接頂點添加時導致原本社區的變化。

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

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

·新的鄰接頂點，將其添加到鄰接的社區，并且更新社區內的強度。

積極的改變可產生社區的生成、增長和融合事件，如圖4所示。

圖4 積極改變

消極的改變為考慮核心頂點、鄰邊頂點、邊界頂點和核心頂點的邊，核心頂點間邊消失時導致原本社區的變化。

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

· 鄰接頂點的消失，當鄰邊頂點為邊界頂點時，更新社區的強度。

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

· 連接核心頂點邊的消失，兩個核心頂點將不可達，可能產生社區間的分離事件發生消極的改變可產生社區的消失、縮減和分離的事件，如圖5所示。

圖5 消極的改變

采用聚類的思想進行動態社區演化發現，方法簡易，能根據靜態聚類對應的參數和頂點變化來判定社區的變化和對應的社區事件更具合理性，而且能細化到每個細節的變化可能導致的社區演變事件。

4.3 基于指標的動態演化

基于指標的動態演化的思想主要在于通過點、邊社區內和社區間的變化，設定頂點的指標判定頂點歸屬社區，從而衡量社區的動態演化過程。

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

社區演化強度本質而言就是不斷累加社區點邊變化的強度，如果變化強度超過一定范圍就認為社區演化可能產生數據漂移現象，應當重新進行社區發現的過程來防止社區演化異常，這是演化事件累積指標，并不能明確指出當前是否已經發現偏移情況。其頂點的永久度可表示為：

頂點的永久度考慮兩個方面：一個方面是社區頂點的社區內連接和社區外連接比，另一個方面是社區內部結構的結構有效度。

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

參考文獻[19]根據增加、減少離群頂點，增加、減少邊，頂點從一個社區轉移到另一個社區的5種變化，判斷頂點的社區成員度的變化，從而判定頂點的歸屬社區，進而實現動態社區發現。

4.4 動態增量策略綜合比較

動態增量社區演化分為核心社區的動態演化、聚類的動態演化、指標的動態演化3個部分，其區別在于核心社區的動態演化主要通過核心社區和擴展判定社區的演化，在時間復雜度上要優于其他策略，但是從探索社區變化的細節和探索演化事件的準確性方面，聚類和指標的動態變化要高一些，但是依據參考文獻[14]中的思想，3種策略欠考慮社區內部的結構方面，本質以邊作為研究對象，把所有的邊同等看待，在實際的網絡中表現的社區結構并不明顯。動態增量社區演化策略綜合比較見表2，其中α為兩個時刻間的變化事件轉為頂點的變化比率。

5 社區演化預測

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

社區演化預測思想主要包括以下3個方面：

· 根據以上動態社區演化判定演化序列中兩社區間的演化事件；

·發現社區內部的特征、社區間的特征和演化序列中兩個時間段的特征變化；

· 運用合理的機器學習方法進行分類預測。

5.1 特征選取

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

表2 動態增量策略綜合比較

圖6 社區演化預測思路

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

其中，w(i,j)表示頂點i與頂點j組成邊的權值，n表示在社區內的頂點數，N表示整個網絡內的頂點數。社區邊的相互作用為：

其中，m表示整個網絡中的邊的數目，當頂點i與頂點j之間存在連接時，a(i,j)為1。

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

其中，#△表示在社區內組成的三角形的數目，#Triples表示整個網絡中三角形的數目。社區內連接度為：

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

5.2 分類預測

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

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

6 結束語

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

參考文獻：

[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-），男，寧波大學信息科學與工程學院碩士生，主要研究方向為大數據、數據挖掘。

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

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

2016-12-15；

2017-01-06

董一鴻，dongyihong@nbu.edu.cn

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

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