局部社區發現算法研究綜述

聶世民 杜彥輝 蘆天亮

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

關鍵詞：社交網絡;局部社區發現;評價指標;移動互聯網

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

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

0 引言

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

1 相關定義

1.1 社交網絡

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

1.2 社區

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

1.3 社區發現

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

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

1.4 社區發現算法評價指標

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

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

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

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

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

2 局部社區發現算法

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

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

2.1 Clauset算法

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

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

在局部社區規模達到預估設定值之前，Clauset算法會不斷挑選能產生最大局部模塊度增量的鄰居節點劃入社區D中。可以得知，使用這種算法進行局部社區發現會受預先設定參數的影響，局部社區發現的結果受初始節點影響較大。

2.2 標簽傳播類方法

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

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

LPA算法需要多次迭代，傳播規則是在每次迭代后，節點標簽受其鄰居節點影響，鄰居節點使用最多的標簽會變為該節點的新標簽。局部網絡中每個節點最終歸屬的社區受其鄰居節點影響，其鄰居節點中大多數節點屬于的社區就是該節點屬于的社區。

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

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

2.3 局部擴張算法

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

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

該算法實現簡單，計算時間復雜度小，但受其種子節點選取隨機性的影響，局部社區發現結果不確定。

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

該算法實現簡單，計算時間復雜度小，但受其種子節點選取隨機性的影響，局部社區發現結果不確定。

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

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

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

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

該算法時間復雜度較低，可以適用于大型網絡，但社區發現結果受提前設置的參數影響，不能用于加權網絡。

3 挑戰及展望

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

（1）社區初步劃分。社交網絡往往規模巨大、節點眾多，在進行局部社區發現時可以采取一定辦法縮小網絡規模從而降低算法時間復雜度。不同的網絡具有不同特點，要根據網絡特點設計符合實際的規則。

（2）社區發現領域快速性需求。社交網絡規模在持續增長，有些社交網絡的節點數能達到十億以上，用戶間的聯系也千絲萬縷，如何快速處理如此大規模的網絡數據，是社區發現領域研究人員共同面臨的一大難題。

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

4 結語

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

參考文獻：

[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，FAUST 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，FAN 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] 吳建，王梓權，易億，等. 基于圖遍歷的局部社區發現算法[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，FENG 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.

（責任編輯：孫 娟）