基于傳染病模型的LPA特征閥值社團劃分方法

鄧小龍,溫 穎

(1.北京郵電大學可信分布式計算與服務教育部重點實驗室,北京 100876; 2.北京郵電大學國際學院,北京 100876)

?

基于傳染病模型的LPA特征閥值社團劃分方法

鄧小龍1,溫 穎2

(1.北京郵電大學可信分布式計算與服務教育部重點實驗室,北京 100876; 2.北京郵電大學國際學院,北京 100876)

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

重疊社團劃分；流行病模型；信息擴散；最大非零特征值

1 引言

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

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

2 相關研究

2.1 基于標簽傳播的社團劃分算法

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

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

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

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

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

2.2 傳染病傳播模型

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

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

3 基于傳染病模型的社團劃分算法

本文在Leskove等[11，12]研究成果基礎上，結合信息傳播的相關定義和假設，以及病毒傳播的網絡譜半徑等重要參數模型，構建了基于傳染病模型的重疊社團劃分算法ESLPA.

3.1 傳染病傳播模型定義

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

表1 傳染病模型符號定義

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

(1)

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

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

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

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

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

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)分別對應上面定義的三種情況.當某特定網絡中感染概率β和自愈概率δ都賦值后，可計算出pi,t，并據式(3)可得時刻t時網絡中所有被感染節(jié)點所占比例ηt，其中N為網絡中所有節(jié)點個數：

(3)

3.2 權重平衡算法WEBA

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

?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é)點的權重向量ω(ν)如下：

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

(5)

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

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

(6)

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

3.3 基于傳染病模型LPA重疊社團劃分算法

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

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

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

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

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

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

4 實驗結果

4.1 實驗環(huán)境

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

4.2 LFR Benchmark網絡數據集實驗結果

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

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

(7)

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

表2 LFR測試網絡實驗數據集

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

4.3 隨機網絡數據集實驗結果

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

4.3.1 劃分精度比較

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

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

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

4.3.2 劃分速度比較

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

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

4.4 真實在線社交網絡數據集實驗結果

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

表3 真實社交網絡數據集

Dataset點邊平均度平均聚類系數平均路徑長度A2405278126115．6450．6514．7B4681980746．3230．5714．23

4.5 真實重疊網絡數據集實驗結果

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

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

表4 真實網絡社團結構劃分性能實驗結果

5 結束語

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

后續(xù)研究將如下展開：(1)進一步調整算法中病毒傳播模型用于特定需求的社團發(fā)現(xiàn)；(2)進一步地研究病毒在帶有不同特點的個體間具體傳播過程，通過病毒傳播模型來發(fā)現(xià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]金弟,劉大有,等.基于局部探測的快速復雜網絡聚類算法[J].電子學報，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]顧亦然，夏玲玲.在線社交網絡中謠言的傳播與抑制[J].物理學報.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的社交網絡信息傳播模型[J].電子學報,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]楊博,劉大有,等.復雜網絡聚類方法[J].軟件學報，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月出生，湖北沙市人，博士，北京郵電大學教師、碩導，主要研究領域為社交網絡，數據挖掘.

E-mail:shannondeng@bupt.edu.cn

溫 穎 男，1994年8月出生，江西贛州人，北京郵電大學碩士研究生，主要研究領域為社會計算，復雜系統(tǒng)動力學.

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;責任編輯：梅志強

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

TP391

A

0372-2112 (2016)09-2114-07

??學報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.09.014