張應龍，夏學文，徐 星，喻 飛，吳泓潤，余 鷹

1(閩南師范大學 物理與信息工程學院，福建 漳州 363000)

2(華東交通大學 軟件學院，南昌 330013)

1 引 言

社團檢測是網(wǎng)絡研究分析中的一項重要任務[1，2]，它以介觀尺度觀察和理解網(wǎng)絡，有助于分析挖掘團體之間的關系動態(tài)、模式和功能，找到隱藏的內(nèi)在關系與規(guī)律并預測復雜網(wǎng)絡的行為，從而更好的理解復雜網(wǎng)絡.相關術語有社團、社區(qū)、圖劃分、聚團或群組結構等，本文對這些概念統(tǒng)一稱之為社團.

自從Newman等人提出社團概念[3]以來，產(chǎn)生了海量的社團檢測算法[4]，可分為全局優(yōu)化和局部優(yōu)化兩大類[5]局部優(yōu)化通過網(wǎng)絡的局部拓撲結構特征，來揭示局部或整個網(wǎng)絡的社團結構.相較于全局優(yōu)化方法，局部優(yōu)化不僅無需整體的網(wǎng)絡結構信息及先驗知識的輔助，而且在計算代價、挖掘局部社團特性等方面存在更多優(yōu)勢[5，6].

標簽傳播算法Label Propagation Algorithm(LPA)[7]憑借其簡潔原理及近乎線性的時間代價等優(yōu)點，成為局部優(yōu)化方法的代表.在過去的十幾年中，研究者發(fā)表了大量相關的工作.

目前優(yōu)秀的社團檢測綜述[4-5，8-11]尚未重點關注LPA算法.文獻[4，8]從全局的角度分析了社團檢測研究現(xiàn)狀.文獻[5，11]概括了局部優(yōu)化的社團檢測方法.文獻[9，10]重點介紹了動態(tài)社團檢測方法.盡管這些綜述有助于了解社團檢測研究現(xiàn)狀，然而缺乏對LPA算法這一分支的詳細介紹、分析與總結.

鑒于上述，有必要系統(tǒng)分析與總結標簽傳播算法研究現(xiàn)狀、面臨問題以及前景，從而為其勾畫出一個較為詳細和全面的輪廓，為社團檢測等相關領域的研究提供有價值的參考.

2 基礎知識

2.1 數(shù)據(jù)集及常用符號

本文所涉真實網(wǎng)絡數(shù)據(jù)集統(tǒng)計信息如表1所示.這些數(shù)據(jù)集一個共同特點是其上的真實社團結構為已知，更多詳情見文獻[12].

表1 本文所涉及的真實網(wǎng)絡統(tǒng)計信息

LFR生成網(wǎng)絡[13]是常用的一個評價社團檢測的測試基準網(wǎng)絡.主要通過節(jié)點度數(shù)分布γ、社團大小分布β以及混合參數(shù)μ等3個參數(shù)控制生成基準網(wǎng)絡.其中參數(shù)μ表示一個節(jié)點的所有邊中占比1-μ條邊屬于同一社團，μ越小則生成的基準網(wǎng)絡越能呈現(xiàn)出清晰的社團結構.

文中常用符號見表2.

表2 文中常用符號描述

文中用到了如下基于共同鄰居和節(jié)點度數(shù)的節(jié)點相似度度量.RA index[14]：

(1)

Edge-clustering coefficient(ECC)[15]：

(2)

這里τ(u)=Nu∪{u}.

2.2 評價指標

如何衡量社團檢測結果質(zhì)量是一個很大挑戰(zhàn).目前存在多種評價指標[4，16]，其中典型的評價指標為模塊度(Modularity)[17]和NMI(Normalized Mutual Information)[18].

已知算法檢測出的社團結構和其對應的不具有社團結構的空模型，模塊度基本思想是比較社團內(nèi)邊密度與相應空模型的期望邊密度的差值，差值越大表明相應的算法性能越優(yōu).模塊度定義為：

m為網(wǎng)絡邊數(shù)，Aij為網(wǎng)絡的鄰接矩陣A的元素，di為節(jié)點i的度數(shù)，ci為節(jié)點i所屬的社團，δ為克羅內(nèi)克函數(shù).

NMI用來評價一個社團劃分X與基準劃分Y相比的準確程度：

ci為第i個社團，CX和CY分別是X和Y對應的社團數(shù).NMI的值域是0到1，越高代表被評價的算法越準.特殊的，社團劃分和基準劃分完全一致，則NMI值為1.

3 LPA算法簡介與分析

3.1 社團定義

網(wǎng)絡用圖G=來表示，這里V是節(jié)點集，E是邊集.社團沒有一個標準定義[4]，一個普遍的觀點是社團內(nèi)部節(jié)點間鏈接(邊)稠密，而不同社團節(jié)點間鏈接稀疏，即內(nèi)部稠密，外部稀疏.有關社團定義的詳細討論可參考文獻[4].

集合{ci|ci?V，∪1≤i≤kci=V，1≤i≤k}為網(wǎng)絡G上一組社團，對于1≤i≤k，1≤j≤k，i≠j，當ci∩cj=?，即任何兩個社團都沒有交集，這時為非重疊社團，當存在ci∩cj≠?時，即存在兩個社團有交集，對應稱為重疊社團.

3.2 LPA算法

LPA[7]算法無需任何先驗信息：社團數(shù)以及社團的大小，也無需預先定義和優(yōu)化目標函數(shù)，具體過程為：

a)每個節(jié)點賦予一個唯一標簽，這時每個節(jié)點當作一個單獨社團.

b)隨機順序更新節(jié)點標簽，對于節(jié)點v，賦予其最大計數(shù)的鄰居標簽：

(3)

c)重復過程b)，直到所有的節(jié)點擁有其計數(shù)最大的鄰居標簽時終止迭代.

最終，緊密連接的節(jié)點間形成共識采納相同標簽組成一個社團，不同標簽的節(jié)點組構成不同的社團[7].為了敘述方便，在上下文不引起歧義的情況下，文中把社團和標簽等同對待.

LPA有兩種更新節(jié)點標簽方式：同步與異步.

同步更新是指節(jié)點x基于上一步，即第t-1步的鄰居標簽更新其標簽：Lx(t)=f(Lx1(t-1)，…，Lxk(t-1))，這里x1，…，xk為其鄰居，f為標簽更新策略函數(shù)，例如公式(3).

異步更新：Lx(t)=f(Lx1(t)，…，Lxm(t)，Lx(m+1)(t-1)，…，Lxk(t-1))，這里x1，…，xm為x的鄰居且當前迭代里已經(jīng)被更新，x(m+1)，…，xk為x的鄰居且當前迭代里仍未被更新.

文獻[19]表明異步要比同步收斂的更快，而同步更新得到的結果更穩(wěn)定，質(zhì)量更好.

若鄰接矩陣為A，則公式(3)可變換為:

(4)

基于公式(4)，文獻[20]把LPA算法形式化為優(yōu)化問題，標簽傳播過程實際是最大化目標函數(shù)H：

(5)

例如當更新節(jié)點x的標簽時，公式(5)變換為：

(6)

由式子(6)可知，公式右端的第1項的值不會發(fā)生變化，第2項與公式(4)一致，因此當更新節(jié)點x時，H的值不會變小，并且最終使H達到局部最大值.

3.3 存在的問題與挑戰(zhàn)

LPA算法簡潔、且時間復雜度接近線性：O(n+m)，n為節(jié)點個數(shù)，m為邊個數(shù).但存在以下一些問題與挑戰(zhàn)，過去的十幾年中，研究者主要針對這些問題與挑戰(zhàn)對其進行改進.

a)性能有待提高.LPA算法總是選擇節(jié)點的最大計數(shù)的鄰居標簽作為其標簽，未考慮網(wǎng)絡的其它特征.例如，不同鄰居對節(jié)點的影響不同，節(jié)點是否處于社團中心等，而這些特征一定程度上影響社團檢測的質(zhì)量.因此，原始LPA算法的性能有待提高.

b)不確定性(Randomness).不確定性是指結果具有不可重復性：每次運行結果可能會不同.導致不確定性的因素之一為平局的解決方案(tie resolution)[7]：當節(jié)點v的計數(shù)最大的鄰居標簽(公式(3))具有多個時，則在其中隨機選取一個作為v的標簽.另外，隨機順序更新節(jié)點標簽，同樣會產(chǎn)生不確定性[21].如圖1所示網(wǎng)絡，整個網(wǎng)絡分為兩個社團，然而右端3個節(jié)點的不同更新順序會導致不同結果，若先更新節(jié)點3，其計數(shù)最大鄰居標簽有多個：1、4、5，節(jié)點的標簽有可能選為1，然后更新節(jié)點4，其最大標簽變?yōu)?，這樣整個網(wǎng)絡劃分為一個社團；相反，若先更新節(jié)點5，選擇其標簽為3，接著更新節(jié)點4，其標簽變?yōu)?，節(jié)點3的標簽保持不變，從而右側3個節(jié)點組成了一個社團.

圖1 不確定性現(xiàn)象[22]

c)標簽震蕩現(xiàn)象.同步更新方式會產(chǎn)生標簽震蕩現(xiàn)象(oscillation problem)[23].這種現(xiàn)象多見于二部圖中，其他類型網(wǎng)絡也有可能發(fā)生這種現(xiàn)象.如圖2所示，從其相鄰兩次迭代標簽(節(jié)點的顏色)的變化，觀察出這種現(xiàn)象使得算法無法收斂.雖然異步更新方式在某種程度能解決上述問題，但這種方式不利并行計算、結果不穩(wěn)定以及容易產(chǎn)生大的社團.

圖2 標簽震蕩現(xiàn)象[24]

d)平凡檢測(trivial detection)問題.檢測算法有時把整個網(wǎng)絡當作一個社團.這可從公式(5)得到解釋：社團越大，H的值越大，特別的，當所有節(jié)點具有相同的標簽時，H具有全局最優(yōu)值；更多的時候，會產(chǎn)生大的社團(monster community)[19].社團結構不明顯的網(wǎng)絡更會導致平凡檢測[7].

e)重疊社團檢測.真實網(wǎng)絡中，社團間具有重疊性，即節(jié)點可以屬于多個社團.這些重疊節(jié)點是社團間橋梁，在信息互通及社團演化方面起著重要作用.分析社團重疊結構有助于理解復雜網(wǎng)絡.由于LPA算法原理簡潔，因此有必要利用其原理研究如何檢測重疊社團.

f)動態(tài)社團檢測.在線社會網(wǎng)絡研究中，社團演化檢測是一個十分關鍵的核心問題，它對于在介觀尺度下觀察在線社會網(wǎng)絡結構特征、預測演化趨勢、掌控網(wǎng)絡勢態(tài)、發(fā)現(xiàn)網(wǎng)絡異常群體事件等具有重要意義[9].如何運用LPA算法的優(yōu)勢進行動態(tài)社團檢測的研究是十分有意義.

上述問題不是單獨存在，有時相互交織在一起，例如圖1所示的不確定的例子中，其中一個結果就產(chǎn)生了平凡檢測現(xiàn)象.針對以上存在問題，研究者提出了系列改進的LPA算法.

4 基于LPA的社團檢測算法

按前述問題的分類，本節(jié)介紹和分析解決相應問題的LPA算法.在基于LPA原理基礎上提出了各種策略構成了這些算法.相應的優(yōu)秀算法是各種策略的組合，沒必要單獨評價某一策略的優(yōu)劣，故文中在綜述現(xiàn)有研究內(nèi)容(策略)后，比較與評價了同一問題下的代表性算法.

4.1 提高算法性能

現(xiàn)分析導致LPA算法性能不高的原因及相應解決對策.

對于社團而言：內(nèi)部節(jié)點間鏈接關系更稠密，不同社團的節(jié)點間鏈接關系更稀疏.其中一類方法引入如下策略[26]：直接鄰居間鏈接越稠密對應的貢獻值就越大，越有可能處于同一社團.邊(u，v)的局部邊介數(shù)(local edge betweenness)[27]是另一類衡量局部鏈接稠密程度的度量：經(jīng)過(u，v)的所有長度不超過h(h>0)的最短路徑的個數(shù).局部邊介數(shù)值越小，對應的節(jié)點之間越稠密，越有可能處于同一社團，文獻[28]在更新節(jié)點u時，計算u的du條邊的長度為2的局部邊介數(shù)，在邊介數(shù)值小的1+du/2條邊所關聯(lián)的鄰居中選計數(shù)最多的標簽Lu賦予u，這樣在原有算法基礎上進一步考慮了局部鏈接稠密性.

LPA標簽傳播過程中，節(jié)點等同對待其所有鄰居，然而真實網(wǎng)絡中，不同鄰居對其具有不同影響力，因此等同對待鄰居不能真實反映網(wǎng)絡特征.針對該問題，研究者引入了基于鏈接的節(jié)點間的相似性進行區(qū)分不同鄰居的重要性，例如，文獻[14]在更新節(jié)點標簽時，把與其具有最高相似性值(公式(1))的鄰居標簽更新為其標簽.

節(jié)點在網(wǎng)絡中所起的作用不同，有的節(jié)點處于社團中心，有的節(jié)點則不然，然而LPA算法沒有考慮這種節(jié)點的中心性.因而，研究者提出了節(jié)點中心性概念，文獻[29]把節(jié)點及其鄰居的度數(shù)之和定義為節(jié)點的密度，密度越大表明不僅節(jié)點本身重要而且其被重要的節(jié)點包圍，那么密度值大的節(jié)點最有可能為核心點，核心點把標簽傳遞給鄰居，從而形成種子區(qū)域，然后進行標簽傳播.

改進的算法主要從以上3方面提高社團的質(zhì)量.然而這些算法沒有解決不確定性、平凡檢測等問題，而且后續(xù)介紹的算法中都有蘊含這些優(yōu)秀思想，但為了強調(diào)這些思想，故匯總在此.基于上述原因?qū)Ρ竟?jié)所涉算法不進行分析比較.

4.2 不確定性(Randomness)

4.2.1 平局問題引發(fā)的不確定性

解決平局問題有如下方法：1)當存在多個最大計數(shù)標簽時，不再隨機選擇，而是按某種規(guī)則在其中選擇一個標簽;2)不以最大計數(shù)為標準選擇標簽，采用新的標簽傳播規(guī)則.

首先分析第1大類方法：在多個最大計數(shù)標簽中選擇鏈接密度高的標簽.

存在多個不同定義的鏈接密度，對于節(jié)點u，文獻[30]定義其鄰居v的絕對鏈接密度為：suv=1+mNv，這里mNv表示v的鄰居集合Nv中相互鏈接的邊數(shù)，然而，該方法傾向于識別出大社團，甚至可能導致平凡檢測問題發(fā)生[31].基于此，文獻[31]定義了鄰居v新的鏈接密度：LDuv=?α/suv」，參數(shù)α的作用是平衡高鏈接密度的和稀疏的鄰居區(qū)域.針對不同的網(wǎng)絡如何取相應的α的值是該方法存在的問題.而文獻[32]則基于包含了鏈接密度的信息[33]定義重要節(jié)點，但該算法時間復雜度高為O(n2).文獻[15]則在其中選擇一個同時屬于其偏好鄰居節(jié)點集的標簽，否則在候選標簽中隨機選一個，節(jié)點u的偏好(高鏈接密度)鄰居節(jié)點定義為：

這里σ(u，v)為公式(2)，ρu=(∑v∈Nuwuv)/(n-1).

第2大類方法是建立系列新的標簽傳播機制：更新最相似的鄰居標簽為節(jié)點標簽.

本類方法主要基于共同鄰居定義節(jié)點間的相似性，例如直接計算節(jié)點間的共同鄰居數(shù)[21].在基于共同鄰居的基礎上，研究者引入了節(jié)點度數(shù)[14，34-35]定義相似性，例如文獻[14]和文獻[35]基于公式(1)定義節(jié)點相似性，而文獻[34]定義如下相似性：σ(u，v)*dv，σ(u，v)見公式(2).文獻[35]更新v的標簽時，不僅要求具有最相似性的鄰居標簽，而且增加了限制條件：v加入該社團能增加模塊度值.特殊的，文獻[23]基于了更多因素定義了節(jié)點間的相似性度量CNP[36].

與以上算法不同，文獻[37]為每個節(jié)點保留來自鄰居的多個標簽.算法通過Inflation操作使得標簽隸屬系數(shù)大的更大，小的更小，然后進行Cutoff操作：過慮掉小于指定閾值的隸屬系數(shù)的標簽.

4.2.2 隨機順序引起的不確定性

現(xiàn)有主要措施為：1)從中心點出發(fā)更新節(jié)點標簽；2)固定更新順序.

第1大類算法思想首先需確定中心節(jié)點，然后標簽由中心節(jié)點按一定的傳播規(guī)則向外擴散[22，38-41].部分工作以節(jié)點度數(shù)定義核心節(jié)點[22，38，40]，度數(shù)越大越有可能成為核心節(jié)點，也有工作依據(jù)節(jié)點密度值[39]來定義核心節(jié)點：

這里di為節(jié)點i的度數(shù).其次面臨的問題是如何選取中心節(jié)點，基本思路為選取最大度數(shù)(密度值)且互不直接相連(相似)的核心節(jié)點作為中心節(jié)點.工作[22，39]需要人為設置k個中心點，為了避免人為指定k，工作[38]選取鄰居區(qū)域度數(shù)最高的節(jié)點作為中心節(jié)點且保證中心節(jié)點間互不為鄰居，但該工作對大規(guī)模網(wǎng)絡的處理能力有限.工作[40]則規(guī)定中心點間的距離不小于網(wǎng)絡的平均距離，而平均距離需要求所有節(jié)點對的距離，這會產(chǎn)生昂貴的時間代價.

第2類依據(jù)節(jié)點的鄰居鏈接密度值從小到大固定更新順序：工作[42]定義密度值Cohesion Index：

CI(u)=nSim(u)/CC(u)

工作[44]認為節(jié)點在開始迭代時要比結束時表現(xiàn)出強的傳播性，開始時，節(jié)點有可能把其標簽傳播鄰居，從而形成社團，然而，在最后幾次迭代中，節(jié)點不能有效的把其標簽傳播出去.為此節(jié)點按訪問順序逆序設置其傳播強度，從而降低訪問順序?qū)Y果的影響.

4.2.3 小結

表3為代表性算法采用的策略及時間復雜度，表中符號‘/’表示與原算法LPA保持一致.需要注意的是，在解決平局策略相應標有的‘/’，盡管仍是隨機選擇，已與原算法的隨機選擇的含義不同.例如表中算法WILPAS，把與節(jié)點v最相似鄰居的標簽更新為其標簽，這種相似性不僅基于與鄰居的共同鄰居，而且與鄰居的節(jié)點度數(shù)有關，因此存在多個最相似鄰居標簽機率很低，某種程度上解決了平局問題引發(fā)的不確定性.從表中算法采用的策略可知，一大部分算法能夠同時解決平局問題和隨機順序引發(fā)的不確定性.

表3 解決不確定性的LPA算法策略，O1核心節(jié)點向外擴展，O2固定順序，S最大相似性鄰居標簽，D高鏈接密度的鄰居標簽，F(xiàn)最大計數(shù)

時間復雜度方面，表中u表示合并社團次數(shù)，d為節(jié)點度數(shù).時間復雜度為O(n2)及以上的算法已不適合處理大型網(wǎng)絡.

LDPA可能導致平凡檢測問題發(fā)生[31]，BLDLP和ASCD-LPA需要人為設置參數(shù).

表4中數(shù)據(jù)來源于前述相關論文，“-”表示缺乏相關數(shù)據(jù).表中可知性能最好的幾個算法為WILPAS，CenLPA，LPA-S與TS.在LFR生成網(wǎng)絡中，WILPAS的性能優(yōu)于CenLPA[34]，而LPA-S與TS算法時間代價高，不適合處理規(guī)模大的網(wǎng)絡數(shù)據(jù).

表4 解決不確定問題的代表性算法的在真實網(wǎng)絡上NMI值

綜上，能夠快速處理大規(guī)模網(wǎng)絡數(shù)據(jù)，且相對穩(wěn)定的基于LPA算法首推WILPAS.

4.3 標簽震蕩現(xiàn)象

標簽震蕩本質(zhì)是使得標簽更新迭代無法收斂.

由于隨機的異步更新方式能夠避免標簽震蕩，但會導致差的性能、弱魯棒性以及不適合并行計算.LPA-SYN算法[45]采用同步更新的方式，利用概率更新策略來避免標簽震蕩.文獻[45]的觀點認為標簽震蕩產(chǎn)生的主要原因是采用計數(shù)最大的鄰居標簽，然而在真實世界中，節(jié)點很大概率選擇鄰居中計數(shù)最大的標簽，也存在機會(概率)選擇其他標簽包括當前自己的標簽.

文獻[24]了半同步LPA算法.該算法分為兩階段：第1階段著色，使得任何相鄰節(jié)點的顏色不同，得到l個不同顏色的劃分D={D1，D2，…，Dl}.第2階段標簽傳播階段，重復以下操作直到達到終止條件：按劃分的下標j從小到大依次對Dj中的每一個節(jié)點v做如下處理，

基本的迭代終止條件是與上次迭代比較，所有節(jié)點的標簽沒有發(fā)生變化.由于標簽震蕩，這樣的終止條件有時會失效.文獻[7]提出如下終止條件(c1)：每個節(jié)點的標簽與其最大計數(shù)的鄰居標簽一致.如果存在多個最大計數(shù)的標簽，且該節(jié)點的標簽同樣為最大計數(shù)的標簽，這時保留該標簽[20]，否則隨機選一個，文獻[24]記這種版本的半同步LPA為LPA-Prec.

文獻[24]提出了一種方案保證算法的收斂性.該方案定義了標簽的優(yōu)先級(標簽用整數(shù)表示)，當標簽l>l*，那么l比l*更具優(yōu)先，若存在多個最大計數(shù)的標簽6時，則取最高優(yōu)先級的標簽，相應版本的LPA記為LPA-MAX[24].同步的LPA-MAX產(chǎn)生的標簽震蕩現(xiàn)象不超過兩趟，因此給出一個簡化版的c1的終止條件，記為c2：如果每個節(jié)點的標簽與其上一次迭代或上上一次迭代相同，則算法終止.文獻[24]把LPA-Prec和LPA-MAX的策略結合起來得到的半同步的LPA記為LPA-Prec-Max.

LPA-SYN最大的問題是在計算標簽概率時需要人工設定參數(shù)，不同的網(wǎng)絡結構需要設定不同參數(shù)[24，45].LPA-Prec要比其他算法更穩(wěn)定，而LPA-max最不穩(wěn)定但最快，LPA-Prec-Max是好的折衷[24].綜上所述，代表性算法推薦LPA-Prec-Max.

4.4 平凡檢測(trivial detection)問題

LPA算法在標簽傳播過程中存在類似的“馬太效應”.有些“強”社團會變得越來越大，甚至整個網(wǎng)絡最終變成一個社團.

4.4.1 基于引導標簽的方法

導致平凡檢測深層原因復雜，至今仍沒有完全探究清楚.其中一個可能的原因是在傳播過程中對標簽缺乏針對性的引導.為了避免發(fā)生平凡檢測問題，研究者主要通過3種不同策略引導標簽傳播.

第1種策略通過傳播跳數(shù)控制標簽的影響力[19]：

由于δ需要人為設置，文獻[46]提出了動態(tài)跳數(shù)衰減策略：按標簽發(fā)生變化的節(jié)點比例設置δ.文獻[46]工作同時又采用了節(jié)點偏好策略：把節(jié)點分為社團核心點和社團邊界點，在此基礎上提出了系列算法.

第2種策略是在迭代早期優(yōu)先擴展小社團.文獻[7]結果表明5次迭代后95%的節(jié)點達到了其最終狀態(tài)，因而杜絕平凡檢測需要早期干預，優(yōu)先擴展小社團.在第t次迭代時，只統(tǒng)計v的滿足如下條件的鄰居標簽的計數(shù)[47]：鄰居標簽對應的社團成員數(shù)小于c(t)，這里c(t)=n([kt/T]+1)/k，T為總迭代次數(shù)，t為第t次迭代，k為參數(shù)(文中k取50、100和200).t越小，迭代越處于早期，c(t)值也越小，越優(yōu)先擴大小的社團.在此基礎上，工作[48]又定義了不同的c(t).

第3種策略與上述策略不同，通過如下條件來抑制社團擴張：社團內(nèi)部鏈接密度強度達到一定條件時，免除該社團參與標簽傳播或社團合并過程[12].該條件在推遲形成大的社團方面起著關鍵作用.

4.4.2 基于公式的方法

文獻[20]通過修改目標函數(shù)H(公式(5))來避免平凡檢測：H′=H-λF，λ是F的權重，所有節(jié)點具有相同標簽時，F(xiàn)的值最大，因此F是用來抵消H從而避免平凡檢測；F的不同選擇，對應不同算法：LPAr[20]與LPAm[20].文獻[20]沒有解決隨機性.

LPAm傾向于陷入弱的局部模塊(modularity)最大值，而且算法不穩(wěn)定[49].為此，文獻[49]提出了一個改進的算法LPAm+解決弱的局部模塊最大值問題：組合使用LPAm和合并社團的方法.該方法在模塊值方面要優(yōu)于LPAm，并且更穩(wěn)定，然而更耗時間.結合最大隸屬系數(shù)[50]和LPAm，文獻[51]提出的LPAbp算法很好抑制了平凡檢測問題，但仍然沒有解決結果的不確定性.文獻[52]針對LPAm+存在的問題：在社團結構不明顯的網(wǎng)絡中容易陷入局部模塊值大，設計了基于啟發(fā)性的LPA算法.該算法“以退為進”，在某些時段，允許合并的社團不增加模塊值，從而避免陷入局部模塊最大，使得下一階段能夠更好的增加模塊值，但該算法需要針對不同網(wǎng)絡，人工確定參數(shù)，算法代價高O(mnlogn).

4.4.3 采用網(wǎng)絡構造的方法

LPAp算法[53]把標簽傳播轉換為網(wǎng)絡構造過程，而網(wǎng)絡構造過程中，滲流轉變(percolation transition)被認為導致產(chǎn)生大的連通分量，另一方面，滲流轉變可以被終止[54]，因而把阻止平凡檢測的方法對應為在網(wǎng)絡構造過程中防止?jié)B流轉變現(xiàn)象發(fā)生.然而該算法的不確定性問題仍然沒有解決.

4.4.4 基于記憶的方法

MemLPA[55]算法在標簽更新時，節(jié)點除了采納新標簽之外，還記錄保存了所有鄰居標簽.每個節(jié)點維護一個用來存儲標簽的列表，列表中每個元素記錄相應標簽的計數(shù).迭代更新時，選取該節(jié)點列表中計數(shù)最大的標簽作為該節(jié)點的標簽，而這個計數(shù)不僅是當前鄰居標簽所貢獻，而且還考慮了歷史狀態(tài)中標簽的貢獻值，這種策略防止最終結果返回單一大的社團.

4.4.5 小結

表5為為解決平凡檢測問題算法的時間復雜度，由表可知基本保持線性時間復雜性.

表5 解決平凡檢測問題的算法時間復雜度

涉及到基于引導標簽的方法有LPAD[19]、DPA[46]、CLPA[47]以及SSCLPA[12]等，總體而言該類方法優(yōu)于其他算法.

ODLAP[45]性能要比LPA略好，而DDALPA[46]檢測質(zhì)量較差，BDPA(與DPA)優(yōu)于這3個算法[46].在較小的網(wǎng)絡上，BDPA性能比LPAD[19]要好，當網(wǎng)絡增大時，LPAD傾向發(fā)現(xiàn)大的社團，modularity值更大.DPA算法無論在時間還是檢測質(zhì)量上都要優(yōu)于這些算法，在少部分真實網(wǎng)絡上(表6)，LPAm檢測的社團質(zhì)量優(yōu)于DPA，但其消耗了更多的時間[46]，因此，DPA是以上算法中比較好的選擇.

盡管SSCLPA是確定性算法，并且性能也相當不錯[12]，但在在生成網(wǎng)絡(LFR)，當μ=0.8附近時，SSCLPA檢測質(zhì)量低；在真實網(wǎng)絡中，如表6所示，DPA算法的質(zhì)量優(yōu)于SSCLPA和MemLPA.而文獻[47]實驗表明CLPA優(yōu)于DPA，尤其是網(wǎng)絡結構不明顯的情況下.綜上，推薦使用CLPA算法.

表6 算法在真實網(wǎng)絡中的modularity值

4.5 重疊社團檢測

為了檢測重疊社團，節(jié)點處理并記錄多個標簽.若某個節(jié)點擁有多個標簽，那它屬于多個社團.

具體的，每個節(jié)點x關聯(lián)一組(c，b)，c表示社團的標識(標簽)，b是隸屬系數(shù)：反映x屬于社團c的概率.第t次迭代時，通過某種方式把鄰居標簽傳給x，例如bt(c，x)=∑y∈Nxbt-1(c，y)/|Nx|，然后刪去所有小于規(guī)定閾值的隸屬系數(shù)(c，b)，對剩余的隸屬系數(shù)進行規(guī)約，使其滿足隸屬系數(shù)之和為1.

目前的算法可分為：1)多標簽傳播算法：節(jié)點的所有標簽都參與了傳播;2)單標簽傳播算法：雖然節(jié)點擁有多個標簽，但按一定規(guī)則只選擇一個標簽參與傳播.

4.5.1 多標簽傳播算法

算法COPRA[50]通過參數(shù)r來控制社團的重疊程度：節(jié)點最多同時屬于r個社團.每次迭代后刪去所有小于閾值1/r的隸屬系數(shù)(c，b)，然后進行規(guī)約.

多標簽傳播算法都是基于COPRA算法基礎上進行改進.改進的算法可分為兩大類.

第1類，首先抽取“rough core”：最小極大團(smallest maximal clique).對同一rough core節(jié)點賦予相同標簽[56，57]，然后進行標簽傳播.工作[56]采用同步的方式對所有節(jié)點進行標簽傳播.而工作[57]保持最小極大團內(nèi)的節(jié)點標簽不變，利用相似度作為權重，四周擴散標簽.

第2大類考慮了節(jié)點在網(wǎng)絡中所處位置以及相互之間相似性不同，導致所起的作用也不同.為此在標簽傳播時考慮了不同鄰居不同作用[58-61].

4.5.2 單標簽傳播算法

單標簽傳播算法同樣可分為兩類.一類是基于占優(yōu)勢標簽的方法[62-64].該類方法把節(jié)點的最大隸屬系數(shù)對應的標簽定義為占優(yōu)勢標簽，只有占優(yōu)勢標簽參與傳播，標簽傳播中同樣考慮了不同鄰居的不同作用.另一類是基于SLPA的方法[65，66].在標簽傳播過程中節(jié)保留了其所有標簽.標簽傳播規(guī)則為：節(jié)點x為listener時，其每個鄰居依據(jù)特定speaking規(guī)則(例如計數(shù)最大的標簽)發(fā)出一個標簽，x根據(jù)listening規(guī)則從鄰居中接受一個標簽：當前迭代中它所觀測到的最流行的標簽(例如：計數(shù)最大).

4.5.3 小結

表7列舉了相關算法的技術細節(jié).在標簽傳播策略中，除了SLPA，其余算法都是在COPRA的標簽傳播規(guī)則：

表7 代表性重疊社團檢測算法采用策略

bt(c，x)=∑y∈Nxbt-1(c，y)/|Nx|

的基礎上額外考慮了所列的信息.每次節(jié)點x的標簽更新結束后，刪除小于特定閾值的隸屬系數(shù)的標簽，r為全局設定的參數(shù)，而其它的閾值設置更為科學合理.SLPA則保留了所有標簽直到迭代結束后集中處理：刪掉小于指定閾值的隸屬系數(shù)的標簽.

算法NALPA計算復雜度為O(n2)，盡管復雜度高，但其檢測質(zhì)量較高[61].在不確定性方面，算法PLPA與SLPA接近[60]，但其適合在社團結構模糊的網(wǎng)絡(LFR網(wǎng)絡為μ>0.3)中檢測重疊社團[60].LINSIA是確定性算法，然而其性能較差[61].

算法LPAMNI、COPRA、SLPA和DLPA都需要設置參數(shù)，其中LPANNI借鑒了DLPA和WLPA[67]的一些優(yōu)點.在真實網(wǎng)絡中，依據(jù)穩(wěn)定性與社團的檢測質(zhì)量，SLPA、COPRA和DLPA穩(wěn)定性差，而WLPA較好，LPAMNI為最好[64].在不同規(guī)模和重疊密度、以及社團結構較模糊(μ=0.3)的LFR網(wǎng)絡中，LPANNI、DLPA 和SLPA檢測質(zhì)量較好，其中LPAMNI最好.而穩(wěn)定性方面LPAMNI和WLPA最好，DLPA次之，COPRA和SLPA最差[64].

綜上，忽略時間因素，NALPA性能最好；綜合時間與性能，推薦LPAMNI；當處理社團結構模糊的網(wǎng)絡(LFR網(wǎng)絡為μ>0.3)，推薦PLPA.

4.6 動態(tài)社團檢測

網(wǎng)絡分為6種狀態(tài)[68]：生成(birth)，壯大(growth)，收縮(shrink)，合并(merge)，分割(split)和消失(death)(見文獻[69]).

現(xiàn)有工作主要是對發(fā)生變化的節(jié)點集進行相應的如下操作：1)使用現(xiàn)有的各種LPA算法更新;2)提出新的標簽更新策略.

4.6.1 基于現(xiàn)有的LPA算法的動態(tài)更新

在發(fā)生變化的節(jié)點集上，使用現(xiàn)有的基于LPA算法進行標簽更新[25，70-72].這些方法除了使用不同的基于LPA的方法之外，最大的區(qū)別是對變化的節(jié)點集的定義.工作[71]定義變化節(jié)點集為發(fā)生變化的節(jié)點集合.而工作[25]和[72]則把其定義為發(fā)生變化的節(jié)點及其鄰居的集合.工作[70]進一步擴充了變化的節(jié)點集合，使其包含了變化節(jié)點所屬社團的所有節(jié)點.

4.6.2 基于新策略的動態(tài)更新方法

針對動態(tài)環(huán)境下存在的一些問題，研究者提出了系列標簽更新策略[63，69，73-74].例如，為解決動態(tài)環(huán)境下的平凡檢測問題，基于邊的權重和隨傳播跳數(shù)增加而標簽影響力減弱這兩個因素，工作[73]設計了標簽更新策略；針對新節(jié)點很少有機會創(chuàng)造新社團，工作[74]結合LPA和信息擴散CID模型[75]設計標簽更新策略；針對基于團(clique)的算法[69，76]在動態(tài)社團檢測存在如下兩個缺陷：1)每次網(wǎng)絡變化，需重新計算團(clique);2)大小至少為k的團才能組成社團，這就導致大量的外圍節(jié)點不屬于任何社團，為此工作[69]把節(jié)點劃分為核心節(jié)點和外圍節(jié)點基礎上設計標簽傳播策略；為避免相鄰網(wǎng)絡快照的社團結果變化劇烈，工作[63]結合最近一次網(wǎng)絡快照和當前網(wǎng)絡標簽情況進行標簽傳播.

為了有效進行動態(tài)更新標簽，除了工作[63]，大部分工作只在發(fā)生的變化的節(jié)點集上運用相應的標簽更新策略.

4.6.3 小 結

表8為動態(tài)社團檢測算法分類.RWSALPA和SBSALPA檢測出的社團質(zhì)量較高，而且RWSALPA要比SBSALPA更具優(yōu)勢，在高度重疊的社團網(wǎng)絡中，RWSALPA、SBSALPA比SLPAD、DLPAE 更好[73]；然而RWSALPA和SBSALPA算法時間復雜性高O(nm)，喪失了LPA算法的接近線性的時間復雜性的優(yōu)點，因此二者不適合處理大規(guī)模數(shù)據(jù).CIDLPA性能優(yōu)于SLPAD與DLPAE，而SLPAD優(yōu)于LabelRankT算法，盡管CIDLPA要比SLPAD和DLPAE處理時間方面稍慢，但三者的時間復雜性基本相同，因此綜合起來推薦CIDLPA檢測大規(guī)模動態(tài)重疊社團[73]；以上算法都是檢測動態(tài)重疊社團，而DLPAE能夠檢測非重疊社團，因此在檢測動態(tài)非重疊社團方面推薦DLPAE算法.所有動態(tài)檢測的方法，隨著快照增加，性能在降低，原因是只關注變化的部分，而忽略整體的網(wǎng)絡.動態(tài)社團檢測仍然屬于研究的起步階段.

表8 動態(tài)社團檢測算法

4.7 其他算法

本節(jié)簡介由于沒有明顯特征而無法歸納到以上6個分類之中的方法.

文獻[77]提出了基于邊標簽的傳播算法，文獻[78]利用圖的一些簡單特征(帶權度數(shù)，聚類系數(shù))，采用機器學習的方法把邊分為3大類：社團內(nèi)的邊，社團間的邊，無法判斷的邊；把屬同一社團的節(jié)點聚合起來，進行標簽傳播.文獻[80]將LPA思想應用到二部圖的網(wǎng)絡粗化(network coarsening)策略中，使相應算法的復雜度降低為線性.基于一組種子節(jié)點(seed vertices)，文獻[80]利用LPA策略檢測相應的一個最佳局部社團.文獻[81]在分布式系統(tǒng)進行基于LPA的社團檢測.

5 總 結

以時間為跨度單位總結LPA算法的發(fā)展，第1階段(2007-2010)為開始階段，在LPA算法發(fā)表一年后出現(xiàn)了一些工作，主要集中在解決LPA的平凡檢測問題[19-20，49]，另外提出了首個基于LPA的重疊社團檢測算法CORPA以及解決標簽震蕩問題的改進算法[24].

第2階段(2011-2015)為發(fā)展階段，算法集中在解決不確定性、重疊社團檢測、動態(tài)檢測以及解決平凡檢測問題上.其中大部分工作是為了解決不確定性問題，重疊社團檢測方面，首次提出了單標簽算法SLPA，期間也出現(xiàn)了動態(tài)網(wǎng)絡上的社團檢測算法，這階段盡管關于平凡檢測的算法很少，但提出了較為優(yōu)秀的算法DPA以及代表性算法CLPA.

第3階段(2016-2020)為逐漸成熟階段，這一時期的工作更為細致，產(chǎn)生了表9所列的大多數(shù)代表性算法：WILPAS、LPANNI、PLPA和CIDLPA.總體來講，該階段大部分的工作集中在重疊檢測、解決不確定性問題以及動態(tài)網(wǎng)絡上的社團檢測.

盡管表9列出了代表性算法，但是其它算法的優(yōu)秀設計思想同樣值得借鑒.這里給出這些代表性算法使用場景的建議，對于非重疊社團檢測，當網(wǎng)絡的社團結構較明顯時建議使用WILPAS算法，若該算法無法收斂或網(wǎng)絡為二部圖時，采用LPA-Prec-Max算法，社團結構不明顯時采用CLPA，重疊社團檢測推薦LPAMNI，當處理社團結構模糊的網(wǎng)絡(μ>0.3)，推薦PLPA.動態(tài)網(wǎng)絡上的重疊社團檢測推薦CIDLPA、非重疊社團檢測推薦DLPAE.

表9 代表性算法

6 展 望

LPA算法的收斂性至關重要，對于作者合作網(wǎng)絡，原始LPA算法迭代10000次后仍有10%節(jié)點的標簽發(fā)生變化[46]，為了防止無限迭代下去，一般設置一個最大迭代次數(shù).探討基于LPA算法在復雜網(wǎng)絡中收斂性仍然是一個開放性問題.

基于LPA的算法主要集中在提高社團檢測質(zhì)量，解決不確定性、標簽震蕩現(xiàn)象以及平凡檢測等問題上.這些算法只針對其中的若干個問題，在保持現(xiàn)有時間復雜度不變以及保證質(zhì)量前提下，如何設計LPA算法使得同時解決不確定性、標簽震蕩現(xiàn)象以及平凡檢測問題需要繼續(xù)深入探索.

目前，基于LPA算法主要應用在同構網(wǎng)絡.同構網(wǎng)絡已不足以應對現(xiàn)實中問題，異構網(wǎng)絡在生活中普遍存在[82，83].另外，真實世界的許多復雜網(wǎng)絡中都存在對立的關系，尤其是在信息、生物和社會領域，這些網(wǎng)絡表示為符號網(wǎng)絡[84].如何將LPA思想移植到異構網(wǎng)絡和符號網(wǎng)絡進行社團檢測有很大的研究空間和較高的研究價值.

最近，研究者結合機器學習和LPA方法[66，78]進行社團發(fā)現(xiàn)，然而這些方法沒能有機的融合機器學習和LPA，機器(深度)學習成為當下的研究熱點，涌現(xiàn)出眾多的優(yōu)秀思想，如何借鑒這些優(yōu)秀思想，使其與LPA有機融合，在超大網(wǎng)絡中快速有效檢測社團是未來值得研究的一個方向.