陳界全 王占全* 李 真 湯敏偉

1(華東理工大學(xué)信息科學(xué)與工程學(xué)院 上海 200237) 2(天翼電子商務(wù)有限公司風(fēng)險(xiǎn)管理部 上海 200080)

0 引 言

社區(qū)檢測(cè)是一種在網(wǎng)絡(luò)中探索集群或社區(qū)的行為。集群或者社區(qū)是一組緊密連接的實(shí)體，它們?cè)诮M內(nèi)的連接比與其他實(shí)體的連接更高[1]。對(duì)各種領(lǐng)域的真實(shí)網(wǎng)絡(luò)進(jìn)行社區(qū)的發(fā)現(xiàn)，對(duì)于理解復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)和模式起著重要的作用。例如，在社交網(wǎng)絡(luò)領(lǐng)域，可以根據(jù)不同的興趣和背景將其劃分為不同的社會(huì)群體進(jìn)行準(zhǔn)確的推薦；在生物學(xué)領(lǐng)域，傳播網(wǎng)絡(luò)由疾病和病毒兩部分組成，通過對(duì)其進(jìn)行研究和分析，找到易感染人群的關(guān)鍵社區(qū)或關(guān)鍵節(jié)點(diǎn)，預(yù)測(cè)傳播路徑，從而及時(shí)控制疾病。綜上所述，社區(qū)檢測(cè)在復(fù)雜網(wǎng)絡(luò)的研究中有重要意義。

然而，目前的研究主要集中在檢測(cè)非重疊的社區(qū)，然而真實(shí)社交網(wǎng)絡(luò)中的社區(qū)通常是互相重疊的[2]。例如，一個(gè)研究者可能屬于多個(gè)研究群組中，一個(gè)人在現(xiàn)實(shí)生活或者網(wǎng)絡(luò)中會(huì)加入多個(gè)興趣小組。所以，重疊社區(qū)的發(fā)現(xiàn)對(duì)于進(jìn)一步分析和利用復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)具有重要的意義，重疊社區(qū)如圖1所示。

圖1 重疊社區(qū)

本文提出一種改進(jìn)的重疊社區(qū)發(fā)現(xiàn)算法(L-SLPA)，其擴(kuò)展了SLPA，在算法的初始階段先對(duì)網(wǎng)絡(luò)進(jìn)行一次非重疊社區(qū)劃分，然后給同一社區(qū)中的節(jié)點(diǎn)分配相同的標(biāo)簽，而不是像SLPA一樣給所有的節(jié)點(diǎn)分配不同的標(biāo)簽。標(biāo)簽分配完成后，僅對(duì)邊界節(jié)點(diǎn)執(zhí)行Speaker-Listener標(biāo)簽傳遞的迭代過程，最后對(duì)各節(jié)點(diǎn)包含的所有標(biāo)簽進(jìn)行過濾。

1 相關(guān)工作

1.1 重疊社區(qū)發(fā)現(xiàn)算法

重疊社區(qū)結(jié)構(gòu)更加貼合現(xiàn)實(shí)網(wǎng)絡(luò)的實(shí)際情況，這一理論和實(shí)踐上的重要意義促使世界上很多研究人員對(duì)復(fù)雜網(wǎng)絡(luò)的社區(qū)進(jìn)行研究，很多有效的模型被不斷提出。派系過濾算法(CPM)基于這樣的假設(shè)：一個(gè)社區(qū)由重疊的完全連接的子圖集組成，并通過搜索相鄰的團(tuán)來檢測(cè)社區(qū)[3]，它適用于密集連接的網(wǎng)絡(luò)中，對(duì)于稀疏的網(wǎng)絡(luò)算法效率將會(huì)變得很低。Raghavan等[4]提出了一種簡(jiǎn)單的標(biāo)簽傳播算法(Label Propagation Algorithms)，每個(gè)節(jié)點(diǎn)都用一個(gè)唯一的標(biāo)簽初始化，并且在每一步中，每個(gè)節(jié)點(diǎn)都采用它的大多數(shù)鄰居當(dāng)前擁有的標(biāo)簽。該算法時(shí)間復(fù)雜度低、簡(jiǎn)單、實(shí)用性強(qiáng)、效果好。Gregory等[5]基于LPA引入了社區(qū)從屬系數(shù)，提出具備重疊社區(qū)發(fā)現(xiàn)能力的COPRA，但是該算法并沒有解決標(biāo)簽傳播所帶來的隨機(jī)性問題。Lancichinetti等[6]定義了一個(gè)可以衡量節(jié)點(diǎn)緊密連接程度的fitness函數(shù)，LFM算法隨機(jī)選擇一個(gè)沒有被分配社區(qū)的節(jié)點(diǎn)作為種子，通過優(yōu)化fitness函數(shù)以形成一個(gè)社區(qū)，但是LFM算法較高的時(shí)間復(fù)雜度使得其在大型網(wǎng)絡(luò)中的效率并不理想。

1.2 Louvain算法

Blondel等[7]提出的基于啟發(fā)式和模塊度Q優(yōu)化的Louvain算法，是一種近線性運(yùn)行時(shí)間的貪婪算法。該算法對(duì)多層次的圖進(jìn)行操作，在每個(gè)層次上應(yīng)用頂點(diǎn)移動(dòng)程序(VM)來提高模塊性,具有運(yùn)行速度快、效果穩(wěn)定等優(yōu)點(diǎn)。

(1)

(2)

式中：Aij為節(jié)點(diǎn)i和節(jié)點(diǎn)j之間邊的權(quán)值；ki為與頂點(diǎn)i相連的邊的權(quán)值和；ci為頂點(diǎn)i所在的社區(qū)；m為圖中所有邊的數(shù)量的1/2；如果u=v則δ(u,v)為1，反之為0；∑in為社區(qū)c中所有邊的權(quán)重和;∑tot為社區(qū)c中節(jié)點(diǎn)關(guān)聯(lián)的所有邊的權(quán)值和；ki,in為頂點(diǎn)與社區(qū)c中節(jié)點(diǎn)所有相連邊的權(quán)重和。

1.3 SLPA

SLPA(Speaker-ListenerLabel Propagation Algorithms)是一種基于一般說話者和收聽者的信息傳播過程的算法。SLPA在LPA的基礎(chǔ)上引入了Speaker(標(biāo)簽傳播節(jié)點(diǎn))和Listener(標(biāo)簽接受節(jié)點(diǎn))兩個(gè)概念[8]，如圖2所示。它根據(jù)成對(duì)的交互規(guī)則在節(jié)點(diǎn)之間傳播標(biāo)簽。當(dāng)一個(gè)節(jié)點(diǎn)忘記了在前一個(gè)迭代中獲得的知識(shí)時(shí)，SLPA為每個(gè)節(jié)點(diǎn)提供一個(gè)大小為T的內(nèi)存來存儲(chǔ)接收到的信息(即標(biāo)簽)。節(jié)點(diǎn)內(nèi)存中觀察到標(biāo)簽的概率被解釋為成員強(qiáng)度。SLPA不需要提前指定社區(qū)數(shù)量，時(shí)間復(fù)雜度為O(Tm)，與邊數(shù)m呈線性關(guān)系，其中T為預(yù)定義的最大迭代次數(shù)(如T≥20)。SLPA還可以通過一般化交互規(guī)則(SLPAw)來適應(yīng)加權(quán)和定向網(wǎng)絡(luò)。

圖2 SLPA中的Speaker和Listener

SLPA的大致步驟如下：

(1) 初始化每個(gè)節(jié)點(diǎn)，給每個(gè)節(jié)點(diǎn)一個(gè)唯一的標(biāo)簽。

(2) 隨機(jī)挑選一個(gè)節(jié)點(diǎn)作為L(zhǎng)istener，其鄰居節(jié)點(diǎn)為Speaker。

(3) Speaker以各個(gè)標(biāo)簽在其內(nèi)存所有標(biāo)簽中存在概率隨機(jī)發(fā)送一個(gè)標(biāo)簽，Listener接收所有發(fā)送過來的標(biāo)簽中最多的那個(gè)標(biāo)簽。

(4) 統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)各類標(biāo)簽數(shù)量，將個(gè)數(shù)超過要求的標(biāo)簽作為節(jié)點(diǎn)最終的社團(tuán)標(biāo)簽。

但是由于SLPA在初始化過程中，為每個(gè)節(jié)點(diǎn)都分配了一個(gè)唯一的標(biāo)簽，對(duì)于復(fù)雜網(wǎng)絡(luò)而言，標(biāo)簽的分配和傳播會(huì)消耗大量的資源。而且標(biāo)簽的傳播過程中的隨機(jī)選擇策略會(huì)造成SLPA的不穩(wěn)定性和隨機(jī)性。

2 基于SLPA優(yōu)化的社區(qū)發(fā)現(xiàn)算法

在SLPA的初始階段，每個(gè)節(jié)點(diǎn)都被分配了一個(gè)單獨(dú)的標(biāo)簽，當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)，這無疑消耗了巨大的資源。所以，可以先對(duì)復(fù)雜的網(wǎng)絡(luò)進(jìn)行一次初步的劃分，然后給相似的一類節(jié)點(diǎn)分配一個(gè)相同的標(biāo)簽，這樣能夠大大減少標(biāo)簽分配的資源消耗。同時(shí)，重疊節(jié)點(diǎn)通常處于社區(qū)的邊緣，因此，本文在改進(jìn)的算法中引入了邊界節(jié)點(diǎn)的概念(定義3)。在T次迭代中，只需要對(duì)邊界節(jié)點(diǎn)進(jìn)行Speaker-Listener的標(biāo)簽傳遞過程，而不是對(duì)所有的節(jié)點(diǎn)都進(jìn)行標(biāo)簽傳遞，從而提高算法的效率。最后根據(jù)閾值r，過濾每個(gè)節(jié)點(diǎn)中的無效標(biāo)簽(定義4)，保留下來的標(biāo)簽所對(duì)應(yīng)的社區(qū)即為該節(jié)點(diǎn)歸屬的社區(qū)。

定義1一個(gè)復(fù)雜網(wǎng)絡(luò)可以表示為G=(V,E)，E為所有邊的集合。

定義2假設(shè)網(wǎng)絡(luò)G劃分得到的社區(qū)集為C={c1,c2,…,cn}，ci表示劃分得到的第i個(gè)社區(qū)。

定義3對(duì)于G=(V,E)的社區(qū)劃分C={c1,c2,…,cn}，若vi∈ci，vj∈cj，i≠j，并且?eij∈E(eij為兩節(jié)點(diǎn)間的邊)，則稱vi和vj為邊界節(jié)點(diǎn)。

定義4當(dāng)某類標(biāo)簽li出現(xiàn)的概率P(li)小于閾值r，則將該標(biāo)簽稱為無效標(biāo)簽，具體條件表示為：

(3)

本文將改進(jìn)后的算法稱為L(zhǎng)-SLPA，算法的具體步驟如算法1所示。其中步驟1-步驟3為非重疊社區(qū)劃分階段，步驟4-步驟5為標(biāo)簽分配和邊界節(jié)點(diǎn)統(tǒng)計(jì)階段，步驟6-步驟9為Speaker-Listener標(biāo)簽傳遞的迭代階段。

算法1L-SLPA

輸入：復(fù)雜網(wǎng)絡(luò)G(V,E)。

輸出：重疊社區(qū){c1,c2,…,cn}。

步驟1初始化所有節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)為一個(gè)單獨(dú)的社區(qū)。

步驟2每個(gè)節(jié)點(diǎn)分別加入鄰居社區(qū)中，按式(2)計(jì)算模塊度增益ΔQ。假如存在ΔQ大于零，則將該節(jié)點(diǎn)加入ΔQ最大的社區(qū)中。

步驟3將社區(qū)合并成超點(diǎn)，重復(fù)步驟1和步驟2，直到模塊度Q不再變化。

步驟4為同社區(qū)中的節(jié)點(diǎn)分配一個(gè)相同的標(biāo)簽，不同社區(qū)中的節(jié)點(diǎn)分配到的標(biāo)簽不同。

步驟5統(tǒng)計(jì)邊界節(jié)點(diǎn)。

步驟6在邊界節(jié)點(diǎn)中隨機(jī)挑選一個(gè)節(jié)點(diǎn)作為L(zhǎng)istener，其鄰居節(jié)點(diǎn)為Speaker。

步驟7Speaker以各個(gè)標(biāo)簽在其內(nèi)存所有標(biāo)簽中存在概率隨機(jī)發(fā)送一個(gè)標(biāo)簽，Listener接收所有發(fā)送過來的標(biāo)簽中最多的那個(gè)標(biāo)簽。

步驟8重復(fù)步驟6和步驟7，直到達(dá)到最大迭代次數(shù)T。

步驟9統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)各類標(biāo)簽的數(shù)量，根據(jù)閾值r，過濾無效標(biāo)簽，將剩下的標(biāo)簽作為節(jié)點(diǎn)最終的社團(tuán)標(biāo)簽。

假設(shè)有這樣一個(gè)圖，其中包含7個(gè)節(jié)點(diǎn)和11條邊。先對(duì)其進(jìn)行非重疊社區(qū)發(fā)現(xiàn)，節(jié)點(diǎn)1-節(jié)點(diǎn)3被劃分為社區(qū)1，節(jié)點(diǎn)4-節(jié)點(diǎn)7被劃分為社區(qū)2。給社區(qū)1中的所有節(jié)點(diǎn)分配一個(gè)標(biāo)簽1，給社區(qū)2中的所有節(jié)點(diǎn)分配一個(gè)標(biāo)簽2。同時(shí)，圖中的節(jié)點(diǎn)1、節(jié)點(diǎn)3、節(jié)點(diǎn)4和節(jié)點(diǎn)7為邊界節(jié)點(diǎn)，對(duì)這4個(gè)邊界節(jié)點(diǎn)執(zhí)行Speaker-Listener的標(biāo)簽傳遞過程。算法結(jié)束后，發(fā)現(xiàn)節(jié)點(diǎn)1同時(shí)包含著標(biāo)簽1和標(biāo)簽2，則可以認(rèn)為，節(jié)點(diǎn)1同時(shí)歸屬于兩個(gè)社區(qū)，是一個(gè)重疊節(jié)點(diǎn)，如圖3所示。

圖3 L-SLPA舉例

當(dāng)復(fù)雜網(wǎng)絡(luò)的規(guī)模不斷增大，時(shí)間復(fù)雜度是算法需要考慮的一個(gè)重要問題。在本文算法的第一階段，非重疊社區(qū)發(fā)現(xiàn)的時(shí)間復(fù)雜度為O(m)，其中m為復(fù)雜網(wǎng)絡(luò)中邊的數(shù)量。第二階段中，統(tǒng)計(jì)邊界節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(m)，SLPA的整個(gè)標(biāo)簽傳遞過程的時(shí)間復(fù)雜度為O(Tn)，其中：T為算法的迭代次數(shù)；n為節(jié)點(diǎn)的數(shù)量。所以，L-SLPA整體的時(shí)間復(fù)雜度為O(m+Tn)，基本與網(wǎng)絡(luò)中邊的數(shù)量呈線性關(guān)系。

3 實(shí) 驗(yàn)

本文將L-SLPA與幾種具有代表性的重疊社區(qū)發(fā)現(xiàn)算法進(jìn)行對(duì)比，分別為SLPA、Copra[5](另一種標(biāo)簽傳播算法)、CPM算法[3](派系過濾算法)和LFM算法[6](一種基于適應(yīng)度函數(shù)的社區(qū)擴(kuò)展算法)，以驗(yàn)證L-SLPA的性能。本文實(shí)驗(yàn)所有算法均采用Python實(shí)現(xiàn)，運(yùn)行環(huán)境為PC，基本配置：CPU為3.1 GHz Intel Core i5，內(nèi)存為8 GB。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文選取了6個(gè)規(guī)模不同的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集[9-17]，對(duì)改進(jìn)的L-SLPA及4種對(duì)比的重疊社區(qū)發(fā)現(xiàn)算法進(jìn)行測(cè)試。真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集的具體參數(shù)如表1所示。

表1 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

Lancichinetti 等[18]提出的LFR基準(zhǔn)網(wǎng)絡(luò)被廣泛應(yīng)用于復(fù)雜網(wǎng)絡(luò)分析中，通過調(diào)整參數(shù)生成規(guī)模不同的人工合成數(shù)據(jù)集。本文實(shí)驗(yàn)中的基準(zhǔn)測(cè)試網(wǎng)絡(luò)參數(shù)設(shè)置如表2所示，其中：節(jié)點(diǎn)的數(shù)量N分別被設(shè)為1 000和5 000；節(jié)點(diǎn)的平均度k被設(shè)為10；最大的節(jié)點(diǎn)度kmax為50；混合參數(shù)μ控制著網(wǎng)絡(luò)中潛在的社區(qū)結(jié)構(gòu)，μ越大社區(qū)結(jié)構(gòu)越模糊，μ被設(shè)置為0.1和0.3；社區(qū)的規(guī)模設(shè)定為10～50之間；重疊節(jié)點(diǎn)數(shù)量on為總節(jié)點(diǎn)數(shù)的10%；每個(gè)節(jié)點(diǎn)歸屬的社區(qū)數(shù)om則為2～8。

表2 LFR基準(zhǔn)網(wǎng)絡(luò)參數(shù)

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

3.2.1重疊模塊度QE

模塊度Q是由Newman提出，用于評(píng)價(jià)社區(qū)劃分結(jié)果的好壞，但是該函數(shù)僅適用于非重疊社區(qū)劃分的結(jié)果。為了能夠合理地評(píng)價(jià)重疊社區(qū)發(fā)現(xiàn)的結(jié)果，Chen等[19]在模塊度函數(shù)的基礎(chǔ)上提出了重疊社區(qū)的模塊度指標(biāo)QE，QE的值在0到1之間，值越高代表社區(qū)劃分得越準(zhǔn)確。

(4)

式中：m為圖中邊的總數(shù)；A為網(wǎng)絡(luò)的鄰接矩陣，若節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在一條邊，則Aij=1，反之為0；ki、kj分別為節(jié)點(diǎn)i和節(jié)點(diǎn)j的度；oi、oj為節(jié)點(diǎn)i和j所屬的社區(qū)數(shù)。

3.2.2標(biāo)準(zhǔn)互信息NMI

模塊度能夠?qū)ι鐖F(tuán)劃分結(jié)果好壞進(jìn)行評(píng)價(jià)。如果知道網(wǎng)絡(luò)的真實(shí)社區(qū)劃分情況，則可以通過得到的社區(qū)劃分結(jié)果與真實(shí)的社區(qū)劃分情況進(jìn)行對(duì)比，這樣就能測(cè)算出社區(qū)發(fā)現(xiàn)算法的準(zhǔn)確性。NMI(標(biāo)準(zhǔn)化互信息)[6]，評(píng)價(jià)一個(gè)社區(qū)劃分和標(biāo)準(zhǔn)劃分結(jié)果之間差異性的指標(biāo)，通常被用來評(píng)價(jià)一個(gè)社區(qū)發(fā)現(xiàn)算法的準(zhǔn)確性。NMI的值在0到1之間，值越高代表社區(qū)劃分得越準(zhǔn)確。

(5)

式中：X和Y分別代表真實(shí)的社區(qū)結(jié)構(gòu)和社區(qū)發(fā)現(xiàn)算法得到的社區(qū)結(jié)構(gòu)；H(X|Y)norm和H(Y|X)norm為社區(qū)分布的條件信息熵。

3.3 算法參數(shù)選取

L-SLPA最終的結(jié)果依賴于閾值r和T的選取。其中r的取值范圍為0～1，如果閾值r取值過小，很多節(jié)點(diǎn)會(huì)被錯(cuò)誤地劃分為重疊節(jié)點(diǎn)，影響重疊劃分結(jié)果的準(zhǔn)確性，但是當(dāng)閾值r的取值接近1時(shí)，又會(huì)使該算法退化成非重疊社區(qū)發(fā)現(xiàn)算法。本文在N=1 000的人工數(shù)據(jù)集上測(cè)試選取不同閾值r時(shí)算法結(jié)果的收斂情況，根據(jù)圖4可以發(fā)現(xiàn)，當(dāng)r大于0.04時(shí)，算法檢測(cè)到的社區(qū)數(shù)量和真實(shí)社區(qū)數(shù)量之比趨于穩(wěn)定。所以，本文在后續(xù)的實(shí)驗(yàn)中取r的值為0.05。

圖4 閾值r的收斂表現(xiàn)

根據(jù)圖5可以發(fā)現(xiàn)，隨著算法的最大迭代次數(shù)T取值的增大，算法的準(zhǔn)確性會(huì)有增長(zhǎng)的趨勢(shì)，但是過多的迭代次數(shù)會(huì)降低算法的運(yùn)行速度。因?yàn)門大于20后，更多的迭代次數(shù)并沒有給算法結(jié)果帶來很大的提升，所以在本文中，選取T的值為20。

圖5 迭代次數(shù)T的收斂表現(xiàn)

3.4 實(shí)驗(yàn)結(jié)果

本文首先在6個(gè)規(guī)模不同的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上對(duì)算法的性能和效果進(jìn)行對(duì)比驗(yàn)證，這些對(duì)比算法的參數(shù)設(shè)置如下：對(duì)于Copra，v被設(shè)置為1到10不等，取值間隔為1；對(duì)于CPM算法，k被設(shè)置為2到8不等，取值間隔為1；對(duì)于LFM算法，設(shè)置α的值為1.0；對(duì)于SLPA和L-SLPA，將迭代次數(shù)T設(shè)置為20，過濾參數(shù)r被設(shè)置為0.05。實(shí)驗(yàn)結(jié)果選取各參數(shù)下得到的最大值進(jìn)行對(duì)比。

本文實(shí)驗(yàn)將5種算法在規(guī)模不同的真實(shí)網(wǎng)絡(luò)上各運(yùn)行100次，對(duì)得到的運(yùn)行時(shí)間取均值，最終的結(jié)果如圖6所示?？梢园l(fā)現(xiàn)，當(dāng)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)較少時(shí)，除SLPA外，其余4種算法的時(shí)間開銷相當(dāng)。但是隨著網(wǎng)絡(luò)規(guī)模的不斷增大，4種對(duì)比算法的運(yùn)行時(shí)間明顯增加。L-SLPA的運(yùn)行時(shí)間仍然呈現(xiàn)線性增長(zhǎng)，并且遠(yuǎn)低于其他4種算法的運(yùn)行時(shí)間，效率更高，可擴(kuò)展性更好。

(a)

同樣地，采用上述參數(shù)設(shè)置，將5種算法分別在每個(gè)數(shù)據(jù)集上運(yùn)行10次，對(duì)得到的重疊模塊度QE取平均值，最終的結(jié)果如圖7所示?？傮w來看，當(dāng)網(wǎng)絡(luò)規(guī)模較小時(shí)，Copra的劃分結(jié)果的重疊模塊度最高，但是隨著節(jié)點(diǎn)數(shù)量增加，劃分結(jié)果明顯有所下降。而L-SLPA在各網(wǎng)絡(luò)上的劃分結(jié)果都具有較高的重疊模塊度QE，SLPA次之。結(jié)果表明，L-SLPA能夠在不同規(guī)模的網(wǎng)絡(luò)中發(fā)現(xiàn)較高質(zhì)量的重疊社區(qū)。

圖7 真實(shí)網(wǎng)絡(luò)劃分結(jié)果的重疊模塊度QE

為了測(cè)試L-SLPA是否能夠有效地降低標(biāo)簽傳遞策略所引起的隨機(jī)性問題，使用SLPA和L-SLPA分別在N=1 000和N=5 000的LFR基準(zhǔn)測(cè)試網(wǎng)絡(luò)上進(jìn)行了100次社區(qū)發(fā)現(xiàn)，每次劃分得到的社區(qū)數(shù)量如圖8所示?？梢园l(fā)現(xiàn)，SLPA得到的社區(qū)數(shù)量隨機(jī)性較大，結(jié)果并不穩(wěn)定。在N=1 000的LFR基準(zhǔn)測(cè)試網(wǎng)絡(luò)上，得到的社區(qū)數(shù)量在65～95個(gè)之間波動(dòng)；在N=5 000的LFR基準(zhǔn)測(cè)試網(wǎng)絡(luò)上，得到的社區(qū)數(shù)量在352～396個(gè)之間波動(dòng)。相同情況下，L-SLPA得到的社區(qū)數(shù)量波動(dòng)較小，結(jié)果比較穩(wěn)定。

圖8 LFR基準(zhǔn)測(cè)試網(wǎng)絡(luò)上劃分的社區(qū)數(shù)量

最后，生成了4組不同參數(shù)的LFR基準(zhǔn)測(cè)試數(shù)據(jù)集，結(jié)合式(5)，對(duì)SLPA和L-SLPA進(jìn)行了性能對(duì)比。將兩種算法分別在每個(gè)數(shù)據(jù)集上運(yùn)行10次，對(duì)得到的NMI值取平均值，最終結(jié)果如圖9所示。

圖9 LFR基準(zhǔn)測(cè)試網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

總體上，隨著每個(gè)節(jié)點(diǎn)歸屬的社區(qū)數(shù)om和混合參數(shù)μ的增加，兩種算法的社區(qū)發(fā)現(xiàn)結(jié)果均有所下降。在N=1 000的LFR基準(zhǔn)測(cè)試網(wǎng)絡(luò)中，L-SLPA的劃分結(jié)果和SLPA的劃分結(jié)果大致相等。然而隨著網(wǎng)絡(luò)規(guī)模的變大，當(dāng)N=5 000時(shí)，相較于SLPA，L-SLPA的性能下降比較多。這是由于L-SLPA的第一階段執(zhí)行了一次基于模塊度Q優(yōu)化的非重疊社區(qū)劃分，而隨著網(wǎng)絡(luò)規(guī)模不斷增大，基于模塊度Q優(yōu)化的方法的解析度問題便會(huì)逐漸凸顯出來，算法得到的社區(qū)數(shù)量有可能遠(yuǎn)小于真實(shí)的社區(qū)數(shù)量，這會(huì)導(dǎo)致NMI值的下降。雖然此方法發(fā)現(xiàn)的社區(qū)數(shù)量小于實(shí)際情況，但是劃分得到的社區(qū)結(jié)構(gòu)穩(wěn)定，與實(shí)際情況吻合度較高，所以并不會(huì)影響社區(qū)發(fā)現(xiàn)結(jié)果的模塊度。

4 結(jié) 語

由于標(biāo)簽傳遞策略的隨機(jī)性，SLPA的社區(qū)發(fā)現(xiàn)結(jié)果并不夠穩(wěn)定。同時(shí)，SLPA初始的標(biāo)簽分配需要消耗大量的資源。為了解決SLPA的這些缺點(diǎn)，本文基于SLPA提出一種更加高效的重疊社區(qū)發(fā)現(xiàn)算法，在算法的初始階段，基于模塊度Q優(yōu)化對(duì)網(wǎng)絡(luò)進(jìn)行一次非重疊社區(qū)劃分，對(duì)同社區(qū)的節(jié)點(diǎn)分配一個(gè)相同的標(biāo)簽后再對(duì)邊界節(jié)點(diǎn)執(zhí)行Speaker-Listener標(biāo)簽傳播的迭代步驟。實(shí)驗(yàn)結(jié)果表明，相較于其他重疊社區(qū)發(fā)現(xiàn)算法，L-SLPA運(yùn)行速度快，具有更好的可擴(kuò)展性，在降低了標(biāo)簽傳播算法結(jié)果的隨機(jī)性的同時(shí)保證了結(jié)果的準(zhǔn)確性。