面向標(biāo)簽傳播算法的社團(tuán)檢測(cè)研究現(xiàn)狀及展望

張應(yīng)龍，夏學(xué)文，徐 星，喻 飛，吳泓潤，余 鷹

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

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

1 引 言

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

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

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

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

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

2 基礎(chǔ)知識(shí)

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

本文所涉真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集統(tǒng)計(jì)信息如表1所示.這些數(shù)據(jù)集一個(gè)共同特點(diǎn)是其上的真實(shí)社團(tuán)結(jié)構(gòu)為已知，更多詳情見文獻(xiàn)[12].

表1 本文所涉及的真實(shí)網(wǎng)絡(luò)統(tǒng)計(jì)信息

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

文中常用符號(hào)見表2.

表2 文中常用符號(hào)描述

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

(1)

Edge-clustering coefficient(ECC)[15]：

(2)

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

2.2 評(píng)價(jià)指標(biāo)

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

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

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

NMI用來評(píng)價(jià)一個(gè)社團(tuán)劃分X與基準(zhǔn)劃分Y相比的準(zhǔn)確程度：

ci為第i個(gè)社團(tuán)，CX和CY分別是X和Y對(duì)應(yīng)的社團(tuán)數(shù).NMI的值域是0到1，越高代表被評(píng)價(jià)的算法越準(zhǔn).特殊的，社團(tuán)劃分和基準(zhǔn)劃分完全一致，則NMI值為1.

3 LPA算法簡介與分析

3.1 社團(tuán)定義

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

集合{ci|ci?V，∪1≤i≤kci=V，1≤i≤k}為網(wǎng)絡(luò)G上一組社團(tuán)，對(duì)于1≤i≤k，1≤j≤k，i≠j，當(dāng)ci∩cj=?，即任何兩個(gè)社團(tuán)都沒有交集，這時(shí)為非重疊社團(tuán)，當(dāng)存在ci∩cj≠?時(shí)，即存在兩個(gè)社團(tuán)有交集，對(duì)應(yīng)稱為重疊社團(tuán).

3.2 LPA算法

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

a)每個(gè)節(jié)點(diǎn)賦予一個(gè)唯一標(biāo)簽，這時(shí)每個(gè)節(jié)點(diǎn)當(dāng)作一個(gè)單獨(dú)社團(tuán).

b)隨機(jī)順序更新節(jié)點(diǎn)標(biāo)簽，對(duì)于節(jié)點(diǎn)v，賦予其最大計(jì)數(shù)的鄰居標(biāo)簽：

(3)

c)重復(fù)過程b)，直到所有的節(jié)點(diǎn)擁有其計(jì)數(shù)最大的鄰居標(biāo)簽時(shí)終止迭代.

最終，緊密連接的節(jié)點(diǎn)間形成共識(shí)采納相同標(biāo)簽組成一個(gè)社團(tuán)，不同標(biāo)簽的節(jié)點(diǎn)組構(gòu)成不同的社團(tuán)[7].為了敘述方便，在上下文不引起歧義的情況下，文中把社團(tuán)和標(biāo)簽等同對(duì)待.

LPA有兩種更新節(jié)點(diǎn)標(biāo)簽方式：同步與異步.

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

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

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

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

(4)

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

(5)

例如當(dāng)更新節(jié)點(diǎn)x的標(biāo)簽時(shí)，公式(5)變換為：

(6)

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

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

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

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

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

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

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

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

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

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

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

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

4 基于LPA的社團(tuán)檢測(cè)算法

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

4.1 提高算法性能

現(xiàn)分析導(dǎo)致LPA算法性能不高的原因及相應(yīng)解決對(duì)策.

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

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

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

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

4.2 不確定性(Randomness)

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

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

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

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

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

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

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

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

4.2.2 隨機(jī)順序引起的不確定性

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

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

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

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

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

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

4.2.3 小結(jié)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.4 平凡檢測(cè)(trivial detection)問題

LPA算法在標(biāo)簽傳播過程中存在類似的“馬太效應(yīng)”.有些“強(qiáng)”社團(tuán)會(huì)變得越來越大，甚至整個(gè)網(wǎng)絡(luò)最終變成一個(gè)社團(tuán).

4.4.1 基于引導(dǎo)標(biāo)簽的方法

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

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

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

第2種策略是在迭代早期優(yōu)先擴(kuò)展小社團(tuán).文獻(xiàn)[7]結(jié)果表明5次迭代后95%的節(jié)點(diǎn)達(dá)到了其最終狀態(tài)，因而杜絕平凡檢測(cè)需要早期干預(yù)，優(yōu)先擴(kuò)展小社團(tuán).在第t次迭代時(shí)，只統(tǒng)計(jì)v的滿足如下條件的鄰居標(biāo)簽的計(jì)數(shù)[47]：鄰居標(biāo)簽對(duì)應(yīng)的社團(tuán)成員數(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)先擴(kuò)大小的社團(tuán).在此基礎(chǔ)上，工作[48]又定義了不同的c(t).

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

4.4.2 基于公式的方法

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

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

4.4.3 采用網(wǎng)絡(luò)構(gòu)造的方法

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

4.4.4 基于記憶的方法

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

4.4.5 小結(jié)

表5為為解決平凡檢測(cè)問題算法的時(shí)間復(fù)雜度，由表可知基本保持線性時(shí)間復(fù)雜性.

表5 解決平凡檢測(cè)問題的算法時(shí)間復(fù)雜度

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

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

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

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

4.5 重疊社團(tuán)檢測(cè)

為了檢測(cè)重疊社團(tuán)，節(jié)點(diǎn)處理并記錄多個(gè)標(biāo)簽.若某個(gè)節(jié)點(diǎn)擁有多個(gè)標(biāo)簽，那它屬于多個(gè)社團(tuán).

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

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

4.5.1 多標(biāo)簽傳播算法

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

多標(biāo)簽傳播算法都是基于COPRA算法基礎(chǔ)上進(jìn)行改進(jìn).改進(jìn)的算法可分為兩大類.

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

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

4.5.2 單標(biāo)簽傳播算法

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

4.5.3 小結(jié)

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

表7 代表性重疊社團(tuán)檢測(cè)算法采用策略

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

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

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

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

綜上，忽略時(shí)間因素，NALPA性能最好；綜合時(shí)間與性能，推薦LPAMNI；當(dāng)處理社團(tuán)結(jié)構(gòu)模糊的網(wǎng)絡(luò)(LFR網(wǎng)絡(luò)為μ>0.3)，推薦PLPA.

4.6 動(dòng)態(tài)社團(tuán)檢測(cè)

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

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

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

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

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

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

為了有效進(jìn)行動(dòng)態(tài)更新標(biāo)簽，除了工作[63]，大部分工作只在發(fā)生的變化的節(jié)點(diǎn)集上運(yùn)用相應(yīng)的標(biāo)簽更新策略.

4.6.3 小 結(jié)

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

表8 動(dòng)態(tài)社團(tuán)檢測(cè)算法

4.7 其他算法

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

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

5 總 結(jié)

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

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

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

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

表9 代表性算法

6 展 望

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

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

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

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