局部社區(qū)發(fā)現(xiàn)算法研究綜述

聶世民 杜彥輝 蘆天亮

摘 要：社區(qū)發(fā)現(xiàn)能幫助人們了解社交網(wǎng)絡的結構特性及隱藏信息。局部社區(qū)發(fā)現(xiàn)算法不需要網(wǎng)絡的整體信息，以局部結構信息為基礎，可以快速找到目標節(jié)點所在的局部社區(qū)，提高了效率，因而受到學者們的青睞。按算法基本思想，現(xiàn)有局部社區(qū)發(fā)現(xiàn)算法可分為標簽傳播類算法、局部擴張算法等。對部分局部社區(qū)發(fā)現(xiàn)領域的研究成果進行總結，分析它們的優(yōu)缺點，并提出未來局部社區(qū)發(fā)現(xiàn)算法研究方向。

關鍵詞：社交網(wǎng)絡;局部社區(qū)發(fā)現(xiàn);評價指標;移動互聯(lián)網(wǎng)

DOI：10. 11907/rjdk. 191832 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2020）005-0271-05

0 引言

隨著互聯(lián)網(wǎng)和計算機科學的發(fā)展，越來越多的人加入社交網(wǎng)絡。人們在社交媒體上相互交流，表達自己的觀點，形成了復雜的網(wǎng)絡關系。社區(qū)發(fā)現(xiàn)對于揭示社交網(wǎng)絡結構、挖掘人們觀點、分析信息傳播、把握和監(jiān)測公眾情緒具有重要意義[1]。近年來，隨著社區(qū)發(fā)現(xiàn)成為社會網(wǎng)絡分析的一個重要領域，科研人員和學者提出了多種多樣的社區(qū)發(fā)現(xiàn)方法。因此，不論從其研究價值還是實用價值角度講，研究社區(qū)發(fā)現(xiàn)問題都具有重要意義。

1 相關定義

1.1 社交網(wǎng)絡

現(xiàn)實世界中有很多種網(wǎng)絡，社交網(wǎng)絡作為一種典型的網(wǎng)絡，發(fā)展迅速。Wang[2]將網(wǎng)絡定義為：“網(wǎng)絡是一組具有特定內(nèi)容和實體間關系的實體”;WOLFE[3]將社交網(wǎng)絡定義為一種由實體和實體之間關系構成的網(wǎng)絡，實體之間可以相互作用。社交網(wǎng)絡是虛擬世界中真實世界的延伸，有許多典型的社交網(wǎng)絡，如Facebook、Twitter、QQ、微信、微博、貼吧等，其特征、變化和社區(qū)結構反映了現(xiàn)實世界的運作方式，越來越多的專家學者致力于社交網(wǎng)絡研究。

1.2 社區(qū)

社區(qū)是社會網(wǎng)絡的重要結構[4-6]。關于社區(qū)的定義，學界尚沒有形成一個精確的統(tǒng)一概念，不同學者從不同角度給出了社區(qū)的定義[7-12]。例如，從圖的角度出發(fā)，Newman[7]將群內(nèi)連接密集、群間連接稀疏的頂點群稱為社區(qū);Santo Fortunato[9]認為社區(qū)內(nèi)的邊必須比將社區(qū)頂點與圖的其余部分連接起來的邊更多，社區(qū)是一組具有相似性的頂點;Filippo Radicchi[12]等基于節(jié)點出度和入度提出了強社區(qū)和弱社區(qū)的概念。雖然定義各式各樣，但可以提取一些相同點：社區(qū)通常被認為是復雜網(wǎng)絡中一些滿足特定條件的節(jié)點，該條件就是社區(qū)內(nèi)節(jié)點與節(jié)點之間連接更加緊密，不同社區(qū)內(nèi)的節(jié)點與節(jié)點之間連接相比較而言則較為稀少。

1.3 社區(qū)發(fā)現(xiàn)

通常，社區(qū)發(fā)現(xiàn)是指通過某種方法找出復雜網(wǎng)絡中的某個或者多個社區(qū)。學者對社區(qū)結構定義的理解不同，在進行社區(qū)劃分時遵循的標準也各不相同，大致可以總結為兩種：全局社區(qū)發(fā)現(xiàn)算法和局部社區(qū)發(fā)現(xiàn)算法[1]。全局社區(qū)發(fā)現(xiàn)算法是在整個目標網(wǎng)絡范圍內(nèi)劃分社區(qū)，從整體角度出發(fā)進行社區(qū)發(fā)現(xiàn)，目的是找出目標網(wǎng)絡中所有可能存在的社區(qū)，使用這類算法必須擁有目標網(wǎng)絡的全局信息[13]。

當下，移動互聯(lián)網(wǎng)用戶不斷發(fā)展壯大，各類社交網(wǎng)絡規(guī)模與日俱增，F(xiàn)acebook、微信等社交網(wǎng)絡都擁有10億以上的節(jié)點，網(wǎng)絡的全局信息逐漸變得難以獲得，如此規(guī)模龐大的社交網(wǎng)絡使用全局社區(qū)發(fā)現(xiàn)算法進行社區(qū)發(fā)現(xiàn)存在諸多困難且社區(qū)發(fā)現(xiàn)效果不盡人意。為解決這些困難，有學者提出了局部社區(qū)發(fā)現(xiàn)算法。局部社區(qū)發(fā)現(xiàn)算法不需要提前獲得目標網(wǎng)絡的整體信息，而是以目標網(wǎng)絡的局部結構信息為基礎，進而發(fā)現(xiàn)局部或整個網(wǎng)絡社區(qū)。與全局社區(qū)算法相比，局部社區(qū)發(fā)現(xiàn)算法在運行時間、應用范圍、算法靈活性等方面存在更大優(yōu)勢，已成為當前研究熱點。

1.4 社區(qū)發(fā)現(xiàn)算法評價指標

社區(qū)發(fā)現(xiàn)算法多種多樣，評價社區(qū)質(zhì)量的標準也有很多，如模塊度、標準互信息（Normalized Mutual Information，NMI）、Jaccard系數(shù)、ARI標準、芮氏指標、F-measure[14-15]值等，它們從不同角度對發(fā)現(xiàn)的社區(qū)進行評價。本文總結幾種使用頻率較高的評價指標：模塊度、標準互信息、Jaccard系數(shù)。

（1）模塊度。Newman等[16]首先提出了模塊度的概念。模塊度即Q函數(shù)，取值范圍在0～1，一般情況下，Q值越大說明算法越精確，而在真實情況下，Q值在0.3～0.7時社區(qū)劃分效果較好。然而，這種模塊度計算方法還有其不足之處，其中一點就是無法在加權網(wǎng)絡中使用。為了解決該不足，在原有模塊度函數(shù)基礎上，Xu等[17]提出了新的模塊度函數(shù)[QW]。除了不適用于加權網(wǎng)絡，Q函數(shù)不能評價重疊社區(qū)的發(fā)現(xiàn)結果[18-19]，為了更好地適應重疊網(wǎng)絡情況，陳俊宇[20]、肖覓[21]等對Q函數(shù)進行了修改以評價重疊社區(qū)的發(fā)現(xiàn)結果。

（2）標準互信息度量。標準互信息度量是信息論中的概念，最初并沒有用在社區(qū)發(fā)現(xiàn)的評價指標上。在社區(qū)發(fā)現(xiàn)領域，Leon Danon[22]等最早使用標準互信息度量進行社區(qū)發(fā)現(xiàn)算法評價。NMI可以衡量社區(qū)發(fā)現(xiàn)結果的精度[23-24]，NMI值越大，說明社區(qū)發(fā)現(xiàn)結果越準確，當NMI值為1時，說明發(fā)現(xiàn)的社區(qū)與真實社區(qū)結構一致。NMI也存在其局限性，如不能用于評價重疊社區(qū)的發(fā)現(xiàn)結果。在重疊網(wǎng)絡中，一個節(jié)點一般不會只存在于單一的社區(qū)之中，往往屬于不同的社區(qū)。為了能夠適用于重疊網(wǎng)絡，Lancichinetti等[25]對NMI的計算方法進行了修改。

（3）Jaccard系數(shù)。Jaccard系數(shù)的基本思想與標準互信息度量相同，也是將找到的社區(qū)結構與真實社區(qū)進行比較，通過計算二者的相似程度評價社區(qū)發(fā)現(xiàn)算法的準確性[26]。使用Jaccard系數(shù)作為評價指標，社區(qū)發(fā)現(xiàn)的結果越準確，Jaccard值越大。當Jaccard值為1時，說明二者的社區(qū)結構完全相同;當發(fā)現(xiàn)的社區(qū)和真實社區(qū)完全不同時，Jaccard值為0。

本文提到的3個評價指標適用范圍并不相同，如表 1所示。由于實驗數(shù)據(jù)中往往不包括社區(qū)結構方面的信息，因此實際應用時，模塊度的使用頻率最高。

2 局部社區(qū)發(fā)現(xiàn)算法

近年來，互聯(lián)網(wǎng)和移動互聯(lián)網(wǎng)取得了長足進展，社交網(wǎng)絡也借此機會發(fā)展壯大，社交網(wǎng)絡的內(nèi)部結構持續(xù)變化，呈現(xiàn)出日趨復雜的趨勢。這些因素都加大了社交網(wǎng)絡分析難度，獲取網(wǎng)絡的全局信息越來越艱難。但是在很多業(yè)務場景中，并不一定要獲取到網(wǎng)絡的全局信息，只需發(fā)現(xiàn)某個節(jié)點所在的局部社區(qū)就能解決真實存在的問題。舉例而言，因案件需要，公安機關需要知道某個犯罪嫌疑人在社交網(wǎng)絡上的活躍社區(qū)從而尋找可能存在的犯罪同伙，這時就不需要社交網(wǎng)絡的全局信息，只需要發(fā)現(xiàn)犯罪嫌疑人經(jīng)?；钴S的社區(qū)即可。

局部社區(qū)發(fā)現(xiàn)算法的基本思想不盡相同，現(xiàn)有的局部社區(qū)發(fā)現(xiàn)算法按照算法基本思想可以分為標簽傳播類算法[27-30]、局部擴張算法[31-40]和派系過濾算法[41-42]等。本文總結了一些經(jīng)典的局部社區(qū)發(fā)現(xiàn)算法，其中局部擴張類算法中的Clauset算法是最早提出用來解決局部社區(qū)發(fā)現(xiàn)問題的算法，標簽傳播類算法、局部擴張類算法是使用頻率較高的算法，這些算法不需要社交網(wǎng)絡的全局信息，可以避免過高的時空開銷。

2.1 Clauset算法

局部社區(qū)發(fā)現(xiàn)的概念由Clauset等[43]最早提出，在這之前，學者們都是從全局的角度研究社區(qū)發(fā)現(xiàn)問題。Clauset等不僅提出了局部社區(qū)發(fā)現(xiàn)的概念，也提出了解決辦法，包括局部社區(qū)模塊度R，該算法效率較高，能夠快速找到局部社區(qū)。

Clauset算法首先初始化局部社區(qū)D，其鄰居集合用S表示。最初從一個初始節(jié)點v開始，將v加入到D中，并將v的所有鄰居節(jié)點加入到S中，然后按如下步驟進行運算：①對于鄰居集合S中的所有節(jié)點計算模塊度增量，也即設想將原本屬于集合S中的節(jié)點j加入到初始化社區(qū)D中所帶來的模塊度增量;②選取具有最大模塊度增量的節(jié)點j加入到D中;③將j的所有鄰居節(jié)點加入到S中，然后更新R和B。

在局部社區(qū)規(guī)模達到預估設定值之前，Clauset算法會不斷挑選能產(chǎn)生最大局部模塊度增量的鄰居節(jié)點劃入社區(qū)D中?？梢缘弥褂眠@種算法進行局部社區(qū)發(fā)現(xiàn)會受預先設定參數(shù)的影響，局部社區(qū)發(fā)現(xiàn)的結果受初始節(jié)點影響較大。

2.2 標簽傳播類方法

Zhu等[27]最早提出標簽傳播算法（Label Propagation Algorithm，LPA），該算法用網(wǎng)絡中已經(jīng)具有標簽信息的節(jié)點預測那些沒有標簽信息的節(jié)點，其本質(zhì)是一種基于圖的半監(jiān)督學習方法。由于這種標簽傳播算法沒有復雜的目標函數(shù)，實現(xiàn)難度較低，算法效率較高，因此受到了眾多學術研究人員的關注。在社區(qū)發(fā)現(xiàn)這一領域，Raghavan等[28]第一次應用標簽傳播方法研究局部社區(qū)發(fā)現(xiàn)問題，提出的LPA算法只使用局部網(wǎng)絡結構進行社區(qū)發(fā)現(xiàn)。

該算法具體過程為：①賦予一個原始標簽給網(wǎng)絡中每個節(jié)點;②在所有節(jié)點標簽不再變化之前，根據(jù)傳播規(guī)則，節(jié)點的標簽在局部網(wǎng)絡中傳播;③相同標簽的節(jié)點歸屬同一個社區(qū)。

LPA算法需要多次迭代，傳播規(guī)則是在每次迭代后，節(jié)點標簽受其鄰居節(jié)點影響，鄰居節(jié)點使用最多的標簽會變?yōu)樵摴?jié)點的新標簽。局部網(wǎng)絡中每個節(jié)點最終歸屬的社區(qū)受其鄰居節(jié)點影響，其鄰居節(jié)點中大多數(shù)節(jié)點屬于的社區(qū)就是該節(jié)點屬于的社區(qū)。

雖然LPA算法有較低的時間復雜度，實現(xiàn)過程也不算困難，但也有其不足之處，比如它的不確定性。因為某些標簽會在迭代傳播過程中逐漸受到其它標簽的控制而消失，結果是局部社區(qū)數(shù)量越來越少，出現(xiàn)少數(shù)幾個規(guī)模較大的局部社區(qū)。為了改進LPA算法的不確定性，Leung等[29]在LPA算法的基礎上，提出了HANP（Hop Attenuation and Node Preference）算法。除算法不確定性之外，標簽的傳播距離沒有在算法中得到明確限制，這就會導致某個社區(qū)中的標簽可以傳播很遠而侵入其它社區(qū)。在HANP算法中，在每個節(jié)點擁有一個標簽的基礎上新增一個分數(shù)參數(shù)，在標簽傳播過程中，傳播距離越大，該分數(shù)值越小。HANP算法的基本思路就是通過該分數(shù)參數(shù)控制標簽在傳播過程中的影響力，分數(shù)參數(shù)變小則會降低該標簽的影響力，從而避免標簽傳播過遠而侵入其它社區(qū)的現(xiàn)象。

LPA算法還有一個問題就是它只能用于非重疊網(wǎng)絡。因為該算法基于單個標簽傳播，最終每個節(jié)點都會歸屬到某個社區(qū)中，而現(xiàn)實情況中，存在節(jié)點屬于多個社區(qū)的情況。為了解決LPA算法在重疊網(wǎng)絡中的應用問題，Gregory等[30]基于LPA算法提出了多標簽傳播算法（Community Overlap Propagation Algorithm，COPRA）。在COPRA算法中，節(jié)點擁有多個標簽，這樣能夠標示出節(jié)點的多個社區(qū)，社區(qū)間的重疊程度通過一個參數(shù)控制，算法每運行一次就會重新計算節(jié)點對于不同社區(qū)的隸屬程度。不同于LPA算法，在標簽傳播時，因為節(jié)點擁有多個標簽，COPRA算法先更新節(jié)點的鄰居標簽集合到該節(jié)點上，再刪除不符合預設條件的標簽。有些節(jié)點可能擁有多個最大隸屬標簽，一旦出現(xiàn)這種情況就隨機選擇一個，這也導致了結果的不確定性。

2.3 局部擴張算法

局部社區(qū)發(fā)現(xiàn)算法中有一大類算法是基于局部擴展優(yōu)化思想的。局部擴張算法根據(jù)定義的局部度量，首先選擇初始節(jié)點，再逐步合并鄰居節(jié)點，從而進行局部擴展優(yōu)化[38]。主要包括兩個步驟：選擇種子節(jié)點和將種子節(jié)點擴展為局部社區(qū)[44]。

Lancichinetti等[25]提出了局部適應度算法（Local Fitness Method，LFM）。在LFM算法中，種子節(jié)點的選擇方法是采取隨機原則，算法通過最大化局部適應度函數(shù)拓展社區(qū)。步驟如下：①計算種子邊緣節(jié)點適應度，若適應度為正值，則將該節(jié)點劃分到對應社區(qū);②計算該社區(qū)內(nèi)每個節(jié)點的適應度;③若某節(jié)點適應度為負，則移除該節(jié)點;④如果發(fā)生③，則執(zhí)行②，否則執(zhí)行①。

該算法實現(xiàn)簡單，計算時間復雜度小，但受其種子節(jié)點選取隨機性的影響，局部社區(qū)發(fā)現(xiàn)結果不確定。

Huang等[33]提出了局部緊密度擴展算法（Local Tightness Expansion，LTE）。在LTE算法中，種子節(jié)點的選擇方法和LFM算法相同，也是隨機選取某個節(jié)點作為種子節(jié)點，算法通過最大化可調(diào)密度增益擴展社區(qū)。方法如下：①計算社區(qū)鄰居集合中每個節(jié)點與社區(qū)的相似度;②根據(jù)①中的結果，計算最大相似度節(jié)點的可調(diào)密度增益，若大于零，則將該節(jié)點劃分到社區(qū)，否則就刪除該節(jié)點。按照相似度的降序依次分析其余節(jié)點;③重復上述過程，直到所有節(jié)點均加入相應社區(qū)。

該算法實現(xiàn)簡單，計算時間復雜度小，但受其種子節(jié)點選取隨機性的影響，局部社區(qū)發(fā)現(xiàn)結果不確定。

陳瓊等[34]為解決部分局部社區(qū)發(fā)現(xiàn)算法受初始節(jié)點位置影響的問題，提出了一種基于局部最大度節(jié)點的算法（Local Maximum Degree，LMD）。LMD算法將初始節(jié)點的局部最大度節(jié)點作為種子節(jié)點，通過優(yōu)化局部社區(qū)度量擴展社區(qū)。

LMD算法采用Clauset算法[43]進行局部社區(qū)拓展，時間復雜度為[O（k2d）]，節(jié)點個數(shù)用k代表，節(jié)點平均度用d代表。以不同的局部最大度節(jié)點作為種子節(jié)點進行局部社區(qū)拓展得到的社區(qū)可能比較接近，因此需要將較近的社區(qū)合并成一個社區(qū)。對于社區(qū)[Ci]和[Cj]，其中，[Ci={vi1，vi2，][vi3，？vip}]，[Cj={vj1，vj2，vj3，？vjp}]，如果[Ci]和[Cj]滿足式（4），則[Ci]和[Cj]可以進行合并。

吳建等[35]提出了一種基于圖遍歷的局部社區(qū)發(fā)現(xiàn)算法，該算法擴張速度較快，可以用于大規(guī)模網(wǎng)絡。該算法首先找出網(wǎng)絡中度數(shù)最低的節(jié)點，以該節(jié)點為起點通過影響力函數(shù)將網(wǎng)絡中的節(jié)點分為社區(qū)節(jié)點和邊界節(jié)點，形成初步社區(qū)劃分，然后通過適應度函數(shù)確定邊界節(jié)點的社區(qū)從而得到最終劃分結果。

算法步驟如下：①計算網(wǎng)絡中所有節(jié)點的度數(shù)，選取度數(shù)最小的節(jié)點作為起始節(jié)點，如果多個節(jié)點的度數(shù)相同則從中隨機選擇一個作為起始節(jié)點，由于此時網(wǎng)絡中的節(jié)點都未被標記，因此該節(jié)點被標記為邊界節(jié)點;②由起始節(jié)點開始，計算該節(jié)點周圍所有鄰居節(jié)點受到的影響力，并根據(jù)節(jié)點標記規(guī)則對鄰居節(jié)點進行標記;③判斷當前已標記節(jié)點是否還有未被標記的鄰居節(jié)點，若存在，計算所有未標記鄰居節(jié)點受到的影響力，根據(jù)規(guī)則給予相應標記，再次執(zhí)行步驟③，若不存在，則跳轉(zhuǎn)至步驟④;④選擇網(wǎng)絡中的邊界節(jié)點與鄰居社區(qū)進行合并，計算每次合并前后的適應度函數(shù)F[24]，若合并后新社區(qū)的F大于合并前的社區(qū)F，則按照規(guī)則對合并后的節(jié)點標記進行更新;⑤當網(wǎng)絡所有邊界節(jié)點均合并完畢時去掉所有邊界節(jié)點標記，將擁有相同標記的節(jié)點劃分到統(tǒng)一社區(qū)中。

該算法時間復雜度較低，可以適用于大型網(wǎng)絡，但社區(qū)發(fā)現(xiàn)結果受提前設置的參數(shù)影響，不能用于加權網(wǎng)絡。

3 挑戰(zhàn)及展望

學者們從不同角度提出了各種局部社區(qū)發(fā)現(xiàn)算法，取得了豐碩成果，讓人們對局部網(wǎng)絡結構有了更加清晰的認識。隨著研究的深入，社交網(wǎng)絡也在不斷衍變，呈現(xiàn)出大規(guī)模、日益復雜的特征，因此需要更快處理速度和更高準確性的社區(qū)發(fā)現(xiàn)算法，但存在一些問題有待進一步研究。

（1）社區(qū)初步劃分。社交網(wǎng)絡往往規(guī)模巨大、節(jié)點眾多，在進行局部社區(qū)發(fā)現(xiàn)時可以采取一定辦法縮小網(wǎng)絡規(guī)模從而降低算法時間復雜度。不同的網(wǎng)絡具有不同特點，要根據(jù)網(wǎng)絡特點設計符合實際的規(guī)則。

（2）社區(qū)發(fā)現(xiàn)領域快速性需求。社交網(wǎng)絡規(guī)模在持續(xù)增長，有些社交網(wǎng)絡的節(jié)點數(shù)能達到十億以上，用戶間的聯(lián)系也千絲萬縷，如何快速處理如此大規(guī)模的網(wǎng)絡數(shù)據(jù)，是社區(qū)發(fā)現(xiàn)領域研究人員共同面臨的一大難題。

（3）社區(qū)發(fā)現(xiàn)領域精確性需求。大多數(shù)局部社區(qū)發(fā)現(xiàn)算法結果受初始節(jié)點影響較大，導致結果不夠準確。當然也有不少算法改善了這一問題，但在精確性上還有待提高。社區(qū)發(fā)現(xiàn)算法是為了找到真實的社區(qū)結構，但存在這樣一個問題：社區(qū)結構是人為定義出來的，不同的學者根據(jù)不同場景提出過多種社區(qū)描述和定義，直到目前都沒有一個統(tǒng)一標準，當前社區(qū)發(fā)現(xiàn)算法往往只能在其定義的社區(qū)結構場景中取得較高準確率，換一個場景就不一定能夠保持高準確率。

4 結語

隨著移動互聯(lián)網(wǎng)的蓬勃發(fā)展，越來越多的人加入到各種社交網(wǎng)絡中，社區(qū)發(fā)現(xiàn)研究的現(xiàn)實意義和應用價值日益凸顯，受到了學者們的廣泛關注。本文總結了部分局部社區(qū)發(fā)現(xiàn)領域的研究成果，提出了未來研究方向。希望更多學者能夠投入社區(qū)發(fā)現(xiàn)及其相關研究，為社區(qū)發(fā)現(xiàn)理論與實踐作出更大貢獻。

參考文獻：

[1] LI J H， WANG X F， WU P. Review on community detection methods based on local optimization[J]. Bulletin of Chinese Academy of Sciences，2015（2）：238-247.

[2] WANG， FAN X. Complex networks： topology， dynamics and synchronization[J]. International Journal of Bifurcation and Chaos，2002，12（5）：885-916.

[3] WASSERMAN S，F(xiàn)AUST K. Social network analysis： methods and applications[J]. Contemporary Sociology，1995，91（435）：219-220.

[4] ZHANG X， WANG C， SU Y， et al. A fast overlapping community detection algorithm based on weak cliques for large-scale networks[J]. IEEE Transactions on Computational Social Systems，2017，4（4）：218-230.

[5] VESPIGNANI A. Complex networks： the fragility of interdependency[J]. ?Nature， 2010， 464（7291）：984-5.

[6] WANG Q，WEN Z P. Multidimensional genetic algorithm for overlapping community detection[J]. Application Research of Computers，2016，33（12）：3543-3546.

[7] GIRVAN M， NEWMAN M E J. Community structure in social and biological networks[J]. Proc. Natl. Acad. Sci. USA，2001，99：7821- 7826.

[8] PAPADOPOULOS S， KOMPATSIARIS Y， VAKALI A， et al. Community detection in social media[J]. Data Mining and Knowledge Discovery，2011，24（3）：515-54.

[9] FORTUNATO S. Community detection in graphs[J]. Physics Reports， 2009.

[10] EVERETT M G，BORGATTI S P.Analyzing clique overlap[J]. Connection，1998， 21（21）：49-61.

[11] PORTER M A， ONNELA J P， MUCHA P J. Communities in networks[J]. Notices of the AMS，2009，56（9）：1082-1097.

[12] RADICCHI F， CASTELLANO C， CECCONI F， et al. Defining and identifying communities in networks[J]. ?Proceedings of the National Academy of Sciences of the United States of America， 2004，101（9）：2658-2663.

[13] LIU L H， FANG Z X， XIAO S L， et al.Fast communities detection algorithm with source nodes[J]. Computer Engineering and Applications， 2016，52（23）：75-80.

[14] ZENG J P， YU H F. A study of graph partitioning schemes for parallel graph community detection[J]. Parallel Computing，2016，58（C）：131-139.

[15] SU Y S， WANG B J， ZHANG X Y. A seed-expanding method based on random walks for community detection in networks with ambiguous community structures[J]. Scientific Reports，2017（7）：1-10.

[16] Newman M E J.Finding and evaluating community structure in networks[J]. ?Physical Review E，2004，69（2）：026113.

[17] XU J M， LI T F， WU S F. A micro-blogging community discovery method based on users interactions[J]. ?Journal of Heibei University（Natural Science Edition）， 2016，36（2）：189-196.

[18] WANG X F， LIU G S， LI J H， et al. Locating structural centers： a density-based clustering method for community detection[J]. ?Plos One，2017，12（1）：1-23.

[19] SHANG M S， CHEN D B， ZHOU T. Detecting overlapping communities based on community cores in complex networks[J]. Chinese Physics Letters， 2010，27（5）：1-4.

[20] CHEN J Y，ZHOU G，NAN Y，et al. Semi-supervised local expansion method for overlapping community detection[J]. Journal of Computer Research and Development， 2016，53（6）：1376-1388.

[21] XIAO M，MENG X W，SHI Y C. A circuits merging community discovery algorithm based on mobile user behaviors[J]. Journal of Electronics & Information Technology， 2012， 34（10）：2369-2374.

[22] DANON L，DUCH J，DIAZ-GUILERA A，et al. Comparing community structure identification[J]. Journal of Statistical Mechanics，2005（9）：09008.

[23] LI L，F(xiàn)AN K，ZHANG Z，et al. Community detection algorithm based on local expansion k-means[J]. Neural Network World，2016，26（6）：589-605.

[24] WEN X Y，CHEN W N，LIN Y， et al. A maximal clique based multiobjective evolutionary algorithm for overlapping community detection[J]. IEEE Transactions on Evolutionary Computation， 2017，21（3）：363-377.

[25] LANCICHINETTI A， FORTUNATO S， KERTESZ J. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics， 2009，11（3）：1-20.

[26] JEUB L G S， MAHONEY M W， MUCHA P J， et al. A local perspective on community structure in multilayer networks[J]. ?Network Science， 2017，5（2）：144-163.

[27] ZHU X， GHANRAMANI Z. Learning from labeled and unlabeled data with label propagation[R]. Carnegie Mellon University， Technical Report CMU-CALD-02， 2002.

[28] RAGHAVAN U N， ALBERT R， KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. ?Physical Review E， 2007，76（3）：036106.

[29] LEUNG I X Y， HUI P， LIO' P， et al. Towards real-time community detection in large networks[J]. ?Physical Review E Statistical Nonlinear & Soft Matter Physics， 2008，79（2）：066107.

[30] GREGORY，STEVE. Finding overlapping communities in networks by label propagation[J]. ?New Journal of Physics， 2010，12（10）：103018.

[31] CHEN J， ZAIANE O AND GOEBEL R. Local community identification in social networks[J]. In Proc. the 2009 Int. Conf. Advances in Social Network Analysis and Mining，2009：237-242.

[32] WU Y J，HUANG H， HAO Z F，et al. Local community detection using link similarity[J]. ?Journal of Computer Science and Technology，2012，27（6）：1261-1268.

[33] HUANG J B， SUN H L， LIU Y G， et al. Towards online multiresolution community detection in large-scale networks[J]. Plos One，2011，6（8）：1-11.

[34] CHEN， QIONG， WU， et al. Detecting local community structures in complex networks based on local;degree central nodes[J]. Physica A Statistical Mechanics & Its Applications，2013，392（3）：529-537.

[35] 吳建，王梓權，易億，等. 基于圖遍歷的局部社區(qū)發(fā)現(xiàn)算法[J]. 計算機應用研究， 2019（9）：1-6.

[36] ANDREA L， FILIPPO R， RAMASCO JOSé J， et al. Finding statistically significant communities in networks[J]. ?Plos One，2011，6（4）：e18961.

[37] SHANGFU GONG， WANLU CHEN， PENGTAO JIA. Survey on algorithms of community detection[J]. Application Research of Computers.2013，30（11）：3216-3215.

[38] JARUKASEMRATANA S，MURATA T， LIU X. Community detection algorithm based on centrality and node distance in scale-free networks[J]. IMT，2013，9（1）：162-172.

[39] KLOUMANN I M， KLEINBERG J M. Community membership identification from small seed sets. KDD'14. 2014（2）：1366-1375.

[40] WHANG J J， GLEICH D F， DHILLON I S. Overlapping community detection using seed set expansion[C]. ACM International Conference on Information and Knowledge Management，2013：2099-2108.

[41] PALLA G， DERENYI I， FARKAS I， et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature，2005， 435（7043）：814-822.

[42] KUMPULA J M，KIVELA M，KASKI K.A sequential algorithm for fast clique percolation[J]. ?Physical Review E Statistical Nonlinear & Soft Matter Physics， 2008， 78（2）：026109.

[43] CLAUSET A. Finding local community structure in networks[J]. Physical Review E， 2005，72（2）：254-271.

[44] SHANG C X，F(xiàn)ENG S Z，ZHAO Z Y，et al. Efficiently detecting overlapping communities using seeding and semi-supervised learning[J]. International Journal of Machine Learning and Cybernetics，2017，8（2）：455-468.

（責任編輯：孫 娟）