賈慧娟，劉 園，史愛(ài)靜，張霄宏

1(河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 焦作 454003)

2(吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春 130012)

1 引 言

復(fù)雜網(wǎng)絡(luò)中普遍存在著群集特征.網(wǎng)絡(luò)中的節(jié)點(diǎn)可以形成不同的群組，同一群組內(nèi)的節(jié)點(diǎn)之間關(guān)系相對(duì)密切，而不同群組的節(jié)點(diǎn)間關(guān)系相對(duì)較弱，稱之為“社區(qū)結(jié)構(gòu)特性”[1].研究結(jié)果表明，網(wǎng)絡(luò)中的某些節(jié)點(diǎn)并不是只屬于一個(gè)社區(qū)，不同的社區(qū)在這些節(jié)點(diǎn)處發(fā)生了重疊[2]，即網(wǎng)絡(luò)中存在重疊的社區(qū).發(fā)現(xiàn)網(wǎng)絡(luò)中的重疊社區(qū)不僅有助于理解網(wǎng)絡(luò)的功能，還可以幫助人們從用戶的行為、群體結(jié)構(gòu)和關(guān)系模式中發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中隱藏的規(guī)律.

有很多方法都可以用來(lái)發(fā)現(xiàn)重疊社區(qū)[3-6]，標(biāo)簽傳播算法(Label Propagation Algorithm，LPA)便是其中之一.LPA算法[7]最初用于發(fā)現(xiàn)非重疊社區(qū)，因具有接近線性的時(shí)間復(fù)雜度而被廣泛關(guān)注.Sun等[8]利用優(yōu)勢(shì)標(biāo)簽傳播來(lái)檢測(cè)重疊社區(qū)，利用膨脹算子控制社區(qū)之間的重疊率.為了降低標(biāo)簽傳播算法在標(biāo)簽更新過(guò)程中采用的隨機(jī)策略導(dǎo)致的社區(qū)劃分結(jié)果不穩(wěn)定問(wèn)題[9]，劉世超等[10]引入節(jié)點(diǎn)影響力，并按節(jié)點(diǎn)影響力由大到小的順序更新各節(jié)點(diǎn)標(biāo)簽.梁世嬌等[11]在通過(guò)粗聚類得到的社區(qū)劃分基礎(chǔ)上，利用節(jié)點(diǎn)親密度進(jìn)行重疊社區(qū)發(fā)現(xiàn).這些方法都采用了異步的方式更新各節(jié)點(diǎn)的標(biāo)簽.與上述方法不同，由Gregory等[12]提出的COPRA算法(Community Overlap Propagation Algorithm，COPRA)采用同步的方式更新標(biāo)簽，即在每輪迭代中僅根據(jù)上一輪迭代的標(biāo)簽傳播結(jié)果來(lái)進(jìn)行本輪的標(biāo)簽更新，本輪中已經(jīng)更新過(guò)標(biāo)簽的節(jié)點(diǎn)不對(duì)其它節(jié)點(diǎn)的標(biāo)簽更新產(chǎn)生影響.COPRA引入了標(biāo)簽歸屬值以及參數(shù)v控制每個(gè)節(jié)點(diǎn)擁有的標(biāo)簽，在可選標(biāo)簽的歸屬值都小于1/v的情況下，COPRA仍然采用隨機(jī)策略選擇標(biāo)簽.馬健等[13]在COPRA的基礎(chǔ)上提出了COPRAPC，該算法利用聚類系數(shù)限制每個(gè)節(jié)點(diǎn)擁有的標(biāo)簽數(shù)量.張昌理等[14]的工作也在COPRA的基礎(chǔ)上進(jìn)行，他們采用了異步的標(biāo)簽更新策略，但是按照各節(jié)點(diǎn)信息熵的大小順序?qū)Ω鞴?jié)點(diǎn)進(jìn)行標(biāo)簽更新.雖然COPRA采用了同步的標(biāo)簽更新策略，不同的學(xué)者也從不同的角度對(duì)COPRA進(jìn)行了改進(jìn)，但是這些算法中仍然存在隨機(jī)策略，由隨機(jī)策略引起的重疊社區(qū)劃分結(jié)果不穩(wěn)定問(wèn)題仍然是一個(gè)開(kāi)放問(wèn)題.

針對(duì)COPRA因在標(biāo)簽更新過(guò)程采用隨機(jī)策略而導(dǎo)致的重疊社區(qū)劃分結(jié)果不穩(wěn)定問(wèn)題，本文對(duì)COPRA進(jìn)行了改進(jìn)，提出了COPRA-S算法(Simple Community Overlap Propagation Algorithm).COPRA-S算法采用同步的方式傳播標(biāo)簽，且只在以邊緣節(jié)點(diǎn)為中心的橋梁節(jié)點(diǎn)群內(nèi)進(jìn)行標(biāo)簽傳播，以此提升發(fā)現(xiàn)重疊社區(qū)的速度.COPRA-S算法還引入了節(jié)點(diǎn)連接社區(qū)強(qiáng)度，利用其降低標(biāo)簽更新過(guò)程中的隨機(jī)性.此外，引入節(jié)點(diǎn)連接社區(qū)強(qiáng)度，還可以防止標(biāo)簽的過(guò)度傳播.

2 COPRA問(wèn)題分析

COPRA利用標(biāo)簽傳播發(fā)現(xiàn)重疊社區(qū).該算法采用同步的方式更新標(biāo)簽，引入標(biāo)簽歸屬值以及參數(shù)v控制每個(gè)節(jié)點(diǎn)擁有的標(biāo)簽.凡是滿足條件歸屬值大于1/v的標(biāo)簽都會(huì)指派給節(jié)點(diǎn)；如果不存在滿足此條件的標(biāo)簽，則隨機(jī)選擇一個(gè)標(biāo)簽更新節(jié)點(diǎn)，而這種隨機(jī)選擇標(biāo)簽的策略會(huì)導(dǎo)致社區(qū)劃分結(jié)果不穩(wěn)定.

圖1所示的例子展示了COPRA存在的社區(qū)劃分結(jié)果不穩(wěn)定問(wèn)題.圖中節(jié)點(diǎn)旁的二元組表示標(biāo)簽與其對(duì)節(jié)點(diǎn)的歸屬值.該圖給出了相應(yīng)輪次的迭代后各節(jié)點(diǎn)擁有標(biāo)簽的情況.假設(shè)在第2輪迭代中，節(jié)點(diǎn)的隨機(jī)遍歷次序?yàn)関5，v6，v7，v1，v3，v2，v4.由于在v2的鄰居節(jié)點(diǎn)中出現(xiàn)的標(biāo)簽的歸屬值都小于1/v，即1/2，故應(yīng)從這些標(biāo)簽中隨機(jī)選擇一個(gè)更新v2，假設(shè)選擇標(biāo)簽γ.相似的，為v4隨機(jī)選擇標(biāo)簽δ.在這種情況下會(huì)得到正確的社區(qū)劃分結(jié)果.但是，如果隨機(jī)地為v2和v4選擇了標(biāo)簽ε，則最終所有的節(jié)點(diǎn)都被劃分到一個(gè)社區(qū).這充分說(shuō)明了COPRA算法采用的隨機(jī)策略帶來(lái)的社區(qū)劃分結(jié)果不穩(wěn)定問(wèn)題.

圖1 COPRA在v=2時(shí)不同的標(biāo)簽更新結(jié)果Fig.1 Different label update results of COPRA at v=2

3 COPRA-S算法

為了降低隨機(jī)性對(duì)社區(qū)劃分結(jié)果穩(wěn)定性的影響，提升算法的性能，本文在COPRA的基礎(chǔ)上提出了COPRA-S算法.本節(jié)闡述該算法的思想及實(shí)現(xiàn)細(xì)節(jié).

3.1 算法思想

根據(jù)文獻(xiàn)[13]的結(jié)果，社區(qū)內(nèi)部的節(jié)點(diǎn)一般是非重疊節(jié)點(diǎn)，而社區(qū)邊緣的節(jié)點(diǎn)由于連接多個(gè)不同的社區(qū)一般會(huì)成為重疊節(jié)點(diǎn).依據(jù)這一結(jié)果，COPRA-S算法要求即將分析的社交網(wǎng)絡(luò)要經(jīng)過(guò)預(yù)處理劃分出非重疊社區(qū)，然后在以邊緣節(jié)點(diǎn)為中心的小范圍節(jié)點(diǎn)內(nèi)進(jìn)行標(biāo)簽傳播，并最終發(fā)現(xiàn)重疊節(jié)點(diǎn).通過(guò)將標(biāo)簽傳播限制在以邊緣節(jié)點(diǎn)為中心的小范圍節(jié)點(diǎn)內(nèi)以來(lái)提升利用標(biāo)簽傳播算法發(fā)現(xiàn)重疊節(jié)點(diǎn)的速度.在圖2所示的網(wǎng)絡(luò)中，COPRA的標(biāo)簽傳播范圍包括圖中所有節(jié)點(diǎn)，而COPRA-S算法只在虛線圈定的節(jié)點(diǎn)范圍內(nèi)傳播標(biāo)簽.

圖2 COPRA和COPRA-S兩種算法的標(biāo)簽傳播范圍比較Fig.2 Label propagation comparison of COPRA and COPRA-S

在COPRA中，當(dāng)某個(gè)節(jié)點(diǎn)所有鄰居節(jié)點(diǎn)標(biāo)簽的歸屬值都小于預(yù)設(shè)閾值時(shí)，隨機(jī)從這些標(biāo)簽中選擇一個(gè)更新當(dāng)前節(jié)點(diǎn)，從而導(dǎo)致社區(qū)劃分結(jié)果不穩(wěn)定.為了降低由隨機(jī)選取標(biāo)簽引起的社區(qū)劃分結(jié)果不穩(wěn)定性，在COPRA-S算法中引入一個(gè)新的標(biāo)簽選擇指標(biāo)—節(jié)點(diǎn)連接社區(qū)強(qiáng)度.在所有鄰居節(jié)點(diǎn)標(biāo)簽的歸屬值相等且都小于預(yù)設(shè)閾值情況下，優(yōu)先采用最大的節(jié)點(diǎn)連接社區(qū)強(qiáng)度所對(duì)應(yīng)的標(biāo)簽.只有在多個(gè)節(jié)點(diǎn)連接社區(qū)強(qiáng)度對(duì)應(yīng)的標(biāo)簽都滿足要求的情況下，才隨機(jī)選擇標(biāo)簽更新節(jié)點(diǎn).

此外，在標(biāo)簽傳播過(guò)程中引入節(jié)點(diǎn)連接社區(qū)強(qiáng)度還可以防止標(biāo)簽的過(guò)度傳播.圖3展示了標(biāo)簽的過(guò)度傳播.在該圖中，社區(qū)2的標(biāo)簽β經(jīng)由橋梁節(jié)點(diǎn)b3傳播到橋梁節(jié)點(diǎn)b1.引入節(jié)點(diǎn)連接社區(qū)強(qiáng)度后，通過(guò)設(shè)計(jì)恰當(dāng)?shù)墓?jié)點(diǎn)連接社區(qū)強(qiáng)度計(jì)算模型和標(biāo)簽傳播策略，可以阻止社區(qū)2的標(biāo)簽β經(jīng)由b3繼續(xù)傳到其它社區(qū)中的節(jié)點(diǎn).

圖3 標(biāo)簽的過(guò)度傳播Fig.3 Excessive spread of labels

3.2 標(biāo)簽傳播范圍計(jì)算

COPRA-S算法的創(chuàng)新點(diǎn)之一是通過(guò)在以邊緣節(jié)點(diǎn)為中心的小范圍節(jié)點(diǎn)內(nèi)進(jìn)行標(biāo)簽傳播，來(lái)提升利用標(biāo)簽傳播算法進(jìn)行重疊節(jié)點(diǎn)發(fā)現(xiàn)的速度.為便于劃定以邊緣節(jié)點(diǎn)為中心的標(biāo)簽傳播范圍，引入橋梁節(jié)點(diǎn)、橋梁節(jié)點(diǎn)群等概念.

定義1.橋梁節(jié)點(diǎn)

?vi∈V，若vi的標(biāo)簽與某個(gè)鄰居節(jié)點(diǎn)的標(biāo)簽不相同，則vi為橋梁節(jié)點(diǎn).孤立節(jié)點(diǎn)不是橋梁節(jié)點(diǎn).

定義2.橋梁節(jié)點(diǎn)群

?vi∈V，若vi是橋梁節(jié)點(diǎn)，與vi有邊相連的節(jié)點(diǎn)共同構(gòu)成以vi為中心的橋梁節(jié)點(diǎn)群，記為Bvi.

橋梁節(jié)點(diǎn)連接兩個(gè)或者多個(gè)社區(qū)，它們最有可能成為擁有多個(gè)標(biāo)簽的重疊節(jié)點(diǎn).但是，重疊節(jié)點(diǎn)的標(biāo)簽只能來(lái)自于以其為中心的橋梁節(jié)點(diǎn)群中的節(jié)點(diǎn).算法1描述了橋梁節(jié)點(diǎn)的篩選過(guò)程.以某橋梁節(jié)點(diǎn)為中心的橋梁節(jié)點(diǎn)群則由該橋梁節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)共同構(gòu)成.

算法1.橋梁節(jié)點(diǎn)篩選

輸入：G=(V，E)；

輸出：Blist；

1.for eachv∈Vdo

2. ifv的鄰居節(jié)點(diǎn)擁有的標(biāo)簽不完全相同，則

3. 記v為橋梁節(jié)點(diǎn)，并加入橋梁節(jié)點(diǎn)列表-Blist；

4. end if

5.end for

6.output Blist；

3.3 標(biāo)簽傳播

COPRA-S算法采用COPRA算法提出的同步更新節(jié)點(diǎn)標(biāo)簽的策略，即本輪標(biāo)簽更新僅受上一輪迭代后的標(biāo)簽更新結(jié)果影響，本輪中已經(jīng)更新的標(biāo)簽只對(duì)下一輪的標(biāo)簽更新產(chǎn)生影響.

COPRA-S算法仍然采用歸屬值作為節(jié)點(diǎn)標(biāo)簽更新的重要依據(jù).當(dāng)橋梁節(jié)點(diǎn)群中出現(xiàn)的標(biāo)簽相對(duì)于橋梁節(jié)點(diǎn)的歸屬值大于預(yù)定義的閾值θ時(shí)，將這樣的標(biāo)簽指派給橋梁節(jié)點(diǎn)，并重新對(duì)標(biāo)簽的歸屬值進(jìn)行歸一化處理，使得橋梁節(jié)點(diǎn)擁有的各標(biāo)簽歸屬值之和為1.

(1)

(2)

(3)

(4)

為了降低標(biāo)簽傳播過(guò)程中的隨機(jī)性以及防止標(biāo)簽的過(guò)度傳播，定義了節(jié)點(diǎn)連接社區(qū)強(qiáng)度.節(jié)點(diǎn)連接社區(qū)強(qiáng)度反應(yīng)節(jié)點(diǎn)與社區(qū)關(guān)系的緊密程度，節(jié)點(diǎn)對(duì)某個(gè)社區(qū)的節(jié)點(diǎn)連接強(qiáng)度越大，節(jié)點(diǎn)和這個(gè)社區(qū)關(guān)系越緊密，節(jié)點(diǎn)接受這個(gè)社區(qū)標(biāo)簽的傾向性就越強(qiáng)，反之亦然.

定義3.節(jié)點(diǎn)連接社區(qū)強(qiáng)度

節(jié)點(diǎn)連接社區(qū)強(qiáng)度表示節(jié)點(diǎn)連接或歸屬于某個(gè)社區(qū)的程度，記為DCon.

?vi∈V，C為與vi相連的一個(gè)社區(qū)，vi對(duì)社區(qū)C的節(jié)點(diǎn)連接社區(qū)強(qiáng)度記為DCon(vi，C)，可根據(jù)式(5)計(jì)算.在該式中，Nvi表示vi的鄰居節(jié)點(diǎn)集合，VC表示社區(qū)C中的節(jié)點(diǎn)集合.

(5)

COPRA-S算法的詳細(xì)內(nèi)容如算法2所示.該算法包含篩選橋梁節(jié)點(diǎn)以及標(biāo)簽傳播兩個(gè)階段.假設(shè)網(wǎng)絡(luò)有n個(gè)節(jié)點(diǎn)，e條邊，每個(gè)節(jié)點(diǎn)的平均度數(shù)為d，篩選橋梁節(jié)點(diǎn)的時(shí)間復(fù)雜度約為O(nd)；影響力計(jì)算的時(shí)間復(fù)雜度是O(et1)，t1為影響力計(jì)算過(guò)程中的迭代次數(shù)；標(biāo)簽傳播的時(shí)間復(fù)雜度約為O(bdt2)，b為橋梁節(jié)點(diǎn)的總數(shù)，t2為迭代次數(shù).因此COPRA-S算法總的時(shí)間復(fù)雜度約是O(et1+nd+bdt2).

算法2.COPRA-S算法

輸入：已劃分好非重疊社區(qū)的網(wǎng)絡(luò)G；

輸出：重疊社區(qū)劃分；

1.t←1；

3.Blist←橋梁節(jié)點(diǎn)篩選；

4.for eachvi∈Blistdo

5. 計(jì)算Bvi中每個(gè)標(biāo)簽相對(duì)vi的歸屬值；

6. 計(jì)算vi對(duì)于這些標(biāo)簽所屬社區(qū)的節(jié)點(diǎn)連接社區(qū)強(qiáng)度；

7. if 存在歸屬值大于θ的標(biāo)簽

8. 將節(jié)點(diǎn)連接社區(qū)強(qiáng)度大于0的標(biāo)簽指派給vi；

9. else

10. if 所有標(biāo)簽的歸屬值都相等

為營(yíng)造良好的政策環(huán)境，雙創(chuàng)園先后制定出臺(tái)促進(jìn)投資和產(chǎn)業(yè)發(fā)展、培育綠色企業(yè)的產(chǎn)業(yè)政策，從培育企業(yè)原創(chuàng)技術(shù)推廣、專利技術(shù)產(chǎn)業(yè)化、“兩化融合”等方面予以重點(diǎn)支持，不斷提升企業(yè)自主研發(fā)水平和原創(chuàng)能力；啟動(dòng)“金豆子”培育工程，力推企業(yè)掛牌上市。

11. if節(jié)點(diǎn)連接社區(qū)強(qiáng)度不等

12. 將最大的節(jié)點(diǎn)連接社區(qū)強(qiáng)度對(duì)應(yīng)的標(biāo)簽指給vi；

13. else

14. 隨機(jī)選擇一個(gè)標(biāo)簽指派給vi；

15. end if

16. else

17. 將歸屬值最大的標(biāo)簽指派給vi；

18. end if

19.end if

20.end for

21.t←t+1；

22.if傳播停止條件未滿足

23. 回到步驟4；

24.end if

25.返回標(biāo)簽傳播結(jié)果.

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

本文通過(guò)在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和人工合成網(wǎng)絡(luò)數(shù)據(jù)集上將COPRA-S算法與COPRA、CPM[2]、Demon[16]及CONGA[17]算法進(jìn)行對(duì)比來(lái)驗(yàn)證COPRA-S算法的正確性和有效性.展示的所有實(shí)驗(yàn)結(jié)果均為相關(guān)算法獨(dú)立運(yùn)行50次的平均結(jié)果.

4.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

本文所有的實(shí)驗(yàn)均在單臺(tái)主機(jī)上進(jìn)行.該主機(jī)采用了 Intel core i5-7200U 處理器，配置了8GB的內(nèi)存，并安裝了Windows10操作系統(tǒng).

在實(shí)驗(yàn)中既用到了真實(shí)網(wǎng)絡(luò)數(shù)據(jù)也用到了人工合成網(wǎng)絡(luò)數(shù)據(jù).表1展示了真實(shí)數(shù)據(jù)集的基本信息，其中，前6個(gè)數(shù)據(jù)集來(lái)自Newman數(shù)據(jù)集(1)http：//www-personal.umich.edu/～mejn/netdata/，后3個(gè)數(shù)據(jù)集來(lái)自SNAP數(shù)據(jù)集(2)http：//snap.stanford.edu/data/.

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

人工合成網(wǎng)絡(luò)數(shù)據(jù)集由LFR基準(zhǔn)發(fā)生器[18]生成，參數(shù)配置如下：節(jié)點(diǎn)總數(shù)n=5000，平均度數(shù)k=50，最大度數(shù)maxk=100，社區(qū)最小節(jié)點(diǎn)數(shù)minc=50，最大節(jié)點(diǎn)數(shù)maxc=100，重疊節(jié)點(diǎn)數(shù)on=500，每個(gè)重疊節(jié)點(diǎn)所屬的社區(qū)個(gè)數(shù)om=5，mu是混合參數(shù)，取值范圍從0.1-0.6，以0.1為間隔遞增.隨著mu的增長(zhǎng)，網(wǎng)絡(luò)結(jié)構(gòu)變得越來(lái)越模糊，社區(qū)檢測(cè)的難度也越來(lái)越大.

4.2 實(shí)驗(yàn)結(jié)果及分析

在實(shí)驗(yàn)中采用了4個(gè)評(píng)價(jià)指標(biāo)，分別是重疊模塊度-EQ、綜合評(píng)價(jià)指標(biāo)-F[10]、標(biāo)準(zhǔn)化互信息-NMI以及執(zhí)行時(shí)間，其中，執(zhí)行時(shí)間適用于所有的數(shù)據(jù)集.由于真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集中沒(méi)有重疊社區(qū)的真實(shí)社區(qū)劃分，僅采用EQ和F平均值兩項(xiàng)指標(biāo)來(lái)評(píng)價(jià)各算法在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的表現(xiàn).在人工合成網(wǎng)絡(luò)數(shù)據(jù)集上采用EQ和NMI平均值作為評(píng)價(jià)指標(biāo).此外，COPRA-S算法需要對(duì)輸入數(shù)據(jù)進(jìn)行預(yù)處理，即劃分非重疊社區(qū)，在實(shí)驗(yàn)中采用文獻(xiàn)[19]中的方法進(jìn)行非重疊社區(qū)劃分.

圖4展示了各個(gè)算法在真實(shí)數(shù)據(jù)集上EQ平均值的比較結(jié)果.由圖可知，COPRA-S算法在每個(gè)數(shù)據(jù)集上的表現(xiàn)都比COPRA算法要好.其中，COPRA-S算法在Karate、Foot-ball、Netscience、Internet及Enron-Email 4個(gè)數(shù)據(jù)集上的EQ平均值相比于COPRA算法均提高了20%以上.COPRA-S算法在真實(shí)數(shù)據(jù)集上的表現(xiàn)也明顯優(yōu)于其它3個(gè)算法.

圖4 真實(shí)數(shù)據(jù)集上EQ平均值對(duì)比Fig.4 Comparisson of average EQ on real data sets

圖5展示了各個(gè)算法在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上綜合評(píng)價(jià)指標(biāo)F平均值的比較結(jié)果.由圖可知，COPRA-S算法在每個(gè)數(shù)據(jù)集上的表現(xiàn)都比COPRA算法要好.其中，COPRA-S算法在Karate、Dolphins、Football、Netscience及Internet 5個(gè)數(shù)據(jù)集上的F平均值相比于COPRA算法均提高了10%及以上.COPRA-S算法在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的F平均值也明顯優(yōu)于其它3個(gè)算法.

圖5 真實(shí)數(shù)據(jù)集上F平均值對(duì)比Fig.5 Comparison of average F on real data sets

表2展示了各算法在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的平均運(yùn)行時(shí)間，時(shí)間單位為s.在該表中，COPRA-S算法的執(zhí)行時(shí)間只包括標(biāo)簽傳播時(shí)間，不包括數(shù)據(jù)預(yù)處理時(shí)間，即非重疊社區(qū)劃分時(shí)間.由表可知，COPRA-S算法在各真實(shí)數(shù)據(jù)集上的執(zhí)行時(shí)間明顯少于其它算法在這些數(shù)據(jù)集上的執(zhí)行時(shí)間.

表2 算法在真實(shí)數(shù)據(jù)集上的平均運(yùn)行時(shí)間對(duì)比Table 2 Average running time comparison on real data sets

圖6展示了各算法在人工數(shù)據(jù)集上的EQ平均值.從圖可知，COPRA-S算法的EQ平均值明顯高于COPRA、Demon和GONGA算法.雖然COPRA-S算法在mu為0.2、0.5及0.6時(shí)的EQ平均值略低于CPM算法，但是當(dāng)采用NMI和執(zhí)行時(shí)間這兩項(xiàng)指標(biāo)進(jìn)行評(píng)價(jià)時(shí)，COPRA-S算法要優(yōu)于CPM算法.在其他情況下COPRA-S算法所取得的結(jié)果都是最好的.

圖6 人工數(shù)據(jù)集上EQ平均值對(duì)比Fig.6 Average EQ comparison on artificial datasets

圖7展示了各算法在人工數(shù)據(jù)集上的平均NMI值.由圖可知COPRA-S算法的平均NMI值除了在mu=0.3時(shí)略低于COPRA外，在其它情況下都大于或等于COPRA.此外，COPRA-S算法的平均NMI值明顯高于其他3個(gè)算法.綜上，COPRA-S算法檢測(cè)重疊社區(qū)的準(zhǔn)確性要好于其它算法.

圖7 人工數(shù)據(jù)集上NMI平均值對(duì)比Fig.7 Average NMI comparison on artificial datasets

表3展示了各算法在人工生成數(shù)據(jù)集上的平均運(yùn)行時(shí)間，時(shí)間單位為s.在該表中，COPRA-S算法的執(zhí)行時(shí)間只包括標(biāo)簽傳播時(shí)間，不包括數(shù)據(jù)預(yù)處理時(shí)間，即非重疊社區(qū)劃分時(shí)間.由表可知，COPRA-S算法在各人工生成數(shù)據(jù)集上的執(zhí)行時(shí)間明顯少于其它算法在這些數(shù)據(jù)集上的執(zhí)行時(shí)間.

表3 算法在人工數(shù)據(jù)集上的平均運(yùn)行時(shí)間對(duì)比Table 3 Average running time comparison on artificial dataset

5 結(jié)束語(yǔ)

本文對(duì)COPRA進(jìn)行了改進(jìn)并提出了COPRA-S算法.COPRA-S算法采用同步的方式傳播標(biāo)簽，且只在以邊緣節(jié)點(diǎn)為中心的橋梁節(jié)點(diǎn)群內(nèi)進(jìn)行標(biāo)簽傳播，以此提升發(fā)現(xiàn)重疊社區(qū)的速度.COPRA-S算法還引入了節(jié)點(diǎn)連接社區(qū)強(qiáng)度，利用其降低標(biāo)簽更新過(guò)程中的隨機(jī)性，并防止標(biāo)簽的過(guò)度傳播.在9個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和人工合成網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了本文方法的正確性和有效性.下一步，將在本文算法的基礎(chǔ)上開(kāi)展動(dòng)態(tài)重疊社區(qū)發(fā)現(xiàn)方面的研究.