鄧小龍,溫 穎

(1.北京郵電大學(xué)可信分布式計(jì)算與服務(wù)教育部重點(diǎn)實(shí)驗(yàn)室,北京 100876; 2.北京郵電大學(xué)國際學(xué)院,北京 100876)

?

基于傳染病模型的LPA特征閥值社團(tuán)劃分方法

鄧小龍1,溫 穎2

(1.北京郵電大學(xué)可信分布式計(jì)算與服務(wù)教育部重點(diǎn)實(shí)驗(yàn)室,北京 100876; 2.北京郵電大學(xué)國際學(xué)院,北京 100876)

社團(tuán)結(jié)構(gòu)劃分對于分析復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特性非常重要.在非均勻社交網(wǎng)絡(luò)的信息傳播中，社團(tuán)結(jié)構(gòu)劃分更是一個(gè)廣泛關(guān)注的研究熱點(diǎn)，相關(guān)研究往往側(cè)重于研究緊密連接的社團(tuán)結(jié)構(gòu)對于信息傳播所產(chǎn)生的關(guān)鍵影響.傳統(tǒng)社團(tuán)劃分方法大多基于點(diǎn)和邊的相關(guān)特性進(jìn)行構(gòu)建，如標(biāo)簽傳播算法LPA(Label Propagation Algorithm)通過半監(jiān)督機(jī)器學(xué)習(xí)方法，基于網(wǎng)絡(luò)節(jié)點(diǎn)標(biāo)簽的智能交換和社團(tuán)融合過程進(jìn)行社團(tuán)劃分，但運(yùn)行效率較低.為提高LPA類算法的運(yùn)行速度，使其快速收斂，并提高社團(tuán)劃分精度，特別是重疊社團(tuán)劃分精度，針對LPA算法劃分中的低運(yùn)行效率和低融合收斂速度，本文從標(biāo)簽傳播的網(wǎng)絡(luò)連接矩陣本質(zhì)出發(fā)，將該矩陣的最大非零特征值與網(wǎng)絡(luò)標(biāo)簽信息傳播的閥值相結(jié)合，提出了新的基于傳染病傳播模型的社團(tuán)劃分方法(簡稱ESLPA算法，Epidemic Spreading LPA).通過經(jīng)典LFR Benchmark模擬測試網(wǎng)絡(luò)、隨機(jī)網(wǎng)絡(luò)以及真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)上的算法驗(yàn)證，結(jié)果表明該算法時(shí)間復(fù)雜度大幅優(yōu)于經(jīng)典LPA算法，在重疊社團(tuán)劃分上精確度優(yōu)于基于LPA模型的經(jīng)典COPRA算法，特別是在重疊社團(tuán)較明顯時(shí)，劃分精度接近精度較高GA、N-cut和A-cut算法，明顯優(yōu)于GN、FastGN和CPM等經(jīng)典算法.

重疊社團(tuán)劃分；流行病模型；信息擴(kuò)散；最大非零特征值

1 引言

互聯(lián)網(wǎng)的快速發(fā)展，促進(jìn)了人們使用社交網(wǎng)站、微博、論壇、百度百科、手機(jī)呼叫網(wǎng)絡(luò)等在線社會網(wǎng)絡(luò)進(jìn)行溝通和交流，形成了海量、復(fù)雜的社會網(wǎng)絡(luò)結(jié)構(gòu).而社會網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的發(fā)現(xiàn)對承載其上的信息傳播模式探索和構(gòu)建非常重要，例如社團(tuán)發(fā)現(xiàn)對在線社交網(wǎng)絡(luò)中研究輿情預(yù)警和口碑傳播就具有重要意義.同時(shí)，隨著社會網(wǎng)絡(luò)規(guī)模的增大，節(jié)點(diǎn)關(guān)系愈發(fā)復(fù)雜.在真實(shí)社會網(wǎng)絡(luò)中，企業(yè)、組織、家庭、朋友、工作伙伴等關(guān)系常交織在一個(gè)網(wǎng)絡(luò)中，混淆了重疊社團(tuán)結(jié)構(gòu)的邊界，使重疊社團(tuán)發(fā)現(xiàn)變得愈發(fā)困難，給重疊社團(tuán)發(fā)現(xiàn)提出了新的挑戰(zhàn)，因此，研究在線社會網(wǎng)絡(luò)的重疊社團(tuán)發(fā)現(xiàn)方法具有重要的研究意義.

為提高LPA算法的運(yùn)行效率和收斂速度，本文提出了基于傳播病傳播模型的LPA特征閥值社團(tuán)發(fā)現(xiàn)算法，通過引用病毒傳播模型準(zhǔn)確定義社團(tuán)重疊區(qū)域，結(jié)合病毒傳播模型和網(wǎng)絡(luò)連接矩陣的最大非零特征值定義了病毒的有限感染率傳播閥值.不同于以往用固定病毒傳播閥值感染整個(gè)網(wǎng)絡(luò)，我們將感染網(wǎng)絡(luò)中特定區(qū)域的病毒傳播閥值設(shè)置為一個(gè)精確的程度域值使其只感染相同社團(tuán)中的其他個(gè)體.得益于病毒傳染模型里不同病毒的獨(dú)立傳播過程，該方法能更精確地挖掘現(xiàn)實(shí)情況下的重疊社團(tuán)，在實(shí)驗(yàn)數(shù)據(jù)上獲得了較高的重疊社團(tuán)劃分精度.此外，通過在模擬網(wǎng)絡(luò)和真實(shí)在線社會網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，充分驗(yàn)證了本文所提算法的精確性和新穎性.

2 相關(guān)研究

2.1 基于標(biāo)簽傳播的社團(tuán)劃分算法

社團(tuán)結(jié)構(gòu)(community structure)具有同社團(tuán)內(nèi)節(jié)點(diǎn)相互連接密集、異社團(tuán)間節(jié)點(diǎn)相互連接稀疏特點(diǎn)，網(wǎng)絡(luò)中真實(shí)存在的社團(tuán)結(jié)構(gòu)的存在使得選擇社會網(wǎng)絡(luò)中不同節(jié)點(diǎn)作為信息傳播源頭時(shí)，信息傳播的速度和效率存在差異，在社團(tuán)結(jié)構(gòu)內(nèi)部，信息的傳輸效率和速度往往優(yōu)于社團(tuán)結(jié)構(gòu)之間的傳播效率.

LPA算法[1]最初由Zhu等在2003年提出，執(zhí)行復(fù)雜度低且分類效果好，時(shí)間復(fù)雜度為o(n2)(n為網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)).基本思路是用已標(biāo)記節(jié)點(diǎn)的標(biāo)簽去預(yù)測未標(biāo)記節(jié)點(diǎn)的標(biāo)簽(邊表示兩個(gè)節(jié)點(diǎn)的相似度).節(jié)點(diǎn)標(biāo)簽按相似度傳遞給其他節(jié)點(diǎn)，節(jié)點(diǎn)間相似度越大，標(biāo)簽越易傳播.當(dāng)標(biāo)簽傳播迭代結(jié)束，相似節(jié)點(diǎn)的標(biāo)簽分布趨于相似并被劃分到同一個(gè)類別.LPA執(zhí)行歸納為節(jié)點(diǎn)初始標(biāo)簽分配、迭代和社團(tuán)融合完成三階段，最后階段需對結(jié)果進(jìn)行確認(rèn)和反復(fù)迭代.

2007年Raghavan等將LPA算法應(yīng)用到社團(tuán)結(jié)構(gòu)劃分，提出了與網(wǎng)絡(luò)規(guī)模成正比的近似線性增長RAK算法[2]，通過預(yù)先定義目標(biāo)函數(shù)簡化LPA的迭代復(fù)雜度，利用網(wǎng)絡(luò)結(jié)構(gòu)作為指導(dǎo)來探測社區(qū)結(jié)構(gòu).RAK在空手道俱樂部網(wǎng)和美國大學(xué)橄欖球網(wǎng)的實(shí)驗(yàn)結(jié)果表明，其社區(qū)檢測效果良好，但在LFR benchmark網(wǎng)絡(luò)上實(shí)驗(yàn)結(jié)果存在一定缺陷.此后，很多研究者改進(jìn)了RAK.2010年Gregory對RAK進(jìn)行了改進(jìn)，提出側(cè)重于挖掘重疊社團(tuán)的COPRA算法[3](Community Overlap PRopagation Algorithm)，COPRA可使單個(gè)節(jié)點(diǎn)保留若干個(gè)社區(qū)標(biāo)簽，傳播過程包括多社區(qū)信息.COPRA能有效檢測重疊社區(qū)，但會導(dǎo)致每次迭代時(shí)間增加，當(dāng)重疊社區(qū)太多時(shí)，會導(dǎo)致不正確的標(biāo)簽隨機(jī)選擇，只對規(guī)模較小的重疊社區(qū)發(fā)現(xiàn)較為有效.

在大規(guī)模網(wǎng)絡(luò)社團(tuán)劃分方面，2011年金弟等[4]針對傳統(tǒng)LPA算法時(shí)間復(fù)雜度和搜索能力的缺陷，提出基于局部探測優(yōu)化的近似線性快速LPA遺傳算法FNCA，發(fā)現(xiàn)LPA 經(jīng)五次迭代后，95%節(jié)點(diǎn)已正確聚集；后面的迭代只對社區(qū)內(nèi)節(jié)點(diǎn)更新，是不必要的，改進(jìn)了迭代結(jié)束條件.2011年Cordasco等[5]提出半同步LPA算法，通過網(wǎng)絡(luò)頂點(diǎn)并行著色，結(jié)合同步和異步模式提高了運(yùn)行效率，適用于大規(guī)模網(wǎng)絡(luò).

但是以上算法在異質(zhì)、多源重疊社團(tuán)的發(fā)現(xiàn)上迭代次數(shù)較高，算法運(yùn)行時(shí)間較長，因此需構(gòu)建效率更高算法提升運(yùn)行效率,并防止算法陷入局部優(yōu)化陷阱.

2.2 傳染病傳播模型

信息傳播領(lǐng)域的經(jīng)典傳播模型是將現(xiàn)實(shí)中的傳染病傳播進(jìn)行抽象和建模所得，早在1760年Daniel Bernoulli就用數(shù)學(xué)方法研究過天花傳播.20世紀(jì)初有學(xué)者開始對確定性傳染病模型進(jìn)行研究，1927年William研究倫敦黑死病時(shí)，提出了SIR模型[6]，后來考慮重復(fù)感染，于1932年提出了SIS模型[7].近年來，2012年張彥超和顧亦然[8]等根據(jù)真實(shí)在線社交網(wǎng)絡(luò)中謠言的傳播特點(diǎn)以及有疾病潛伏期的傳染病模型，研究了在線社交網(wǎng)絡(luò)中用戶狀態(tài)和信息傳播模型，對其進(jìn)行了模型逼真模擬，提出新的基于在線社交網(wǎng)絡(luò)的謠言傳播SEIR模型[9]，該模型比較符合真實(shí)在線社交網(wǎng)絡(luò)的傳播特性.

但是這些模型并未考慮信息傳播者被感染后又痊愈的概率，也未從整個(gè)網(wǎng)絡(luò)的傳染持續(xù)性來考慮，因此本文選擇了2003年Wang[10]的傳染病模型并在其上構(gòu)建了重疊社團(tuán)劃分算法.該模型系統(tǒng)研究了網(wǎng)絡(luò)譜半徑和傳染持久性的關(guān)系，采用比以往模型更精確、定義更優(yōu)的閥值，更適用于重疊和龐大網(wǎng)絡(luò)，應(yīng)用于檢測網(wǎng)絡(luò)而不需要考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，其具體定義將在3.3節(jié)中敘述.

3 基于傳染病模型的社團(tuán)劃分算法

本文在Leskove等[11，12]研究成果基礎(chǔ)上，結(jié)合信息傳播的相關(guān)定義和假設(shè)，以及病毒傳播的網(wǎng)絡(luò)譜半徑等重要參數(shù)模型，構(gòu)建了基于傳染病模型的重疊社團(tuán)劃分算法ESLPA.

3.1 傳染病傳播模型定義

2003年Wang[10]等提出傳染病模型，將人與人間的感染關(guān)系抽象為有權(quán)有向網(wǎng)絡(luò)圖：G=(N,E)(N是節(jié)點(diǎn)集合，E是邊集合)，假設(shè)網(wǎng)絡(luò)所有節(jié)點(diǎn)感染率(定義為β)是相同的，每個(gè)節(jié)點(diǎn)消除自身病毒的治愈率也相同(定義為δ).

表1 傳染病模型符號定義

在上述假設(shè)的用時(shí)間戳t定義的離散時(shí)間序列中，已被感染的節(jié)點(diǎn)i在隨后每個(gè)時(shí)間間隔內(nèi)，都嘗試去感染它的鄰居(感染一個(gè)鄰居節(jié)點(diǎn)成功的概率為β)，同樣，節(jié)點(diǎn)i在某時(shí)間間隔中自愈概率為δ.我們定義在時(shí)刻t時(shí)節(jié)點(diǎn)i被感染的概率為pi,t,同樣,在時(shí)刻t節(jié)點(diǎn)i未受鄰居節(jié)點(diǎn)感染,不被感染的概率為ζi,t,定義如下:

(1)

假設(shè)在某個(gè)時(shí)刻t,存在以下三種情況之一,則節(jié)點(diǎn)i是健康的,假如:

情況1 節(jié)點(diǎn)i在時(shí)刻t之前是健康的,并且沒有被它的鄰居節(jié)點(diǎn)所感染(由ζi,t定義)；

情況2 節(jié)點(diǎn)i在時(shí)刻t之前已經(jīng)被感染,在時(shí)刻t被治愈了,并且沒有被它的鄰居節(jié)點(diǎn)所感染(由ζi,t定義)；

情況3 節(jié)點(diǎn)i在時(shí)刻t之前已被感染,在時(shí)刻t前受到了鄰居節(jié)點(diǎn)的感染,但是該感染對節(jié)點(diǎn)i沒有奏效,且節(jié)點(diǎn)i最終在時(shí)刻t被治愈了.

依據(jù)上述定義，假設(shè)某節(jié)點(diǎn)i被其鄰居感染，但被治愈的概率為50%，那么可定義該節(jié)點(diǎn)的健康概率為：

1-pi,t= (1-pi,t-1)ζi,t+δpi,t-1ζi,t+0.5

×δpi,t-1(1-ζi,t)

(2)

式(2)中,i的取值范圍是是從1到N，(1-pi,t-1)ζi,t、δpi,t-1ζi,t和0.5×δpi,t-1(1-ζi,t)分別對應(yīng)上面定義的三種情況.當(dāng)某特定網(wǎng)絡(luò)中感染概率β和自愈概率δ都賦值后，可計(jì)算出pi,t，并據(jù)式(3)可得時(shí)刻t時(shí)網(wǎng)絡(luò)中所有被感染節(jié)點(diǎn)所占比例ηt，其中N為網(wǎng)絡(luò)中所有節(jié)點(diǎn)個(gè)數(shù)：

(3)

3.2 權(quán)重平衡算法WEBA

權(quán)重平衡算法WEBA(Weight-Balanced Algorithm)用于定義某個(gè)節(jié)點(diǎn)對于其所屬社團(tuán)的重要性權(quán)值[13]，對于包含N個(gè)節(jié)點(diǎn)和m條邊的無向圖G=(N，E)而言，定義互不相連的L個(gè)核心節(jié)點(diǎn)(即Kernel)子集{K1，…，KL}，對于網(wǎng)絡(luò)所有邊組成的集合E?V×V(|E|為所有邊的條數(shù))，滿足：

?i,?u∈Ki,?v?Ki,

|E(u，Ki)|≥|E(v，Ki)| and |E(Ki,u)|≥|E(Ki,v)|,

where |E(A,B)|={(u,v)∈E,u∈A,v∈B},

for {A,B?V}

(4)

接著定義節(jié)點(diǎn)的權(quán)重向量ω(ν)如下：

ω(ν)={ω1(ν)，…，ωL(ν)}，ν∈V

(5)

ωL(ν)是節(jié)點(diǎn)i對于其所屬社團(tuán)核心的重要性權(quán)重.據(jù)WEBA算法可計(jì)算和排序不同節(jié)點(diǎn)的ωL(ν)值得到社團(tuán)核心節(jié)點(diǎn)序列，對于某給定整數(shù)值k(假設(shè)k為Kernel中節(jié)點(diǎn)個(gè)數(shù))，計(jì)算排序不同節(jié)點(diǎn)的操作變?yōu)槿缦聝?yōu)化問題[14]：

ωi(ν)≥0,?ν∈V,?i∈{1,…,L}

(6)

當(dāng)式(6)計(jì)算完畢得到L(ω)的全局最大值，WEBA算法會收斂，可得全圖核心節(jié)點(diǎn)序列.

3.3 基于傳染病模型LPA重疊社團(tuán)劃分算法

本文所提基于傳染病模型的ESLPA高效重疊社團(tuán)劃分算法構(gòu)建基于“社團(tuán)”定義的一個(gè)默認(rèn)常識[15]，即當(dāng)社團(tuán)內(nèi)部的某個(gè)節(jié)點(diǎn)被病毒所感染后，相對于社團(tuán)外部的節(jié)點(diǎn)而言，在社團(tuán)內(nèi)部該節(jié)點(diǎn)影響其他節(jié)點(diǎn)感染病毒的速度更快，該過程可模擬某些網(wǎng)絡(luò)輿情信息在社團(tuán)內(nèi)部傳播比社團(tuán)外部傳播更快的現(xiàn)實(shí)情況.

在線社交網(wǎng)絡(luò)符合冪律分布，社團(tuán)內(nèi)連接邊數(shù)遠(yuǎn)多于該社團(tuán)和外部連接邊數(shù),因此病毒在社團(tuán)內(nèi)更容易快速傳播，感染病毒的節(jié)點(diǎn)越是處于“核心節(jié)點(diǎn)”地位，其被感染和傳播病毒的速度越快，并更易將病毒傳播至整個(gè)網(wǎng)絡(luò).

本文所提方法首先用種子病毒感染由RAK算法[2]劃分所得社團(tuán)和WEBA算法檢測出的社團(tuán)核心節(jié)點(diǎn)后，社團(tuán)被定義為受相同病毒感染的節(jié)點(diǎn)群，然后模仿病毒傳染過程，其他社團(tuán)成員以被感染的模式展示出來，快速得到最終較精確的社團(tuán)劃分結(jié)果.本文所提基于傳染病模型的LPA高效重疊社團(tuán)劃分算法步驟如下：

(1)采用Raghavan的RAK算法[2]進(jìn)行初步的社團(tuán)劃分，獲得較粗的社團(tuán)分布情況；

(2)在這些初步劃分所得社團(tuán)，用WEBA算法計(jì)算得到這些社團(tuán)的核心節(jié)點(diǎn)序列[13]；

(4)最終感染過程收斂，并獲得最終社團(tuán)劃分結(jié)果.

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

4.1 實(shí)驗(yàn)環(huán)境

處理器:Intel(R) Pentium(R) 4，3.0GHz;內(nèi)存:2GB;硬盤:160GB;操作系統(tǒng):Windows XP;編譯環(huán)境：Matlab R2010和JDK1.7.

4.2 LFR Benchmark網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

我們選取了在社區(qū)發(fā)現(xiàn)方面被廣泛采用的LFR(Lancichinetti Fortunate Radicchio)Benchmark網(wǎng)絡(luò)程序[16]來生成基準(zhǔn)模擬網(wǎng)絡(luò)數(shù)據(jù).LFR 能夠靈活生成高質(zhì)量的測試網(wǎng)絡(luò)數(shù)據(jù)，LFR網(wǎng)絡(luò)生成時(shí)可包含真實(shí)網(wǎng)絡(luò)所具有的統(tǒng)計(jì)特性，例如真實(shí)網(wǎng)絡(luò)中度分布不均勻性和社團(tuán)大小分布的不均勻性等.實(shí)驗(yàn)共生成4組測試網(wǎng)絡(luò)，為保證實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，每組網(wǎng)絡(luò)均用本文所提ESLPA算法和經(jīng)典COPRA算法[3]測試了20次，取其平均值作為實(shí)驗(yàn)結(jié)果.

由于存在重疊社團(tuán)，故未選用模塊度(Modularity)作為算法評測標(biāo)準(zhǔn)，而是選用了重疊社團(tuán)發(fā)現(xiàn)中常被采用的規(guī)范化互信息[17](NMI，Normalized Mutual Information)作為評測標(biāo)準(zhǔn).NMI標(biāo)準(zhǔn)由Danon等2005年提出，用于衡量算法劃分的社區(qū)結(jié)構(gòu)和預(yù)先已知社區(qū)結(jié)構(gòu)間的差異[17].NMI基于混合矩陣(confusion matrix)M計(jì)算，如式(7)所示：

(7)

式(7)中,Ni表示M中第i行元素的總和，Nj表示M中第j列元素的總和.NMI指標(biāo)可衡量劃分出的社區(qū)結(jié)構(gòu)與已知網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的差異，該值越大，則表明獲得的社區(qū)結(jié)構(gòu)劃分越好，NMI達(dá)到最大值1時(shí)，說明算法發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)與已知社區(qū)結(jié)構(gòu)完全一致.

表2 LFR測試網(wǎng)絡(luò)實(shí)驗(yàn)數(shù)據(jù)集

圖1至圖4給出了ESLPA算法和COPRA算法[3]在表1所示的4組LFR Benchmark網(wǎng)絡(luò)程序上的實(shí)驗(yàn)結(jié)果，圖中的y-軸表示劃分結(jié)果中的NMI結(jié)果數(shù)值，x-軸表示網(wǎng)絡(luò)中位于重疊社團(tuán)的節(jié)點(diǎn)比例.從圖中顯示結(jié)果可知，ESLPA算法在NMI數(shù)值上比COPRA算法結(jié)果要好，劃分結(jié)果更為精確，并且隨著MIX混合參數(shù)的數(shù)值變大，兩種算法的劃分精度差距減小.

4.3 隨機(jī)網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

劃分精度和劃分速度是評價(jià)社團(tuán)劃分算法性能的重要指標(biāo)，我們給出了ESLPA算法和其他典型社團(tuán)算法在這兩個(gè)維度上的實(shí)驗(yàn)結(jié)果，作為定量比較和評價(jià)各算法性能的重要依據(jù).實(shí)驗(yàn)數(shù)據(jù)集選取了廣泛采用的已知社團(tuán)結(jié)構(gòu)隨機(jī)網(wǎng)絡(luò)測試法[15]，在該方法中，已知社團(tuán)結(jié)構(gòu)的隨機(jī)網(wǎng)絡(luò)定義為(C,s,d,Pin)[15]，其中C表示網(wǎng)絡(luò)社團(tuán)的個(gè)數(shù)，s表示每個(gè)社團(tuán)包含節(jié)點(diǎn)的個(gè)數(shù)，d表示網(wǎng)絡(luò)中節(jié)點(diǎn)的平均度,Pin表示社團(tuán)內(nèi)連接密度(即社團(tuán)內(nèi)連接總數(shù)與網(wǎng)絡(luò)連接總數(shù)的比值).Pin值越大，隨機(jī)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)越明顯；反之社團(tuán)結(jié)構(gòu)越模糊.特別地，當(dāng)Pin<0.5時(shí)，認(rèn)為該隨機(jī)網(wǎng)絡(luò)不具有社團(tuán)結(jié)構(gòu).一個(gè)隨機(jī)網(wǎng)絡(luò)被正確劃分當(dāng)且僅當(dāng)預(yù)定義的C個(gè)網(wǎng)絡(luò)社團(tuán)被全部正確識別，且沒有某個(gè)社團(tuán)被進(jìn)一步分割為多個(gè)子社團(tuán).

4.3.1 劃分精度比較

目前社團(tuán)劃分大致可分為基于優(yōu)化的劃分方法和啟發(fā)式劃分方法[18]，我們分別從基于優(yōu)化的劃分方法和啟發(fā)式劃分方法中選擇了具有代表性的七種算法GN、FastGN、GA、FEC、N-Cut、A-Cut和CPM(算法源代碼來自文獻(xiàn)[18])和側(cè)重于挖掘重疊社團(tuán)的經(jīng)典COPRA算法[3]進(jìn)行了比較.圖5給出了本文ESLPA劃分算法和其他七種典型算法劃分精度比較的實(shí)驗(yàn)結(jié)果，這里選取了被普遍采用的基準(zhǔn)隨機(jī)網(wǎng)絡(luò)RN(4,32,16,Pin).在圖5中，對應(yīng)于x-軸上的每個(gè)Pin數(shù)值都生成了一組含100個(gè)隨機(jī)網(wǎng)絡(luò)的數(shù)據(jù)集(隨機(jī)網(wǎng)絡(luò)通過實(shí)現(xiàn)文獻(xiàn)[18]中介紹的算法批量生成，一共生成了12組)，y-軸表示劃分精度.劃分精度曲線上的每個(gè)數(shù)據(jù)點(diǎn)是該算法劃分100個(gè)隨機(jī)網(wǎng)絡(luò)得到的平均準(zhǔn)確率.

由圖5分析可知：(1)ESLPA算法在Pin<0.5存在重疊社團(tuán)時(shí)，劃分精度略低于計(jì)算復(fù)雜度非常高的GA算法、N-cut算法和A-cut算法，但是明顯優(yōu)于COPRA算法、FastGN算法(圖5中的FN曲線)和CPM算法；(2)在0.5

由圖5可得結(jié)論：在重疊社團(tuán)的劃分精度上ESLPA算法優(yōu)于COPRA算法，特別是在重疊社團(tuán)較明顯時(shí)(Pin<0.55)，劃分精度甚至接近時(shí)間復(fù)雜度非常高的GA算法、N-cut算法和A-cut算法，明顯優(yōu)于GN算法、FastGN算法和CPM算法等經(jīng)典算法.

4.3.2 劃分速度比較

圖6實(shí)驗(yàn)結(jié)果給出了ESLPA算法和其他八種經(jīng)典社團(tuán)劃分算法在劃分速度上的時(shí)間復(fù)雜性比較(由于GA算法時(shí)間復(fù)雜度太高[18]，故未和它進(jìn)行比較)，其中包含經(jīng)典LPA和經(jīng)典RAK算法[2]，實(shí)驗(yàn)結(jié)果給出了各算法的實(shí)際運(yùn)行時(shí)間，作為比較和評價(jià)各算法性能的重要依據(jù).本實(shí)驗(yàn)采用隨機(jī)網(wǎng)絡(luò)RN(4,s,16,0.7)作為測試網(wǎng)絡(luò).該網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)確定，規(guī)?？捎蓅值調(diào)節(jié)，共包括4s個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，64s條邊.圖6中，y-軸表示以秒為單位的算法實(shí)際運(yùn)行時(shí)間，x-軸表示被測試網(wǎng)絡(luò)的網(wǎng)絡(luò)規(guī)模(節(jié)點(diǎn)數(shù)+邊數(shù)).

分析圖6所示實(shí)驗(yàn)結(jié)果可知，ESLPA算法的計(jì)算速度在經(jīng)典的LPA和RAK算法之間，相對于經(jīng)典LPA算法的運(yùn)行時(shí)間，有較明顯改善.從時(shí)間復(fù)雜度o(n2)(n是網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù))來衡量，其運(yùn)行速度明顯快于GN(時(shí)間復(fù)雜度接近o(n3))，從整體上來說，均屬于啟發(fā)式算法的LPA、ESLPA、RAK、FEC和CPM算法，其實(shí)際運(yùn)行時(shí)間與網(wǎng)絡(luò)規(guī)模呈近似線性比例關(guān)系，運(yùn)行較快，其次是兩種譜方法N-Cut和A-Cut.

4.4 真實(shí)在線社交網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

為驗(yàn)證ESLPA算法在真實(shí)社交網(wǎng)絡(luò)上的劃分效果，我們依據(jù)Leskove等[11]數(shù)據(jù)采集方法，采集了某個(gè)已知大三學(xué)生人人網(wǎng)交友圈的真實(shí)社交網(wǎng)絡(luò)(表3中數(shù)據(jù)A).另一個(gè)真實(shí)社會網(wǎng)絡(luò)數(shù)據(jù)來自新浪微博(表3中數(shù)據(jù)B)，數(shù)據(jù)A和B均為典型小世界網(wǎng)絡(luò).圖7所示劃分結(jié)果與該學(xué)生的真實(shí)社團(tuán)結(jié)構(gòu)保持了一致，結(jié)果準(zhǔn)確顯示了該學(xué)生所在的4個(gè)社團(tuán)：高中、大一、大二和大三同學(xué)，最大重疊模塊密度為7.2541.圖8所示劃分結(jié)果顯示該網(wǎng)絡(luò)被劃分為兩個(gè)重疊社團(tuán)，最大重疊模塊密度為6.8975，也與真實(shí)情況相符，以上兩個(gè)實(shí)驗(yàn)結(jié)果顯示了ESLPA算法在大型在線社交網(wǎng)絡(luò)上的較好性能.

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

Dataset點(diǎn)邊平均度平均聚類系數(shù)平均路徑長度A2405278126115．6450．6514．7B4681980746．3230．5714．23

4.5 真實(shí)重疊網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

為檢測ELSPA算法在具有重疊的不確定社團(tuán)結(jié)構(gòu)的真實(shí)網(wǎng)絡(luò)上的性能，選擇了具有重疊社團(tuán)的經(jīng)典數(shù)據(jù)集，選取了 Newman個(gè)人網(wǎng)站(www.personal.umich.edu/～mejn/netdataGirvan)上的部分標(biāo)準(zhǔn)數(shù)據(jù)集Netscience、Wordadja、Lesmis、Polbooks和Celegan等.采用近年被多次引用的網(wǎng)絡(luò)社團(tuán)輪廓方法(Network Community Profile，NCP)[11]，選取Q值、社團(tuán)劃分個(gè)數(shù)、劃分后社團(tuán)最大連通分量大小以及強(qiáng)弱社團(tuán)個(gè)數(shù)比例[11]4個(gè)參數(shù)比較了代表性的LPA類算法RAK、COPRA和本文ELSPA算法的性能，實(shí)驗(yàn)結(jié)果如表4所示.

通過分析表4可知:在這4個(gè)網(wǎng)絡(luò)數(shù)據(jù)集上，本文所提ELSPA算法的Q值非常接近RAK和COPRA算法，但是在強(qiáng)弱社團(tuán)比和社團(tuán)最大連通分量大小兩個(gè)指標(biāo)上ELSPA算法數(shù)值優(yōu)于RAK和COPRA，所得社團(tuán)結(jié)構(gòu)節(jié)點(diǎn)數(shù)更多，社團(tuán)結(jié)構(gòu)更明顯，可見其劃分效果更好.

表4 真實(shí)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)劃分性能實(shí)驗(yàn)結(jié)果

5 結(jié)束語

群體中的個(gè)體具有更加密集的聯(lián)系和較高概率的相互信息傳播，本文針對LPA算法運(yùn)行速率低和融合收斂慢的缺點(diǎn)，提出了一種通過定義網(wǎng)絡(luò)核心節(jié)點(diǎn)和網(wǎng)絡(luò)連接矩陣非零最大特征值閥值，利用傳播病毒模型來發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)的新方法.通過經(jīng)典LFR Benchmark模擬測試網(wǎng)絡(luò)、隨機(jī)網(wǎng)絡(luò)、真實(shí)網(wǎng)絡(luò)(含社交網(wǎng)絡(luò)和非社交的重疊網(wǎng)絡(luò))數(shù)據(jù)上的算法驗(yàn)證，表明該算法時(shí)間復(fù)雜度大幅優(yōu)于經(jīng)典LPA算法，在重疊社團(tuán)劃分上精確度優(yōu)于基于LPA模型的經(jīng)典COPRA算法，特別是在重疊社團(tuán)較明顯時(shí)，劃分精度接近精度較高GA、N-cut和A-cut算法，明顯優(yōu)于GN、FastGN和CPM等經(jīng)典算法.

后續(xù)研究將如下展開：(1)進(jìn)一步調(diào)整算法中病毒傳播模型用于特定需求的社團(tuán)發(fā)現(xiàn)；(2)進(jìn)一步地研究病毒在帶有不同特點(diǎn)的個(gè)體間具體傳播過程，通過病毒傳播模型來發(fā)現(xiàn)具有不同興趣的多種異質(zhì)社團(tuán).

[1]ZHU X,Ghahramani Z,Lafferty J.Semi-supervised learning using Gaussian fields and harmonic functions[A].Proceedings of the Twentieth International Conference on Machine Learning[C].Washington DC,USA:AAAI,2003.912-919.

[2]Usha Nandini Raghavan,R′eka Albert,Soundar Kumara.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(3):036106,1-11.

[3]Steve Gregory.Finding overlappingcommunities in networks by label propagation[J].New J Phys,2010,12(10):103018,1-26.

[4]金弟,劉大有,等.基于局部探測的快速復(fù)雜網(wǎng)絡(luò)聚類算法[J].電子學(xué)報(bào)，2011,39(11):2540-2546.

Jin Di,Liu Dayou,et al.Fast complex network clustering algorithm using local detection[J].Acta Electronica Sinica,2011,39(11):2540-2546.(in Chinese)

[5]Cordasco G，Gargano L.Community detection via semi-synchronous label propagation algorithms[A].Proceedings of 2010 IEEE International Workshop on Business Applications of Social Network Analysis[C].Bangalore,India:IEEE Computer Society，2010.45-50.

[6]William O Kermack,Anderson G McKendrick.Contributions to the mathematical theory of epidemics,part I[J].Proceedings of the Royal Society of London，Series A,1927,115(772):700-721.

[7]William O Kermack,Anderson G McKendrick.Contributions to the mathematical theory of epidemics,part II.The problem of endemicity[J].Proceedings of the Royal Society of London，Series A,1932,138(834):55-83.

[8]顧亦然，夏玲玲.在線社交網(wǎng)絡(luò)中謠言的傳播與抑制[J].物理學(xué)報(bào).2012,61(23):238701,1-7.

Gu Yi-Ran,Xia Ling-Ling.The propagation and inhibition of rumors in online social network[J].Acta Phys Sin,2012,61(23):238701,1-7.(in Chinese)

[9]王超,楊旭穎,等.基于SEIR的社交網(wǎng)絡(luò)信息傳播模型[J].電子學(xué)報(bào),2014,11(1):2325-2330.

Wang Chao,Yang Xuying，et al.SEIR-based model for the information Spreading over SNS[J].Acta Electronica Sinica,2014,11(1):2325-2330.(in Chinese)

[10]Yang Wang,Deepayan Chakrabarti,Chenxi Wang.Epidemic spreading in real networks:An eigenvalue viewpoint[A].Proceedings of 22nd Symposium in Reliable Distributed Computing[C].Florence Italy:Institute of Electrical and Electronics Engineers Computer Society,200.25-34.

[11]Jure Leskovec,Kevin J Lang,Michael W.Mahoney.Empirical comparison of algorithms for network community detection[A].Proceedings of WWW ACM 2010[C].Raleigh,NC:Association for Computing Machinery,2010.631-640.

[12]R Pastor-Satorras,A Vespignani.Epidemic dynamics infinite size scale-free networks[J].Physical Review E,2002,65(3):035108,1-4.

[13]Liaoruo Wang,Tiancheng Lou,Jie Tang,John E Hopcroft.Detecting community kernels in large social networks[A].Proceedings of 2011 IEEE 11th International Conference on Data Mining[C].Vancouver,BC,Canada:Institute of Electrical and Electronics Engineers Inc,2011.784-793.

[14]Michael R Garey,David S Johnson.Computers and Intractability :A Guide to the Theory of NP-Completenes[M].San Francisco :W HFreeman Company,1979.90-194.

[15]Girvan M,Newman MEJ.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.

[16]Andrea Lancichinetti,Santo Fortunato,Filippo Radicchi.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110,1-5.

[17]Leon Vicsek Danon，Jordi Duch，Alex Arenas,Albert Diaz-Guilera.Comparing community structure identification[J].Journal of Statistical Mechanics Theory & Experiment，2005,09:P09008,1-10.

[18]楊博,劉大有,等.復(fù)雜網(wǎng)絡(luò)聚類方法[J].軟件學(xué)報(bào)，2009,20(1):54-66.

Yang Bo,Liu Dayou,et al.Complex network clustering algorithms[J].Journal of Software,2009,20(1):54-66.(in Chinese)

鄧小龍 男，1977年10月出生，湖北沙市人，博士，北京郵電大學(xué)教師、碩導(dǎo)，主要研究領(lǐng)域?yàn)樯缃痪W(wǎng)絡(luò)，數(shù)據(jù)挖掘.

E-mail:shannondeng@bupt.edu.cn

溫 穎 男，1994年8月出生，江西贛州人，北京郵電大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)樯鐣?jì)算，復(fù)雜系統(tǒng)動力學(xué).

E-mail:wenying@bupt.edu.cn

Efficient Epidemic Spreading Model Based LPA Threshold Community Detection Method

DENG Xiao-long1,WEN Ying2

(1.KeyLabofTrustworthyDistributedComputingandServiceofEducationMinistry,BeijingUniversityofPostandTelecommunication,Beijing100876,China； 2.DepartmentofInternationalSchool,BeijingUniversityofPostandTelecommunication,Beijing100876,China)

Community detection method is significant to character statistics of complex network.Community detection in inhomogeneous structured network is an attractive research problem while most previous approaches attempted to divide networks into communities which are based on node or edge measurement.The label propagation algorithm (LPA) adopts semi-supervised machine learning and implemented community detection in an intelligent way with automatic convergent process of network node label iteration but it often results in low efficiency in the final convergent process.In this article,aiming to promote low efficiency and stagnant converging rate of LPA in network with overlapping communities,we propose a new method (ESLPA) for community detection using epidemic spreading model combined with network connection matrix’s largest Eigenvalue as label propagation threshold.Extensive experiments in synthetic signed network and real-life large networks derived from online social media are conducted to explore optimal mechanism of the most suitable community detecting virus infection threshold.Experiments result prove that our method is more accurate and faster than several traditional modularity based community detection methods such as COPRA,GN,FastGN and CPM.

overlapping community detection;Epidemic model;information spreading;largest eigenvalue

2015-02-12;

2015-06-05;責(zé)任編輯：梅志強(qiáng)

國家973重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(No.2013CB329600);“十二五”國家科技支撐計(jì)劃國家文化科技創(chuàng)新工程(No.2013BAH43F01);國家自然科學(xué)基金(No.91024032)

TP391

A

0372-2112 (2016)09-2114-07

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.09.014