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

1.中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇徐州 221116

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

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

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

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

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

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

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

1 相關(guān)工作

本章首先介紹相關(guān)符號(hào)的定義，然后通過(guò)網(wǎng)絡(luò)級(jí)別的行為演化和節(jié)點(diǎn)級(jí)別的行為演化分析目前主要?jiǎng)討B(tài)社區(qū)發(fā)現(xiàn)的研究方法。

1.1 相關(guān)定義

Fig.2 Framework of dynamic community detection圖2 動(dòng)態(tài)社區(qū)發(fā)現(xiàn)結(jié)構(gòu)圖

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

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

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

Table 1 Notions and descriptions表1 符號(hào)及描述

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

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

1.2.1 網(wǎng)絡(luò)級(jí)行為演化

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

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

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

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

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

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

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

重現(xiàn)（resurgence），一個(gè)社區(qū)消失一段時(shí)間后重新出現(xiàn)。

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

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

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

Gao 等[28]提出了基于領(lǐng)導(dǎo)者節(jié)點(diǎn)的演化社區(qū)發(fā)現(xiàn)算法，通過(guò)Top Leader 社區(qū)發(fā)現(xiàn)算法將初始網(wǎng)絡(luò)進(jìn)行劃分后，對(duì)社區(qū)進(jìn)行分裂以及合并操作。Xin 等[29]將網(wǎng)絡(luò)分為生成、分裂、合并和生存4 種群落演化，并使用相應(yīng)算法分別對(duì)4 種演化進(jìn)行研究。He 等[30]通過(guò)將大型網(wǎng)絡(luò)分解，構(gòu)造出小型網(wǎng)絡(luò)，提升社區(qū)發(fā)現(xiàn)的準(zhǔn)確性和速度。

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

1.2.2 節(jié)點(diǎn)級(jí)行為演化

節(jié)點(diǎn)級(jí)的行為演化主要從節(jié)點(diǎn)變化的角度來(lái)探索動(dòng)態(tài)網(wǎng)絡(luò)中社區(qū)的相關(guān)變化，包括以下四種情況：

（1）節(jié)點(diǎn)增加，新的節(jié)點(diǎn)加入當(dāng)前網(wǎng)絡(luò)；

（2）節(jié)點(diǎn)減少，一些現(xiàn)有節(jié)點(diǎn)離開當(dāng)前網(wǎng)絡(luò)；

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

（4）邊減少，一些節(jié)點(diǎn)之間斷開現(xiàn)有聯(lián)系。

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

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

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

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

2 動(dòng)態(tài)社區(qū)發(fā)現(xiàn)方法

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

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

2.1 基于經(jīng)典聚類方法的社區(qū)發(fā)現(xiàn)

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

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

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

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

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

2.2 基于動(dòng)力學(xué)的社區(qū)發(fā)現(xiàn)

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

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

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

Jdidia 等[45]對(duì)Infocom 會(huì)議的共同作者網(wǎng)絡(luò)進(jìn)行了分析。他們從不同的快照構(gòu)建一個(gè)網(wǎng)絡(luò)，并使用經(jīng)典的社區(qū)發(fā)現(xiàn)算法Walktrap[48]進(jìn)行社區(qū)發(fā)現(xiàn)，同時(shí)引入Infocom 會(huì)議委員會(huì)成員來(lái)進(jìn)行數(shù)據(jù)分析。Xie等[39]在標(biāo)簽傳播算法LabelRank[49]的基礎(chǔ)上提出了一種增量算法LabelRankT。網(wǎng)絡(luò)更新后，算法重新初始化已更改節(jié)點(diǎn)的標(biāo)簽，并重新應(yīng)用LabelRank 算法來(lái)更新標(biāo)簽概率分布。真實(shí)網(wǎng)絡(luò)上的結(jié)果表明，LabelRankT 的計(jì)算成本遠(yuǎn)低于同類算法，并且提高了網(wǎng)絡(luò)結(jié)構(gòu)的質(zhì)量。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.5 方法比較

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

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

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

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

基于動(dòng)力學(xué)的動(dòng)態(tài)社區(qū)發(fā)現(xiàn)方法主要依據(jù)網(wǎng)絡(luò)傳播的動(dòng)力學(xué)特點(diǎn)，采用如馬爾可夫鏈、標(biāo)簽傳播算法、隨機(jī)游走等方法進(jìn)行動(dòng)態(tài)網(wǎng)絡(luò)的社區(qū)劃分。

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

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

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

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

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

3 評(píng)價(jià)標(biāo)準(zhǔn)與數(shù)據(jù)集

3.1 評(píng)價(jià)標(biāo)準(zhǔn)

3.1.1 模塊度

模塊度是衡量網(wǎng)絡(luò)或圖形結(jié)構(gòu)的一種方法，旨在測(cè)量網(wǎng)絡(luò)劃分為模塊（社區(qū)）的強(qiáng)度。具有高模塊度的網(wǎng)絡(luò)在模塊內(nèi)的節(jié)點(diǎn)之間具有密集的連接，而在不同模塊內(nèi)的節(jié)點(diǎn)之間具有稀疏的連接。模塊度多被用來(lái)評(píng)價(jià)對(duì)未知社區(qū)結(jié)構(gòu)劃分后的社區(qū)分類結(jié)果的好壞。

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

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

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

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

3.1.2 標(biāo)準(zhǔn)化互信息

NMI 是基于熵的方法，用于測(cè)量當(dāng)前時(shí)序和先前時(shí)序之間的社區(qū)結(jié)構(gòu)相似性。同時(shí)NMI 也是大多數(shù)文章用來(lái)評(píng)價(jià)對(duì)已知社區(qū)結(jié)構(gòu)的數(shù)據(jù)集劃分所得結(jié)果的優(yōu)劣的標(biāo)準(zhǔn)。其公式如式（2）所示：

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

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

3.1.3 持久性

持久性是Chakraborty 等[68]提出的一種基于節(jié)點(diǎn)的社區(qū)質(zhì)量衡量指標(biāo)，不僅衡量了網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)保留在原有社區(qū)中的程度，還對(duì)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)進(jìn)行質(zhì)量估計(jì)。其公式如式（3）所示：

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

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

3.1.4 其他方法

此外還有不少方法對(duì)社區(qū)劃分結(jié)果或算法性能的優(yōu)劣進(jìn)行評(píng)價(jià)。

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

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

3.2 數(shù)據(jù)集

3.2.1 真實(shí)世界網(wǎng)絡(luò)

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

Table 4 Datasets of partial real social networks表4 部分真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)集

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

3.2.2 人工合成網(wǎng)絡(luò)

LFR（Lancichinetti，F(xiàn)ortunato and Radicchi）人工網(wǎng)絡(luò)由Lancichinetti 等[71]于2008 年提出，用來(lái)合成具有預(yù)定義社區(qū)結(jié)構(gòu)的隨機(jī)網(wǎng)絡(luò)。LFR 網(wǎng)絡(luò)的定義如式（4）所示：

其中，N為節(jié)點(diǎn)數(shù)量；k表示節(jié)點(diǎn)的平均度；maxk表示節(jié)點(diǎn)的最大度；mu是混合參數(shù)，用來(lái)調(diào)節(jié)生成網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，mu值越大，越難劃分社區(qū)結(jié)構(gòu)；minc表示社區(qū)的最少能包含的節(jié)點(diǎn)數(shù)量；maxc表示社區(qū)最大能包含的節(jié)點(diǎn)數(shù)量；on表示重疊節(jié)點(diǎn)的數(shù)量；om表示重疊節(jié)點(diǎn)中有成員關(guān)系的數(shù)量；C表示平均聚類系數(shù)。

3.3 性能分析

本節(jié)在11 種數(shù)據(jù)集上驗(yàn)證了8 種典型的社區(qū)發(fā)現(xiàn)算法，采用運(yùn)行時(shí)間、模塊度和標(biāo)準(zhǔn)化互信息來(lái)分析算法的相關(guān)性能，并詳細(xì)介紹了6 種用于網(wǎng)絡(luò)社區(qū)可視化的相關(guān)軟件。

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

3.3.1 運(yùn)行時(shí)間

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

Table 5 Running time of 8 methods on datasets表5 8 種算法在數(shù)據(jù)集中的運(yùn)行時(shí)間 s

Table 6 Time complexity and input parameters of 8 methods表6 8 種經(jīng)典算法的時(shí)間復(fù)雜度以及輸入?yún)?shù)

3.3.2 模塊度

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

3.3.3 標(biāo)準(zhǔn)化互信息

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

Fig.5 NMI of 8 methods on datasets圖5 8 種算法在數(shù)據(jù)集中的標(biāo)準(zhǔn)化互信息

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

3.3.4 可視化

目前，復(fù)雜網(wǎng)絡(luò)可視化分析軟件有50 多種，表7中選擇6 種主流常用軟件信息進(jìn)行對(duì)比：UCINET、NodeXL、Pajek 和Gephi 屬于獨(dú)立軟件，NetworkX 和igraph 屬于工具類庫(kù)。

Table 7 Complex network analysis tools表7 復(fù)雜網(wǎng)絡(luò)分析工具

圖6 是NetworkX 應(yīng)用Karate 數(shù)據(jù)集繪制的標(biāo)準(zhǔn)社區(qū)結(jié)構(gòu)，以及應(yīng)用8 種算法進(jìn)行社區(qū)發(fā)現(xiàn)的結(jié)果。從圖中可以發(fā)現(xiàn)每個(gè)算法對(duì)數(shù)據(jù)集的劃分都與標(biāo)準(zhǔn)的社區(qū)結(jié)構(gòu)有著一定的差距。結(jié)合圖3、圖4 研究發(fā)現(xiàn)，模塊度大并不代表所劃分的結(jié)果與實(shí)際社區(qū)結(jié)構(gòu)相似，如Louvain 算法在Karate 數(shù)據(jù)集上的模塊度高于其他算法，但在NMI 上的結(jié)果比Kernighan 算法要低。

4 經(jīng)典應(yīng)用場(chǎng)景

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

Fig.6 Comparison of results of 8 methods and normalized structure in Karate dataset圖6 空手道數(shù)據(jù)集中8 種算法和標(biāo)準(zhǔn)結(jié)構(gòu)的結(jié)果對(duì)比

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

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

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

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

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

（6）在鏈接預(yù)測(cè)中，可評(píng)估網(wǎng)絡(luò)成員之間將來(lái)鏈接的可能性，并用于確定虛假鏈接、丟失的鏈接和將來(lái)的鏈接。通過(guò)社區(qū)檢測(cè)算法找到網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，然后計(jì)算兩個(gè)成員之間存在鏈接的可能性。Valverde等[92]提出了一種基于社區(qū)檢測(cè)的鏈接預(yù)測(cè)方法，使用社區(qū)發(fā)現(xiàn)算法對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行劃分，然后在鏈接預(yù)測(cè)中明確使用獲得的社區(qū)結(jié)構(gòu)信息。Soundarajan 等[93]通過(guò)使用Louvain、Infomap 和Link Communities 進(jìn)行社區(qū)劃分，使用獲得的社區(qū)信息來(lái)提高鏈接預(yù)測(cè)的準(zhǔn)確性。

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

5 挑戰(zhàn)

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

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

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

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

6 結(jié)束語(yǔ)

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

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