端祥宇，袁 冠，2+，孟凡榮

1.中國礦業(yè)大學計算機科學與技術學院，江蘇徐州 221116

2.礦山數字化教育部工程研究中心，江蘇徐州 221116

復雜網絡是對復雜系統(tǒng)進行抽象。其中節(jié)點是代表復雜系統(tǒng)中的個體，節(jié)點之間的邊表示個體之間根據某種規(guī)則形成的聯系。隨著社交平臺的多元化發(fā)展，社交媒體用戶不斷增加，社交網絡已經逐漸成為最具挖掘價值的復雜網絡之一。社交網絡的一個重要特征是社區(qū)結構。雖然社區(qū)的概念依然沒有一個明確的定義[1]，但多數文獻中都認為社區(qū)是對網絡的分解與劃分，將網絡劃分成多個集合，集合內部的節(jié)點連接密集，集合之間連接稀疏[2]，使得社區(qū)具有高內聚、低耦合的特性。

社區(qū)發(fā)現是研究網絡社區(qū)結構必不可少的技術，采用有效方法將社交網絡中潛在的社區(qū)挖掘出來。目前，對社區(qū)發(fā)現方法的研究越來越多，在DBLP（database systems and logic programming）上以community detection 為關鍵詞搜索公開發(fā)表的相關論文，可以發(fā)現學術界對社區(qū)發(fā)現的研究成遞增趨勢，社區(qū)發(fā)現已經逐步成為復雜網絡分析中的重點研究方向之一（如圖1 所示）。通過對社交網絡進行社區(qū)發(fā)現，可以分析社區(qū)結構、計算節(jié)點影響力、尋找核心節(jié)點、進行興趣推薦等。

Fig.1 Papers on community detection published in DBLP from Jan.2011 to Oct.2020圖1 2011.01—2020.10關于社區(qū)發(fā)現論文的統(tǒng)計（DBLP）

社交網絡的社區(qū)發(fā)現算法主要分為靜態(tài)社區(qū)發(fā)現方法和動態(tài)社區(qū)發(fā)現方法。目前關于復雜網絡的社區(qū)發(fā)現方法的研究主要集中在靜態(tài)方法。傳統(tǒng)的靜態(tài)社區(qū)發(fā)現一般分為兩類，一類是非重疊社區(qū)發(fā)現，另一類則是重疊社區(qū)發(fā)現。前者使得網絡中的每個節(jié)點僅屬于一個社區(qū)，不存在任何節(jié)點同時屬于兩個或兩個以上社區(qū)的情況[3]，而后者則相反。非重疊社區(qū)發(fā)現算法主要包括基于圖分割的算法[4-6]、基于層次聚類的方法[2，7-8]、基于模塊度（modularity，Q）的優(yōu)化算法[9-10]、基于標簽傳播的算法[11]、基于模型推斷的方法[12]等。重疊社區(qū)發(fā)現算法主要包括基于團過濾的方法[13-15]、基于邊劃分的方法[16]、基于局部擴展的方法[17]、基于模糊檢測的算法[18]、基于馬爾可夫鏈的方法[19]等。

多數復雜網絡中節(jié)點和邊的數量隨時間動態(tài)變化，因此動態(tài)社區(qū)發(fā)現逐漸成為研究社區(qū)結構的主要方向。社交網絡具有交叉性和時序性，即隨著時間的推移，不同的社區(qū)的節(jié)點和邊相互交叉變化，部分節(jié)點和邊的增加與刪除，會導致一些社區(qū)出現消失、增長、收縮、合并等現象，從而影響社交網絡的質量[20]。常見的動態(tài)社區(qū)發(fā)現方法有基于經典聚類方法的社區(qū)發(fā)現、基于動力學的社區(qū)發(fā)現、基于統(tǒng)計模型的社區(qū)發(fā)現以及基于啟發(fā)式方法的社區(qū)發(fā)現方法（詳細介紹見第2 章）。

動態(tài)社區(qū)發(fā)現具體研究框架如圖2 所示。

1 相關工作

本章首先介紹相關符號的定義，然后通過網絡級別的行為演化和節(jié)點級別的行為演化分析目前主要動態(tài)社區(qū)發(fā)現的研究方法。

1.1 相關定義

Fig.2 Framework of dynamic community detection圖2 動態(tài)社區(qū)發(fā)現結構圖

定義1（復雜網絡）復雜網絡可用圖G=(V,E)表示，其中V代表節(jié)點的集合，E代表邊的集合。邊e=(u,v)∈E表示兩個節(jié)點u,v∈V之間的相互聯系。復雜網絡的社區(qū)發(fā)現本質上是對圖中的節(jié)點進行聚類劃分，n表示節(jié)點數量，m表示邊的數量。與節(jié)點v關聯的邊的數目稱為節(jié)點v的度，記為d。

定義2（動態(tài)網絡）動態(tài)網絡G可以由一系列離散的快照網絡表示，即G={G0,G1,…,GT}，其中T表示劃分的快照網絡的數量?？煺站W絡Gt=(Vt,Et)，0 ≤t≤T表示節(jié)點集V和邊集E在當前時間t出現的快照圖。

定義3（動態(tài)社區(qū)）動態(tài)社區(qū)發(fā)現是在連續(xù)的時間快照中找到一系列相似的社區(qū)。動態(tài)社區(qū)可以看作是由按照時間快照時序排列的社區(qū)集合組成，即C={C0,C1,…,Ct,…,CT},t∈T,0 ≤t≤T。在第t時刻的快照網絡中檢測到的k個社區(qū)可以表示為,0 ≤s≤k。文中使用的部分符號如表1 所示。

Table 1 Notions and descriptions表1 符號及描述

1.2 動態(tài)社區(qū)演化

關于社區(qū)的動態(tài)演化，Qiu 等[21]提出了事件驅動的網絡建?？蚣堋；谠摽蚣茉O計了一個基于事件驅動的演化增長模型，融合節(jié)點的度（依附）和節(jié)點間的距離（位置）作為動態(tài)社區(qū)演化的參考因素。他們還提出了網絡級的行為演化以及節(jié)點級的行為演化兩種概念，是社區(qū)的動態(tài)演化的重要參考。

1.2.1 網絡級行為演化

網絡級的行為演化是指在社區(qū)范圍內定義社區(qū)的變化行為，稱為“事件（event）”[22]。有多項研究[7，23-25]定義了在網絡演化過程中出現的相關事件。圖3 所示是Dakiche 等[22]綜合上述文獻后，對事件定義進行的簡化。

出生（birth），在特定時間形成一個新社區(qū)。

消失（death），一個社區(qū)消失。

增長（growth），社區(qū)有一些新成員（節(jié)點）加入。

收縮（shrink），一個社區(qū)失去一些成員。

合并（merge），幾個社區(qū)合并形成一個新社區(qū)。

拆分（split），將一個社區(qū)劃分為幾個新社區(qū)。

重現（resurgence），一個社區(qū)消失一段時間后重新出現。

Fig.3 Evolution of events over time圖3 隨時間發(fā)展的事件的演化過程

Asur 等[23]設計了一個基于事件的框架來描述交互網絡的演變，并對社區(qū)之間的拆分、合并、連續(xù)、形成和消失等關鍵事件進行定義，同時又關注于節(jié)點在社區(qū)中出現、消失、加入、離開等行為的定義。該框架將演化過程中社區(qū)和節(jié)點行為相結合，分析了合著者網絡和臨床數據網絡中的相關社區(qū)和主題演變，取得了良好的效果。但是該方法分配事件的條件過于嚴格，容易導致部分事件難以識別。Bródka等[24]引入收縮和增長等事件的定義，設計了基于組演化的社區(qū)發(fā)現方法，使用決策樹將“組”的類型與事件進行匹配，解決了上述問題并提高了社區(qū)發(fā)現的速度。該方法比Asur等[23]方法快50 倍以上。

Cazabet 等[26]提出iLCD（intrinsic longitudinal community detection）算法，根據網絡拓撲結構的變化，對前一個快照網絡的社區(qū)進行更新、合并、生成新社區(qū)來發(fā)現當前快照網絡的社區(qū)結構。該算法能夠在動態(tài)網絡中進行重疊社區(qū)發(fā)現。Zhao 等[27]將網絡中隨時間改變的部分定義為增量元素，并認為各種子圖組成增量元素，根據子圖之間的關系和先前時間片中社區(qū)的關系，將其分為完全獨立、完全包含、混合新舊節(jié)點以及多包含等四種類型的子圖，并通過判斷增量元素類型從而更新社區(qū)或形成新的社區(qū)，用于動態(tài)發(fā)現社區(qū)。

Gao 等[28]提出了基于領導者節(jié)點的演化社區(qū)發(fā)現算法，通過Top Leader 社區(qū)發(fā)現算法將初始網絡進行劃分后，對社區(qū)進行分裂以及合并操作。Xin 等[29]將網絡分為生成、分裂、合并和生存4 種群落演化，并使用相應算法分別對4 種演化進行研究。He 等[30]通過將大型網絡分解，構造出小型網絡，提升社區(qū)發(fā)現的準確性和速度。

Gou 等[31]關注社區(qū)的擴展和合并，設計了動態(tài)加權網絡中的演化社區(qū)結構發(fā)現算法，但是該算法的缺陷在于每個演化步驟中都需要人為設定閾值，不同的閾值設定對算法的結果具有較大的影響。張高禎等[32]借鑒模塊度優(yōu)化算法的思想，解決了上述問題，并對Guo 等[31]算法中擴展社區(qū)、合并社區(qū)的步驟進行了優(yōu)化，最終在模塊度質量上優(yōu)于上述算法。

1.2.2 節(jié)點級行為演化

節(jié)點級的行為演化主要從節(jié)點變化的角度來探索動態(tài)網絡中社區(qū)的相關變化，包括以下四種情況：

（1）節(jié)點增加，新的節(jié)點加入當前網絡；

（2）節(jié)點減少，一些現有節(jié)點離開當前網絡；

（3）邊增加，一些節(jié)點之間建立新的聯系；

（4）邊減少，一些節(jié)點之間斷開現有聯系。

Agarwal等[33]就是將節(jié)點級的行為演化融入到算法之中，將算法分為節(jié)點添加、節(jié)點刪除、邊添加和邊刪除四種情況及對應方法。Cordeiro 等[34]關注于新增或刪除的節(jié)點和邊所在的社區(qū)，運用局部模塊度最大化思想，僅對改變的元素重新劃分社區(qū)，不對其他元素進行操作，大大提升了運行效率。

郭昆等[35]將當前時間的新增節(jié)點、消失節(jié)點以及鄰居變化節(jié)點等定義為增量節(jié)點。通過節(jié)點的變化和節(jié)點間的距離來調整生成新社區(qū)。Duan 等[36]通過k-團過濾算法將初始網絡劃分成k個團，通過分析團與團之間邊和節(jié)點的增減，使用局部深度優(yōu)先搜索森林更新技術，以及增量k-clique算法進行聚類。

蔣盛益等[37]同樣關注于節(jié)點行為的演化，提出一種基于增量式譜聚類的動態(tài)社區(qū)自適應發(fā)現算法，采用歸一化圖形拉普拉斯矩陣，以上一個時間片網絡的社區(qū)特征為基礎，采用調整的鏈接相關線性譜聚類進行動態(tài)社區(qū)發(fā)現。Ning 等[38]同樣提出了一種基于譜聚類的動態(tài)網絡社區(qū)發(fā)現算法，將動態(tài)網絡的變化分為節(jié)點之間相似度的變化和增刪節(jié)點，并用關聯向量和關聯矩陣表示動態(tài)變化，通過增量譜聚類算法得到動態(tài)網絡的社區(qū)結構。

Xie 等[39]專注于追蹤快照圖中由于邊的改變而造成變化的節(jié)點，提出一種用于動態(tài)社區(qū)發(fā)現的增量標簽傳播算法。文中采用標簽傳播算法對快照網絡進行迭代更新。該算法在加權網絡和有向網絡上具有更好的普適性。Xin 等[40]使用一種自適應隨機游走采樣的動態(tài)社區(qū)發(fā)現算法來實現對動態(tài)網絡社區(qū)的更新，從節(jié)點級行為演化角度將網絡的變化進行劃分，將網絡中的產生變化的節(jié)點及其相鄰節(jié)點、與產生變化的邊所連接的節(jié)點加入到隊列中，用隨機游走采樣算法對隊列中節(jié)點進行計算，從而完成社區(qū)的更新，提高了社區(qū)發(fā)現效率。

2 動態(tài)社區(qū)發(fā)現方法

動態(tài)社區(qū)發(fā)現方法可以分為四種，分別是基于經典聚類方法、基于動力學的方法、基于統(tǒng)計模型的方法以及基于啟發(fā)式的方法。表2 對典型動態(tài)社區(qū)發(fā)現的論文、采用的算法以及時間復雜度進行了總結歸納。主要參數p表示算法的迭代次數，l表示局部搜索迭代的次數，x、y是常量。

Table 2 Introduction of dynamic community detection methods表2 動態(tài)社區(qū)發(fā)現方法的介紹

2.1 基于經典聚類方法的社區(qū)發(fā)現

經典聚類方法，如密度聚類[35，41-42]、譜聚類[43-44]、派系過濾算法[36]等常應用于靜態(tài)社區(qū)發(fā)現中。本節(jié)主要探討經典聚類算法與動態(tài)社區(qū)發(fā)現的結合。

郭昆等[35]利用基于密度的方法發(fā)現社區(qū)增量變化過程。首先，基于改進后的DBSCAN（density-based spatial clustering of applications with noise）生成初始社區(qū)，并根據邊變化率和余弦相似度確定相鄰時刻下發(fā)生變化的鄰居節(jié)點，同時根據節(jié)點的直接鄰居和間接鄰居的影響，調整鄰居節(jié)點的社區(qū)歸屬。最后，通過迭代更新模塊度增益實現社區(qū)合并，以及更新當前社區(qū)。方法在Enron 和人工數據集上有出色表現。

朱騰云[41]首先利用邊密度在靜態(tài)網絡中識別相關社區(qū)，然后依據靜態(tài)算法提出基于邊密度和改進模塊度的增量動態(tài)社區(qū)算法。利用靜態(tài)算法生成初始社區(qū)，并根據相鄰時刻增量對鄰居節(jié)點社區(qū)歸屬度的影響進行計算，結合網絡的歷史拓撲結構在Enron 和人工數據集上進行社區(qū)發(fā)現，結果表明其效果在標準化互信息（normalized mutual information，NMI）和運行速度上優(yōu)于傳統(tǒng)算法。

Sun 等[42]提出了基于增量的密度聚類算法Inc-Order。算法分為在線和離線兩部分。在線階段中，通過引入核心連接相似性的概念，從動態(tài)網絡中構造基于密度聚類的核心連接鏈，并實時維護該連接鏈。離線階段則是從核心連接鏈中提取所有高于相似度閾值的結果序列，使用模塊度優(yōu)化的方法從序列中提取社區(qū)。該算法在靜態(tài)和動態(tài)數據集的劃分上取得了很好的效果。Qin 等[43]提出了一種多相似譜聚類方法，將快照網絡構造為多個相似性矩陣。為了保持相鄰快照之間的演化的動態(tài)性，該方法采用動態(tài)協同訓練方法來進行不同相似性度量聚類，這能夠保留社區(qū)結構的歷史信息。此外，他們還提出一種自適應方法來估計目標中的時間平滑參數。算法在真實數據集和人工數據集上的NMI 值高于對比算法，而誤差平方和低于對比算法，具有良好的動態(tài)社區(qū)劃分性能。Liu 等[44]提出全局譜聚類的概念，將當前網絡與前后時間網絡的前導特征向量平滑連接，目的在于通過合并有關網絡演化的可用信息來改善社區(qū)發(fā)現方法。又設計一種全局社區(qū)發(fā)現方法，采用特征向量的平滑性建立連續(xù)社區(qū)，并且通過演化譜聚類和度校正的方法將時序網絡中的信息聚類，用于增強對各個時間片的推斷。算法在恒河猴大腦基因表達數據上展示了優(yōu)良的性能，為分析恒河猴的相關習性提供了有力支持。

Duan 等[36]設計增量k-團聚類算法對動態(tài)網絡進行社區(qū)發(fā)現。方法采用變化流模型，將派系過濾算法應用深度優(yōu)先遍歷森林進行改進。從節(jié)點級行為演化角度出發(fā)，進行動態(tài)社區(qū)發(fā)現。該算法在DBLP和Enron 數據集上的運行速度較相應靜態(tài)算法有很大的提升。但該算法的缺點在于需要設置固定系數，并且在實驗中僅選取運行時間作為評價標準，無法確定最終生成的社區(qū)結構的質量。

2.2 基于動力學的社區(qū)發(fā)現

復雜網絡與圖論的區(qū)別在于圖論僅僅只是研究網絡的靜態(tài)結構，而復雜網絡還具有動力學特性。隨機游走、游客漫步、流行病傳播等都是網絡的動力學過程。在這些動力學過程中，也有不少用于動態(tài)社區(qū)發(fā)現的方法，如馬爾可夫聚類[23]、隨機游走方法[29，40，45]和標簽傳播算法[39，46-47]等。

Asur 等[23]提出了一種基于匹配方法的社區(qū)事件識別算法，主要采用位運算對時序社區(qū)成員矩陣進行計算，大大減少了運行時間。采用馬爾可夫聚類算法對快照網絡進行社區(qū)劃分，在連續(xù)快照中比較了每個可能社區(qū)對的大小和重疊性，并確定這些社區(qū)的事件。該方法在DBLP 數據集和臨床實驗數據集的特征描述和事件推理中具有較好的性能。同時為鏈接預測場景中的應用提供了良好的結果。

Xin 等[29，40]提出自適應隨機游走采樣（adaptive random walk sampling，ARWS）方法，進行動態(tài)社區(qū)發(fā)現。隨機游走采樣方法解決了由固定隨機游走引起的不穩(wěn)定性問題，實現了對象的非均勻隨機游走。此外，還采用ARWS 算法使受影響的節(jié)點自適應地找到新近的鄰居和變化的社區(qū)。ARWS 采用局部社區(qū)發(fā)現與動態(tài)自適應調整相結合的方法，僅在動態(tài)事件發(fā)生時來更新受到影響的節(jié)點和社區(qū)。但是算法具有過多的參數，不同參數值對社區(qū)發(fā)現結果影響較大。

Jdidia 等[45]對Infocom 會議的共同作者網絡進行了分析。他們從不同的快照構建一個網絡，并使用經典的社區(qū)發(fā)現算法Walktrap[48]進行社區(qū)發(fā)現，同時引入Infocom 會議委員會成員來進行數據分析。Xie等[39]在標簽傳播算法LabelRank[49]的基礎上提出了一種增量算法LabelRankT。網絡更新后，算法重新初始化已更改節(jié)點的標簽，并重新應用LabelRank 算法來更新標簽概率分布。真實網絡上的結果表明，LabelRankT 的計算成本遠低于同類算法，并且提高了網絡結構的質量。

Liu 等[46]提出了一種基于標簽傳播算法的動態(tài)網絡演化聚類新方法。每個節(jié)點的社區(qū)標簽由其鄰居確定，同時采用與網絡結構相關的特殊順序來更新節(jié)點標簽，并且為每個標簽分配一個歸屬因子，其中節(jié)點標簽之一被視為主要社區(qū)，其他標簽被視為次要社區(qū)的一部分。通過迭代更新節(jié)點標簽，每個節(jié)點最后可以保留一個或多個社區(qū)標簽。這樣能夠檢測動態(tài)網絡中不重疊和重疊的社區(qū)。該算法在真實網絡上的靜態(tài)和動態(tài)的社區(qū)劃分均表現良好。

Sattari 等[47]提出了一種基于標簽傳播算法和級聯信息擴散模型的方法用來發(fā)現重疊社區(qū)。首先為每個節(jié)點分配一個標簽，計算節(jié)點鄰居的強度，并根據強度決定每個節(jié)點的兩個狀態(tài)，這兩個狀態(tài)可以根據節(jié)點的影響度或不影響度來區(qū)分節(jié)點。然后計算鄰居投票的最大標簽并發(fā)送給節(jié)點，根據歸屬因子劃分社區(qū)。該算法在真實數據集和人工數據集上都有很好的劃分性能，模塊度和標準化互信息均高于對比算法，但是在運行速度上慢于其對比方法。

2.3 基于統(tǒng)計模型的社區(qū)發(fā)現

基于統(tǒng)計模型的社區(qū)發(fā)現主要包括三種方法[50]：一是使用或擴展隨機塊模型[51-52]，采用最大似然估計對模型進行優(yōu)化；二是利用矩陣分解來解決社區(qū)發(fā)現問題[53-57]；三是基于深度學習的社區(qū)發(fā)現模型[58]。

Xu 等[51]將靜態(tài)網絡隨機塊模型擴展到動態(tài)網絡中，提出了一種狀態(tài)空間模型。作者在初始時刻使用譜聚類進行社區(qū)發(fā)現，并且將擴展的卡爾曼濾波器和局部搜索策略組合，這樣能夠以接近最佳的方式擬合模型。Yang 等[52]將隨機塊模型在時間信息上進行擴展，使用轉換矩陣明確地建立了節(jié)點隨時間變化的模型，該轉換矩陣指定了對于所有在時間t的i類節(jié)點在t+1 時刻轉換為j類的概率，并將Gibbs 采樣和模擬退火算法結合來擬合模型。該方法對Enron 數據集進行分析，并結合實際情況對比，最終該算法能夠獲得較好的推斷結果。

Wang 等[53]提出了動態(tài)貝葉斯非負矩陣因式分解概率模型，這屬于具有概率解釋的演化聚類方法。該模型不僅可以基于每個快照網絡中節(jié)點的概率成員資格來給出重疊的社區(qū)結構，而且可以基于自動相關性來自動確定每個快照網絡中的社區(qū)數量。文章又提出一種基于乘法更新規(guī)則的梯度下降算法用來優(yōu)化目標函數。該算法在動態(tài)合成網絡和一些真實時間網絡上具有更好的性能。

Lin 等[54]提出了FacetNet（a framework for analyzing communities and evolutions in dynamic networks）框架，將社區(qū)結構分析和演化相統(tǒng)一，并考慮到歷史社區(qū)結構對當前社區(qū)的影響。該框架能夠發(fā)現同時使觀測數據和時間演變的擬合最大化的社區(qū)，并且以非負矩陣分解的方式統(tǒng)一分解了社區(qū)及其演化，并且提出了一種具有較低的時間復雜度迭代算法，可以保證獲得局部最優(yōu)解。FacetNet 在合成網絡和真實網絡中具有很快的處理速度，有較好劃分結果，但其劃分結果的質量依賴于網絡中社區(qū)的數目。

Gao 等[55]提出了一種使用非負矩陣分解的新型動態(tài)社區(qū)檢測模型（evolutionary nonnegative matrix factorization，ENMF），該模型通過引入轉移矩陣，將復雜網絡的動力學與時間成員信息相結合用以檢測社區(qū)結構，可以在保證檢測社區(qū)的質量的情況下跟蹤時間演化。但是該框架的缺陷在于假設社區(qū)及其節(jié)點的數量不會隨時間的發(fā)展而變化，與現實的社交網絡的變化有較明顯的差距。

Ma 等[56]提出了兩個用于檢測動態(tài)社區(qū)的演化非負矩陣分解框架，該框架中保留了聚類質量和聚類成員資格。文章首先證明了ENMF、演化模塊密度和演化譜聚類優(yōu)化之間是等價的，并根據等價性來擴展理論。接著提出了一種結合ENMF和譜聚類的半監(jiān)督的ENMF，將先驗信息集成到算法的目標函數中，能夠在不增加時間復雜度的情況下選擇局部最優(yōu)解。此外，Ma等[57]又進一步提出了圖正則化演化非負矩陣分解（graph regularized evolutionary nonnegative matrix factorization algorithm，GrENMF）算法進行動態(tài)社區(qū)發(fā)現。該算法將時間成本引入到算法的總體目標函數作為正則化器，用于平衡快照成本與時間成本。同時文中又證明了GrENMF 與ENMF、演化譜、Kmeans 和模塊度密度算法是等價的。算法實施到三個人工數據集和兩個真實世界數據集中，表明該算法沒有增加額外的時間復雜度。

Ma 等[58]提出了一種社區(qū)感知的動態(tài)網絡嵌入方法（community-aware dynamic network embedding method，CDNE），并且實施在合成網絡和真實網絡中，并且都取得了較好的性能。該算法首先將動態(tài)網絡嵌入問題建模為使整體損失函數最小化，采用Genlouvain[59]進行社區(qū)結構的發(fā)現，使用K-means 將其分為小社區(qū)，采用堆疊式深度自編碼器算法來解決最小化問題，從而獲得節(jié)點的低維表示。又提出了一種社區(qū)感知平滑技術，采用了時間正則化來保持動態(tài)網絡中社區(qū)的平滑動態(tài)。CDNE 對兩個合成網絡和九個現實世界動態(tài)網絡進行分析，結果表明在網絡重建、鏈路預測、網絡穩(wěn)定和社區(qū)穩(wěn)定方面都具有較好的性能。

2.4 基于啟發(fā)式算法的社區(qū)發(fā)現

啟發(fā)式算法基于優(yōu)化的思想，將隨機算法與局部搜索算法相結合。社區(qū)發(fā)現算法中主要采用遺傳算法[60]、粒子群優(yōu)化算法[61-62]、模塊度優(yōu)化[30，34，59，63]。

Niu 等[60]將動態(tài)社區(qū)發(fā)現轉化為一個多目標優(yōu)化問題，設計了一種基于標簽的動態(tài)多目標遺傳算法，用來檢測具有最大化快照質量和最小化時間成本兩個目標的動態(tài)網絡中的社區(qū)結構。文中將標簽傳播算法集成到遺傳算法中，獲得了理想的聚類結果。同時在人工網絡和真實網絡中采用模塊度來最大化快照質量以及采用NMI 使時間成本最小化，使結果都高于其對比算法，具有較好的社區(qū)發(fā)現性能。

Gao 等[61]提出了一種基于分解的多目標離散粒子群優(yōu)化算法來發(fā)現動態(tài)結構。該方法采用模塊度優(yōu)化來測量當前時序的社區(qū)結構質量，同時也使用優(yōu)化的NMI 去計算兩個連續(xù)時間步的社區(qū)結構相似性。在人工數據集和真實數據集的多次實驗結果表明該算法在模塊度和NMI 的結果優(yōu)于作者所采用的對比算法。但是該算法造成粒子過早收斂和多樣性不足等缺陷。為了彌補這兩種缺點，Wang 等[62]通過提出基于演化聚類框架和標簽的群體智能方法，采用融合標簽傳播和遺傳算法改進的離散粒子群算法，引入模塊度和NMI 來評估社區(qū)發(fā)現的準確性。算法使用改進的標簽傳播算法來確定粒子位置，采用遺傳算法進行粒子處理，利用粒子群優(yōu)化選擇最優(yōu)解。該算法在人工合成網絡和真實世界網絡中的實驗結果優(yōu)于其對比算法，取得了良好的社區(qū)劃分效果。

He 等[30]提出了一種用于時間網絡中動態(tài)社區(qū)檢測的快速算法，該算法利用了先前時序中的歷史社區(qū)信息，通過歷史社區(qū)結構構造一個小型網絡，采用Louvain[64]算法來檢測新網絡中的社區(qū)。通過對真實和合成的時態(tài)網絡的實驗研究表明，該方法的運行速度遠遠快于傳統(tǒng)方法。Cordeiro 等[34]提出了一種可以在添加或刪除節(jié)點和邊后始終使社區(qū)結構保持為最新狀態(tài)的方法。該方法通過執(zhí)行局部模塊度優(yōu)化對Louvain 算法進行修改，僅對那些節(jié)點和邊變化的社區(qū)執(zhí)行最大化模塊度增益，保持網絡的其余部分不變。在實驗中作者將傳統(tǒng)靜態(tài)Louvain 算法作為基準算法，在真實數據集上對比了其他動態(tài)和靜態(tài)算法，結果取得了較好的實時社區(qū)劃分效果。

Mucha 等[59]創(chuàng)建了一個能夠在兩個不同的連續(xù)時間步長之間連接相同的節(jié)點的網絡，使用Louvain算法來優(yōu)化模塊度。該方法在真實網絡中展示了強大的分析功能，對真實網絡數據集的分析較為準確。而Aynaud 等[63]使用了Louvain 算法的優(yōu)化版本，在整個快照集或子集上最大程度地優(yōu)化了一組節(jié)點的平均模塊度，其主要目的是在網絡中尋找連貫的、模塊度最優(yōu)的社區(qū)。該算法實施在動態(tài)數據集mrinfo 上，研究了節(jié)點的變化、模塊度隨時間的變化以及全局和瞬時結構的差異，與其采用的對比算法相比，都取得了較好的性能評價。

2.5 方法比較

本節(jié)將從各種方法的主要采用算法和相關算法特點方面對基于聚類方法、基于動力學、基于統(tǒng)計模型以及基于啟發(fā)式算法等四種類型的社區(qū)發(fā)現方法進行比較分析，如表3 所示。

基于經典聚類方法的動態(tài)社區(qū)發(fā)現方法主要是將靜態(tài)社區(qū)發(fā)現中的經典社區(qū)發(fā)現方法進行改進，主要代表算法是密度聚類算法、派系過濾算法以及譜聚類算法等。

經典聚類算法都是專注于網絡自身的結構特性，對網絡結構的相關屬性進行節(jié)點聚類。基于密度聚類的方法是通過使用密度聚類相關算法在有噪音的數據中發(fā)現各種形狀和各種大小的簇。在譜聚類中，其主要思想是將所有數據作為空間中的點，這些點之間用帶有權重的邊連接起來。距離較遠的兩點之間的邊權重較低，而距離較近的兩點之間的邊權重較高，通過對節(jié)點和權重邊生成的圖進行切圖，使不同子圖之間的邊權重和盡可能得低，子圖內部的邊權重和盡可能得高，從而達到聚類的目的。而派系過濾算法主要思想是首先搜索所有具有k個節(jié)點的完全子圖，然后建立以k-團為節(jié)點的新圖，若在該圖中兩個k-團有k-1 個公共節(jié)點，則在新圖中兩個團之間建立一條邊。最終在新圖中，每個連通子圖代表一個社區(qū)。

Table 3 Comparison of dynamic community detection methods表3 動態(tài)社區(qū)發(fā)現方法的比較

基于動力學的動態(tài)社區(qū)發(fā)現方法主要依據網絡傳播的動力學特點，采用如馬爾可夫鏈、標簽傳播算法、隨機游走等方法進行動態(tài)網絡的社區(qū)劃分。

動力學算法的最大特點是隨機性，因此社區(qū)發(fā)現得到的結果有時會有一些差異，許多次實驗將結果取平均值。當采用馬爾可夫方法時，主要是利用其性質，即當一個隨機過程在給定現在狀態(tài)及所有過去狀態(tài)情況下，其未來狀態(tài)的條件概率分布僅依賴于當前狀態(tài)。隨機游走同樣具有馬爾可夫鏈的性質，即每一步具有“無記憶”的特性，每一次變化都不會影響別的變動。標簽傳播算法是一種自底向上的迭代算法。主要思想是在初始時刻對每一個節(jié)點分配一個標簽，在之后的迭代過程中，每個節(jié)點都將與它相連的鄰居里面數量最多的標簽作為該節(jié)點的新標簽，直至整個網絡的節(jié)點標簽都不再變化。

基于統(tǒng)計模型的動態(tài)社區(qū)發(fā)現方法，主要是采用隨機塊模型、矩陣分解以及深度學習等方法。

統(tǒng)計模型最大的特點是將線性代數和概率論等數學模型及規(guī)律應用于動態(tài)社區(qū)發(fā)現，有數學理論支撐，可解釋性強。隨機塊模型是隨機圖的生成模型，能夠生成網絡，主要以概率向量為依據，將網絡中的每個節(jié)點分配相應社區(qū)。矩陣分解算法中，非負矩陣分解是最為常用的算法，該算法簡便、可解釋性強、存儲空間少，能在降維的過程中保存較好的信息完整性。深度學習方法中網絡嵌入方法為每個節(jié)點輸出一個特征向量，從而將相似的節(jié)點嵌入到一個低維稠密的向量空間中，這些節(jié)點表示保持了原來的網絡結構特性。

基于啟發(fā)式算法的動態(tài)社區(qū)發(fā)現方法主要是將相關優(yōu)化的算法應用于動態(tài)網絡。采用的算法包括遺傳算法、粒子群優(yōu)化算法以及模塊度優(yōu)化算法等。

啟發(fā)式方法的特點就是采用優(yōu)化的思想，逐步求解最優(yōu)解，但在計算效率上可能不是最優(yōu)。遺傳算法是一種基于群體進化的計算模型，它通過群體的個體之間選擇（繁殖）、交叉和變異這三個基本的遺傳算子的遺傳操作來實現，從而逼近問題的最優(yōu)解。粒子群優(yōu)化是一種基于群體智能的全局隨機尋優(yōu)算法，算法為每個微粒給定位置和速度，每個微粒通過更新速度來更新其自身的位置。通過迭代搜索，種群可以不斷地找到更好的微粒位置，從而得到優(yōu)化問題的較優(yōu)解。Louvain 算法是基于模塊度優(yōu)化的常用算法，主要是通過模塊度來衡量社區(qū)的緊密程度，可在大型靜態(tài)網絡上進行快速、高效和健壯的社區(qū)發(fā)現。主要思想是若一個節(jié)點加入到某一社區(qū)中會使得該社區(qū)的模塊度有最大程度的增加，則節(jié)點就屬于該社區(qū)。若加入其他社區(qū)后，模塊度沒有增加，則留在當前社區(qū)。

3 評價標準與數據集

3.1 評價標準

3.1.1 模塊度

模塊度是衡量網絡或圖形結構的一種方法，旨在測量網絡劃分為模塊（社區(qū)）的強度。具有高模塊度的網絡在模塊內的節(jié)點之間具有密集的連接，而在不同模塊內的節(jié)點之間具有稀疏的連接。模塊度多被用來評價對未知社區(qū)結構劃分后的社區(qū)分類結果的好壞。

模塊度是Newman 等[9]于2004 年首次提出。為了解決GN（Girvan and Newman）算法無法評價社區(qū)發(fā)現結果以及不能發(fā)現最優(yōu)社區(qū)劃分的問題，使模塊度具有譜屬性，Newman 又在2006 年將其進一步定義[65]。具體公式如式（1）所示：

式中，eii表示社團i內部的邊占總邊數的比例；ai表示連接到社區(qū)i中的邊占總邊數的比例；m表示邊數；Avw表示網絡中的實際邊數；kv表示節(jié)點v的度數；表示節(jié)點v,w之間存在邊的概率。δ(cv,cw)有兩個值，當δ(cv,cw)=0 時表示節(jié)點v,w不在同一社區(qū)，當δ(cv,cw)=1 時，表示節(jié)點v,w在同一社區(qū)。

模塊度的物理意義是網絡社區(qū)內部的邊數目占整個網絡中的邊數目的比例與在同等社區(qū)結構條件下節(jié)點間任意連接的邊數目占整個網絡中的邊數目的比例之差的期望值。當模塊度為零時，說明網絡內部結構與構造的隨機模型沒有差異，即不存在明顯的社區(qū)結構特征。模塊度的取值范圍為[-0.5，1.0)，其值越大，表明網絡內部的社區(qū)結構越強，表示社區(qū)質量越高，社區(qū)劃分效果越好，準確度越高。但在實際應用中，大多數的真實世界網絡的模塊度都位于[0.3,0.7]之間。

很多文章中將模塊度這一評價標準進行拓展，應用在評價不同類型的社區(qū)結構中，如Shen 等[66]將模塊度拓展到重疊社區(qū)的評價上，Gou 等[31]形成了快照質量、歷史質量、總質量的評價指標，其主要思想還是使用模塊度對社區(qū)劃分結果進行評價。同時，模塊度優(yōu)化也作為一種基本的社區(qū)發(fā)現方法，被廣泛用于相關的算法研究之中。

3.1.2 標準化互信息

NMI 是基于熵的方法，用于測量當前時序和先前時序之間的社區(qū)結構相似性。同時NMI 也是大多數文章用來評價對已知社區(qū)結構的數據集劃分所得結果的優(yōu)劣的標準。其公式如式（2）所示：

其中，CN表示標準社區(qū)結構劃分的結果，CR表示算法所得的社區(qū)劃分的結果，C是一個混合矩陣，Cij表示N中屬于社區(qū)i的節(jié)點也屬于R中社區(qū)j的數目，Ci?(C?j)表示矩陣C中行或列元素的總和。

標準化互信息的物理意義是將按標準已劃分好的社區(qū)與某算法得到的劃分結果兩者做出對比，消除了相關信息的不確定性及信息關系之間的模糊性[67]，較為客觀地對標準社區(qū)結構與社區(qū)劃分結果之間的準確度進行評價。NMI 的取值范圍是[0,1]，當取值為0 時，算法劃分結果與實際社區(qū)結果完全不同；而當取值為1 時，算法劃分結果與實際社區(qū)結果完全相同。即NMI 值越大，社區(qū)劃分的結果越好。但其缺點也顯而易見，即NMI 指標需要在標準網絡結構已知的情況下使用。

3.1.3 持久性

持久性是Chakraborty 等[68]提出的一種基于節(jié)點的社區(qū)質量衡量指標，不僅衡量了網絡中每個節(jié)點保留在原有社區(qū)中的程度，還對網絡中的社區(qū)結構進行質量估計。其公式如式（3）所示：

其中，I(v) 是節(jié)點v在其社區(qū)中的鄰居節(jié)點數量；Emax(v)是節(jié)點v的鄰居社區(qū)中的最大鄰居節(jié)點數量；d(v)為節(jié)點v的度；Eneig(v)為節(jié)點v的在社區(qū)內部鄰居之間的連接數量。

持久性的物理意義在于將節(jié)點的內部連接性、節(jié)點的凝聚性和節(jié)點的外部最大連接相結合，基于局部頂點度量來量化分析節(jié)點與其所在社區(qū)、節(jié)點與其相鄰的社區(qū)的關系。持久性的取值范圍是[-1,1]，其取值越大，表示節(jié)點與其所在社區(qū)的連接越緊密，當取值為0 時，表示節(jié)點與其相鄰社區(qū)的連接緊密度都相同，需要將該節(jié)點劃分為單獨社區(qū)。

3.1.4 其他方法

此外還有不少方法對社區(qū)劃分結果或算法性能的優(yōu)劣進行評價。

運行時間是一個非常普遍使用的算法性能評價方法。對同一數據集使用不同的算法進行社區(qū)發(fā)現，每種方法所花費的時間一定程度上標志著該算法在時間復雜度上的優(yōu)劣性。好的算法花費時間少，劃分結果準確，更能受到用戶的青睞；差的算法，花費時間多，劃分不準確，就不能成為流行的方法。

另外還有一些論文將多種評價標準進行融合，以獲得更好的評價效果。如Takaffoli 等[69]將Guo 等[31]的快照質量與歷史質量線性組合形成新的評價標準，將其命名為動態(tài)模塊度。Tabarzad 等[70]認為模塊度和標準互信息措施不足以描述動態(tài)網絡中社區(qū)的質量，根據兩個定性標準的存在，使用調和平均數計算模塊度與標準互信息得到新的衡量標準。

3.2 數據集

3.2.1 真實世界網絡

真實世界網絡數據集包括已知標準社區(qū)結構的網絡以及未知標準社區(qū)結構的網絡。前者包含有空手道網絡Karate、海豚網絡Dolphin、政治書籍網絡Polbooks、足球網絡Football和政治博客網絡Polblogs等；而后者有小說《悲慘世界》中人物的共同出現網絡Les Mis、查爾斯·狄更斯的小說《大衛(wèi)·科波菲爾》中常見形容詞和名詞的鄰接網絡Adjnoun、表示線蟲的神經網絡的有向加權網絡Neural、恐怖分子電話網絡Call1、酵母細胞網絡Yeast、Facebook 社交網絡、國家電網網絡Power、Arxiv 廣義相對論協同網絡Ca-GrQc、Arxiv 高能物理理論協同網絡Ca-HepTh 和Arxiv 高能物理協同網絡Ca-HepPh 等。表4 給出了以上真實世界網絡數據集的相關信息。

Table 4 Datasets of partial real social networks表4 部分真實社交網絡數據集

在動態(tài)社區(qū)發(fā)現中真實數據集經常使用的是ENRON 和DBLP 數據集。Enron 電子郵件數據集包含了1991 年至2002 年間Enron Corporation 員工之間的交換電子郵件信息。數據集包含151 名員工的275 332 封電子郵件。DBLP 是計算機領域內以作者為核心將研究成果集成的計算機類英文文獻數據庫系統(tǒng)，按年代列出了作者的科研成果。DBLP 數據集存儲了相關文獻的元數據，如標題、作者、發(fā)表時間等。使用者可以根據需要提取相關的數據。

3.2.2 人工合成網絡

LFR（Lancichinetti，Fortunato and Radicchi）人工網絡由Lancichinetti 等[71]于2008 年提出，用來合成具有預定義社區(qū)結構的隨機網絡。LFR 網絡的定義如式（4）所示：

其中，N為節(jié)點數量；k表示節(jié)點的平均度；maxk表示節(jié)點的最大度；mu是混合參數，用來調節(jié)生成網絡的社區(qū)結構，mu值越大，越難劃分社區(qū)結構；minc表示社區(qū)的最少能包含的節(jié)點數量；maxc表示社區(qū)最大能包含的節(jié)點數量；on表示重疊節(jié)點的數量；om表示重疊節(jié)點中有成員關系的數量；C表示平均聚類系數。

3.3 性能分析

本節(jié)在11 種數據集上驗證了8 種典型的社區(qū)發(fā)現算法，采用運行時間、模塊度和標準化互信息來分析算法的相關性能，并詳細介紹了6 種用于網絡社區(qū)可視化的相關軟件。

本節(jié)采用的8 種算法分別是Fluidc 算法[72]、GN 算法[2]、Louvain 算法[64]、LPA（label propagation algorithm）算法[11]、Spectral Clustering 算法[73]、Greedy modularity算法[74]、Kernighan 算法[5]以及Block model 算法[75]，對3 種類型共11 種數據集進行研究，分別是已知社區(qū)結構的真實網絡數據集Karate、Football、Polbooks；未知社區(qū)結構的真實網絡數據集Dolphin、Lesmis、Power；人工數據集Lfr200、Lfr500、Lfr1000、Lfr2000 和Lfr5000。

3.3.1 運行時間

表5 中給出了8 種算法在11 種數據集中的運行時間，其中GN 算法對Lfr2000 和Lfr5000 數據集的社區(qū)發(fā)現沒有成功，主要原因在于GN 算法對大型數據集的處理效率過低，耗費時間過長；而Spectral Clustering 算法在對Power 數據集的處理上由于采用算法的某些原因不能對其進行社區(qū)劃分。實驗表明，GN 算法在運行速度上與其余算法相比最慢，耗費時間最長。LPA 相對于其他算法而言，運行時間最短，速度最快，主要原因是其時間復雜度呈線性，較其他算法要快得多。各算法的時間復雜度和輸入參數對比詳見表6，其中μ表示深度。對于小型數據集大部分算法都可以在較短的時間內計算出來。GN、Spectral Clustering 以及Kernighan 算法在大型數據集上則需要較多的時間。

Table 5 Running time of 8 methods on datasets表5 8 種算法在數據集中的運行時間 s

Table 6 Time complexity and input parameters of 8 methods表6 8 種經典算法的時間復雜度以及輸入參數

3.3.2 模塊度

圖4 給出了8 種算法在11 種數據集中的模塊度。結果表明，Louvain 算法在所有數據集中形成社區(qū)的模塊度都是最大的，即相對于其他算法性能最優(yōu)，主要是因為Louvain 算法是基于模塊度優(yōu)化的算法，其對模塊度的計算有著天然的優(yōu)勢。同時Spectral Clustering 算法對于5 種人工數據集的模塊度與Louvain 算法的結果一致，表明譜聚類算法對人工數據集的社區(qū)劃分的性能優(yōu)于其對真實網絡數據的劃分。Block model 算法的模塊度在8 種算法中是最低的，即其所劃分的社區(qū)結構的質量較差。

3.3.3 標準化互信息

Fig.4 Modularity of 8 methods on datasets圖4 8 種算法在數據集中的模塊度

Fig.5 NMI of 8 methods on datasets圖5 8 種算法在數據集中的標準化互信息

圖5 給出了8 種算法在8 種已知社區(qū)結構的數據集中的標準化互信息。結果表明，Louvain 算法、譜聚類算法、GN 算法對于5 種人工數據集的標準化互信息均為1，即這3 種算法對人工數據集的社區(qū)劃分的所得結果與真實社區(qū)結果一致，性能最優(yōu)。但結合表5，Spectral Clustering 算法的缺點在于需要社區(qū)數量作為輸入。而Kernighan 算法和Block model 算法在圖中處于較低水平，表明這兩種算法對于相關數據集的劃分結果與實際社區(qū)結構有較為明顯的差距。

3.3.4 可視化

目前，復雜網絡可視化分析軟件有50 多種，表7中選擇6 種主流常用軟件信息進行對比：UCINET、NodeXL、Pajek 和Gephi 屬于獨立軟件，NetworkX 和igraph 屬于工具類庫。

Table 7 Complex network analysis tools表7 復雜網絡分析工具

圖6 是NetworkX 應用Karate 數據集繪制的標準社區(qū)結構，以及應用8 種算法進行社區(qū)發(fā)現的結果。從圖中可以發(fā)現每個算法對數據集的劃分都與標準的社區(qū)結構有著一定的差距。結合圖3、圖4 研究發(fā)現，模塊度大并不代表所劃分的結果與實際社區(qū)結構相似，如Louvain 算法在Karate 數據集上的模塊度高于其他算法，但在NMI 上的結果比Kernighan 算法要低。

4 經典應用場景

社區(qū)發(fā)現的應用場景非常廣泛，Karata?等[76]綜述了社區(qū)發(fā)現算法在犯罪學、公共衛(wèi)生、政治學、智能廣告、定向市場營銷、推薦系統(tǒng)、社交網絡分析、網絡歸納、隱私領域、鏈接預測和社區(qū)演化預測等領域的研究進展。本章探索研究動態(tài)社區(qū)發(fā)現在公共安全、公共衛(wèi)生、市場營銷、推薦系統(tǒng)、網絡分析、鏈接預測和輿論監(jiān)測等領域的研究進展。

Fig.6 Comparison of results of 8 methods and normalized structure in Karate dataset圖6 空手道數據集中8 種算法和標準結構的結果對比

（1）在公共安全領域，社區(qū)發(fā)現能夠識別犯罪用戶群體。能夠將支持或散布犯罪觀念或類似恐怖主義的活動的真人賬號或機器人賬號建立為社區(qū)，從而發(fā)現其中有價值的信息。Ferrara 等[77]通過手機通話記錄，建立一個基于網絡科學、法醫(yī)學和統(tǒng)計分析原理的計算框架，使用GN 和Newman 快速算法進行社區(qū)發(fā)現來研究犯罪網絡的社區(qū)結構和演化，設計出專家系統(tǒng)用以幫助警察分析電話日志記錄。Calderoni 等[78]通過研究針對意大利南部地區(qū)卡拉布里亞的黑手黨組織的大型執(zhí)法行動的案例來分析社區(qū)結構。Sarvari 等[79]使用PageRank 分析網絡中犯罪分子的重要程度，通過CFinder 對網絡上的犯罪分子的電子郵件地址網絡進行社區(qū)發(fā)現來構建大規(guī)模的社交圖，并使用人工分析的方法來發(fā)現犯罪分子的社交信息，從而能夠破壞犯罪社區(qū)并找到關鍵成員。

（2）在公共衛(wèi)生領域，網絡社區(qū)中健康相關話題已經引起相關研究人員的關注。Lu 等[80]對醫(yī)學健康論壇中的話題進行文本聚類，用于構建醫(yī)學主題模型，從而分析論壇用戶對疾病的關注重點。社區(qū)發(fā)現通常用于發(fā)現易患流行病的某些群體的發(fā)展動態(tài)[81]，檢測癌癥等疾病[82-83]，或者用于器官檢測[84-85]。

（3）在市場宣傳營銷方面，社區(qū)發(fā)現直接用于劃分公司的客戶類型、智能廣告和定向營銷[76]。如果公司能夠了解其客戶類型，就可以提供更好的服務方案。Mosadegh 等[86]根據發(fā)現到的客戶類型進行定向廣告和營銷宣傳的研究。

（4）在推薦系統(tǒng)領域，社區(qū)發(fā)現有著十分廣泛的應用，通過社區(qū)發(fā)現將特定目標用戶進行分類，可以將同一社區(qū)的用戶的相關喜好進行相互推薦，能提高推薦成功的概率。Rezaeimehr 等[87]提出了基于時間的推薦算法，該算法主要采用重疊社區(qū)發(fā)現用于研究。而Gurini 等[88]基于社區(qū)的用戶推薦算法利用興趣和情感進行社區(qū)發(fā)現，從而給用戶最終的推薦。Lalwani 等[89]采用社區(qū)檢測算法通過分析用戶-用戶社交圖來提取用戶之間的友誼關系，并采用基于用戶項目的協作過濾來進行評分預測，進行推薦。

（5）在網絡分析領域，社區(qū)發(fā)現仍然是一個非常重要的研究領域。社區(qū)發(fā)展預測是指根據社區(qū)過去和現在狀態(tài)對社區(qū)未來形式的預測，這也是社區(qū)分析領域的熱門話題之一[76]。為了實現社區(qū)演變的預測，需要檢測動態(tài)社區(qū)來查看分析社區(qū)的演變規(guī)律。Bringmann 等[90]利用圖演化規(guī)則開發(fā)了圖演化規(guī)則挖掘器，并運用到社區(qū)演化預測中。?lhan 等[91]提出基于事件預測的特征識別框架來檢查網絡的各種結構特征，并發(fā)現社區(qū)特征的最突出子集。該框架通過提取網絡結構，確定社區(qū)特征的子集，從而能夠實現準確的社區(qū)事件預測。

（6）在鏈接預測中，可評估網絡成員之間將來鏈接的可能性，并用于確定虛假鏈接、丟失的鏈接和將來的鏈接。通過社區(qū)檢測算法找到網絡的社區(qū)結構，然后計算兩個成員之間存在鏈接的可能性。Valverde等[92]提出了一種基于社區(qū)檢測的鏈接預測方法，使用社區(qū)發(fā)現算法對每個節(jié)點進行劃分，然后在鏈接預測中明確使用獲得的社區(qū)結構信息。Soundarajan 等[93]通過使用Louvain、Infomap 和Link Communities 進行社區(qū)劃分，使用獲得的社區(qū)信息來提高鏈接預測的準確性。

（7）在輿論監(jiān)測領域，隨著智能手機的普遍使用，社交媒體應用越來越頻繁，微信、QQ、微博、Facebook、Twitter 等社交應用成為信息傳播的主要平臺。輿論傳播的方式也越來越多，與此同時也帶來了許多虛假信息的發(fā)布與傳播。因此，輿論監(jiān)測顯得尤為重要。Xia 等[94]則是從評論內容中提取語義信息從而構建語義網絡，然后通過社區(qū)發(fā)現方法對網絡進行劃分，從而進行網絡數據分析。

5 挑戰(zhàn)

隨著大規(guī)模在線復雜社交網絡的出現，傳統(tǒng)的動態(tài)社區(qū)發(fā)現技術面臨著一些新的挑戰(zhàn)。

（1）網絡異質?，F實社交網絡一般擁有多種多樣的異質信息，例如在線社交網絡除了包含用戶與用戶之間的相互關系，還包含用戶發(fā)布或轉發(fā)的文本、圖片、視頻等信息。目前對網絡的表示，僅僅是將角色轉換為節(jié)點，將角色之間的聯系轉換為邊，而忽略了角色之間存在多種類型的聯系。Interdonato等[95]嘗試使用局部社區(qū)發(fā)現的方法對多層網絡進行劃分，而Meng 等[96]則在悉尼科技大學出版物數據集上使用多語義路徑聚類方法進行分析研究。該數據集是包含期刊、會議論文、會議記錄、章節(jié)和書籍等多種信息的異構數據集。SHINE[97]是一種用于情感鏈接預測的帶符號的異構信息網絡嵌入框架，可以對情感網絡、社交網絡和個人資料網絡進行網絡嵌入，然后將三種特征進行融合并進行優(yōu)化。

（2）計算效率。隨著大規(guī)模實時復雜社交網絡的出現，對于動態(tài)社區(qū)發(fā)現算法的計算效率要求也越來越高?，F有的動態(tài)社區(qū)發(fā)現方法或犧牲準確度提高計算效率，或犧牲計算效率提高準確度，很難同時滿足時間復雜性低、發(fā)現準確度高和無監(jiān)督等要求?，F實應用場景里，許多方法很難適應復雜的大型實時網絡，計算和存儲方面的效率也都較為低下。

（3）評價標準。雖然目前多數算法的實驗結果都從模塊度、NMI 或時間復雜度來與現有算法進行比較，但研究表明，模塊度函數有時不能準確地衡量劃分出的社區(qū)結構的優(yōu)劣程度[67]。有些模塊度較高的社區(qū)直觀上還不如模塊度較低的結果。Takaffoli等[69]嘗試將當前網絡的模塊度與歷史網絡的模塊度線性組合形成新的評價標準，將其命名為動態(tài)模塊度。Tabarzad 等[70]則將模塊度和標準互信息的調和平均數作為新的衡量標準。因此，統(tǒng)一的動態(tài)社區(qū)發(fā)現結果評價標準可能成為動態(tài)社區(qū)發(fā)現未來重點研究方向之一。

6 結束語

本文首先從網絡和節(jié)點層面對社區(qū)發(fā)現方法進行了分析，然后根據采用算法的不同將動態(tài)社區(qū)發(fā)現分為四種類型，分別是基于聚類方法的社區(qū)發(fā)現方法、基于動力學的社區(qū)發(fā)現方法、基于統(tǒng)計模型的社區(qū)發(fā)現方法和基于啟發(fā)式算法的社區(qū)發(fā)現方法。接著介紹了社區(qū)發(fā)現方法中模塊度、標準化互信息、持久性等常用的評價標準以及在進行仿真實驗中常用的真實世界網絡和人工合成網絡數據集。然后對八種經典靜態(tài)社區(qū)發(fā)現算法進行對比實驗，使用運行時間、模塊度和NMI 評價這些方法在真實網絡和人工網絡中的性能。隨后介紹了動態(tài)社區(qū)發(fā)現方法在公共安全、公共衛(wèi)生、市場宣傳營銷、推薦系統(tǒng)、網絡分析、鏈接預測和輿論監(jiān)測等領域的應用研究。最后從網絡異質、計算效率和評價標準三方面提出了動態(tài)社區(qū)發(fā)現目前面臨的挑戰(zhàn)。

目前對復雜網絡的社區(qū)發(fā)現的研究雖已日漸深入，但仍存在需要深入研究的方向。隨著大數據時代的來臨，社交媒體的廣泛應用，對真實社交網絡的動態(tài)社區(qū)發(fā)現的研究仍具有重要意義。在未來的工作中，將進一步研究動態(tài)社區(qū)發(fā)現方法的對比實驗，著力于解決網絡異質、計算效率和評價標準的挑戰(zhàn)，以期在后續(xù)研究上有更大突破。