基于節(jié)點(diǎn)影響力的標(biāo)簽傳播社區(qū)檢測(cè)算法

馬 秀，冀慶斌

(中北大學(xué) 理學(xué)院， 太原 030051)

人們發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)除了擁有小世界特性和無標(biāo)度特性外，還具有社區(qū)結(jié)構(gòu)[1]的拓?fù)湫再|(zhì)。復(fù)雜網(wǎng)絡(luò)中存在一些特殊的節(jié)點(diǎn)組，同一組內(nèi)節(jié)點(diǎn)之間的連接較為稠密，不同組之間節(jié)點(diǎn)連接較為稀疏[2]。社區(qū)結(jié)構(gòu)的研究有助于發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中隱藏著的個(gè)體關(guān)系。

學(xué)者們對(duì)復(fù)雜網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的研究做了大量工作，提出了許多社區(qū)檢測(cè)算法。主要有：Kernighan等[3]提出的試探優(yōu)化算法，時(shí)間復(fù)雜度為O(n2)；Girvan等[4]提出的基于邊介數(shù)的分割算法，時(shí)間復(fù)雜度為O(n3)；Palla等[5]首次提出檢測(cè)重疊社區(qū)結(jié)構(gòu)的派系過濾算法；Clauset等[6]提出的貪婪算法(CNM算法)，使算法復(fù)雜度降為O(nlog2n)，已接近線性復(fù)雜度；2007年Raghavan等[7]提出了一種基于標(biāo)簽傳播思想的社區(qū)檢測(cè)算法(LPA算法)，時(shí)間復(fù)雜度為O(m)。該算法具有線性的時(shí)間復(fù)雜度，提高了在大規(guī)模網(wǎng)絡(luò)社區(qū)檢測(cè)的效率。但是LPA算法中存在的隨機(jī)性，使得算法劃分結(jié)果穩(wěn)定性差。

針對(duì)LPA算法存在的問題，許多學(xué)者提出改進(jìn)算法。Barber等[8]提出帶約束的模塊化標(biāo)簽傳播算法LPAm，通過引入一個(gè)目標(biāo)函數(shù)H，利用標(biāo)簽傳播算法檢測(cè)H函數(shù)的最優(yōu)解，將社區(qū)檢測(cè)問題轉(zhuǎn)化為目標(biāo)函數(shù)最大值問題；然而LPAm算法可能會(huì)將網(wǎng)絡(luò)劃分為相似的社區(qū)，導(dǎo)致模塊度陷入局部極大值的問題，為了避免這種情況的出現(xiàn)，Liu等[9]將LPAm算法與多步貪婪凝聚算法(MSG)相結(jié)合，提出基于模塊度專業(yè)化的標(biāo)簽傳播算法LPAm+，該算法復(fù)雜度為O(nlogm2)；Zhao等[10]提出了基于標(biāo)簽熵序列的標(biāo)簽傳播算法LPA-E，節(jié)點(diǎn)將根據(jù)標(biāo)簽熵值從小到大進(jìn)行更新。這些算法從不同的角度對(duì)LPA算法進(jìn)行了改進(jìn)，在一定程度上提高了算法的穩(wěn)定性，但均未考慮網(wǎng)絡(luò)中節(jié)點(diǎn)影響力的差異對(duì)標(biāo)簽傳播的影響。

本文提出基于節(jié)點(diǎn)影響力的標(biāo)簽傳播社區(qū)檢測(cè)算法(KLPA算法)，在評(píng)價(jià)網(wǎng)絡(luò)中節(jié)點(diǎn)影響力的基礎(chǔ)上，選取部分影響力大的節(jié)點(diǎn)為種子節(jié)點(diǎn)，在初始標(biāo)簽分配上改進(jìn)算法。另外，在標(biāo)簽決策過程中，考慮相同標(biāo)簽節(jié)點(diǎn)之間的關(guān)系，選擇影響力大的標(biāo)簽進(jìn)行更新。通過在不同數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果證明，本文改進(jìn)的算法減少了隨機(jī)性，提高了算法的穩(wěn)定性。

1 相關(guān)工作

1.1 標(biāo)簽傳播算法的隨機(jī)性問題

LPA算法的基本過程是：標(biāo)簽初始化時(shí)給網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)分配唯一的標(biāo)簽；在傳播過程中，各節(jié)點(diǎn)的標(biāo)簽更新為鄰接節(jié)點(diǎn)中頻數(shù)最多的標(biāo)簽，當(dāng)出現(xiàn)多個(gè)頻數(shù)最多的標(biāo)簽時(shí)，隨機(jī)選擇一個(gè)標(biāo)簽更新該節(jié)點(diǎn)；若網(wǎng)絡(luò)中所有節(jié)點(diǎn)的標(biāo)簽均更新為其鄰接節(jié)點(diǎn)中頻數(shù)最多的標(biāo)簽時(shí)，算法結(jié)束，此時(shí)標(biāo)簽相同的節(jié)點(diǎn)形成一個(gè)社區(qū)。

分析標(biāo)簽傳播算法，我們發(fā)現(xiàn)該算法中有兩個(gè)步驟體現(xiàn)隨機(jī)性：1)在每一次迭代過程，節(jié)點(diǎn)的更新順序都會(huì)重新排列。2)在節(jié)點(diǎn)標(biāo)簽更新時(shí)，當(dāng)鄰接節(jié)點(diǎn)中頻數(shù)最多的標(biāo)簽出現(xiàn)多個(gè)時(shí)，采用隨機(jī)選擇策略。這些隨機(jī)性會(huì)增加算法的迭代次數(shù)，降低算法的穩(wěn)定性，導(dǎo)致多次實(shí)驗(yàn)的結(jié)果有差異性。

針對(duì)存在的問題，研究者們通過評(píng)價(jià)網(wǎng)絡(luò)中節(jié)點(diǎn)的影響力，提出了系列改進(jìn)算法。如LIB算法[11]提出采用文獻(xiàn)[12]的方法，選擇網(wǎng)絡(luò)中前k個(gè)影響力較大的節(jié)點(diǎn)為初始標(biāo)簽開始傳播，但該方法無法直接確定k值；黃佳鑫等[13]在衡量網(wǎng)絡(luò)中節(jié)點(diǎn)重要性時(shí)綜合考慮點(diǎn)權(quán)和集聚系數(shù)，但該方法中計(jì)算集聚系數(shù)增加了標(biāo)簽傳播算法的復(fù)雜度；IPLPA算法[14]在k-shell分解[15]的基礎(chǔ)上，通過綜合考慮節(jié)點(diǎn)被刪除時(shí)的迭代層數(shù)與鄰接節(jié)點(diǎn)的度值，構(gòu)造新的衡量節(jié)點(diǎn)重要性的計(jì)算方法，指導(dǎo)節(jié)點(diǎn)的更新順序和標(biāo)簽更新策略。與該方法不同，本文通過采用k-shell分解衡量網(wǎng)絡(luò)中節(jié)點(diǎn)的影響力，選擇部分k-shell值較大的節(jié)點(diǎn)為網(wǎng)絡(luò)的種子節(jié)點(diǎn)，在標(biāo)簽初始化時(shí)，只給種子節(jié)點(diǎn)分配標(biāo)簽。

1.2 節(jié)點(diǎn)影響力分析

網(wǎng)絡(luò)中節(jié)點(diǎn)的影響力具有差異性，快速準(zhǔn)確地識(shí)別影響力較大的節(jié)點(diǎn)，有助于網(wǎng)絡(luò)中信息更快地傳播。很多評(píng)價(jià)節(jié)點(diǎn)影響力的指標(biāo)被提出：傳統(tǒng)的度中心性方法計(jì)算復(fù)雜度低，但沒有考慮節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置；介數(shù)中心性與接近中心性由于都要計(jì)算網(wǎng)絡(luò)中各節(jié)點(diǎn)之間的距離，因此時(shí)間復(fù)雜度都比較高，不適合用于大規(guī)模網(wǎng)絡(luò)。此外，很多研究中將網(wǎng)頁排名算法用于分析網(wǎng)絡(luò)中節(jié)點(diǎn)的影響力排序，比如He等[16]采用PageRank作為節(jié)點(diǎn)影響力判定標(biāo)準(zhǔn)，但是該方法存在節(jié)點(diǎn)排序不唯一的問題；Lü等[17]提出的LeaderRank解決了PageRank存在的問題，指出利用LeaderRank算法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)影響力排序比PageRank算法排序更精準(zhǔn)。Kitsak等提出k-shell分解方法，它是利用節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的位置確定節(jié)點(diǎn)的影響力。文獻(xiàn)[15]指出采用k-shell分解方法衡量節(jié)點(diǎn)的影響力比度和介數(shù)更為準(zhǔn)確，并且具有線性的時(shí)間復(fù)雜度，適用于大型網(wǎng)絡(luò)。

k-shell分解方法具體過程如下：首先，去掉網(wǎng)絡(luò)中所有度值為1的節(jié)點(diǎn)及連邊，這時(shí)可能會(huì)出現(xiàn)一些新的度值為1的節(jié)點(diǎn)，再去除這些節(jié)點(diǎn)及其連邊，直到網(wǎng)絡(luò)中剩下的節(jié)點(diǎn)的度值都大于1為止，這些被去掉的點(diǎn)及其之間的連邊稱為1-shell；隨后繼續(xù)分解，去掉度值小于等于2的節(jié)點(diǎn)以及連邊，以此類推，直至網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)都被劃分到某一個(gè)k-shell當(dāng)中。用k-shell指標(biāo)來衡量網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)傳播的影響力程度，是目前為止被廣泛認(rèn)可的一種度量方法[18]，認(rèn)為k值越大的節(jié)點(diǎn)越處于網(wǎng)絡(luò)中的核心位置，其影響力就越大。

2 基于節(jié)點(diǎn)影響力的標(biāo)簽傳播社區(qū)檢測(cè)算法

2.1 種子節(jié)點(diǎn)的選取

在KLPA算法中，考慮到網(wǎng)絡(luò)中節(jié)點(diǎn)影響力的差異性，有效地選取網(wǎng)絡(luò)中部分影響力大的節(jié)點(diǎn)組成種子節(jié)點(diǎn)集，在標(biāo)簽初始化時(shí)，只為種子節(jié)點(diǎn)集中節(jié)點(diǎn)分配不同的標(biāo)簽，不僅能減少初始標(biāo)簽的數(shù)目，而且可以使標(biāo)簽影響的范圍更廣。

定義1 給定網(wǎng)絡(luò)G=(V,E)，其中V表示節(jié)點(diǎn)集，E表示邊集。定義種子節(jié)點(diǎn)集M。

M={i|ki>K}

(1)

其中節(jié)點(diǎn)i∈V，ki,(i=1…n)表示節(jié)點(diǎn)i的k-shell值，K表示節(jié)點(diǎn)k-shell值的平均值。

2.2 節(jié)點(diǎn)標(biāo)簽更新策略

在LPA算法中，各節(jié)點(diǎn)標(biāo)簽將更新為鄰接節(jié)點(diǎn)中頻數(shù)最多的標(biāo)簽，標(biāo)簽更新公式如下：

其中：li表示待更新節(jié)點(diǎn)i的標(biāo)簽；N(i)表示節(jié)點(diǎn)i鄰接節(jié)點(diǎn)的集合；lj表示節(jié)點(diǎn)i鄰接節(jié)點(diǎn)j的標(biāo)簽；δ(lj,l)為克羅內(nèi)克函數(shù)。當(dāng)鄰接節(jié)點(diǎn)中頻數(shù)最多的標(biāo)簽不止一個(gè)時(shí)，節(jié)點(diǎn)i會(huì)隨機(jī)選擇一個(gè)標(biāo)簽更新，這種隨機(jī)性在很大程度上影響了算法的穩(wěn)定性。本文提出進(jìn)一步考慮頻數(shù)最多的標(biāo)簽影響力，將節(jié)點(diǎn)i更新為最具影響力的標(biāo)簽，標(biāo)簽影響力由該標(biāo)簽所對(duì)應(yīng)的節(jié)點(diǎn)k-shell值決定。

定義2 給定網(wǎng)絡(luò)G=(V,E)，標(biāo)簽更新的新公式如下：

其中，p(i)表示節(jié)點(diǎn)i的鄰接節(jié)點(diǎn)j中標(biāo)簽頻數(shù)最多的節(jié)點(diǎn)集合。節(jié)點(diǎn)i將更新為頻數(shù)最多的標(biāo)簽中影響力最大的標(biāo)簽，這樣做能降低標(biāo)簽選擇的隨機(jī)性，提高算法的穩(wěn)定性。

2.3 KLPA算法實(shí)現(xiàn)

在分析初始標(biāo)簽分配和標(biāo)簽更新策略基礎(chǔ)上，提出基于節(jié)點(diǎn)影響力的標(biāo)簽傳播算法KLPA，算法如下：

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

輸出：社區(qū)劃分結(jié)果。

1) 計(jì)算種子節(jié)點(diǎn)集M，并給M集中的節(jié)點(diǎn)分配唯一的標(biāo)簽，其標(biāo)簽表示節(jié)點(diǎn)所屬社區(qū)；

2) 置迭代次數(shù)t=1；

3) 隨機(jī)排列網(wǎng)絡(luò)中的節(jié)點(diǎn)形成序列V；

4) 對(duì)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)i，i∈V，標(biāo)簽更新規(guī)則如下：

5) 如果節(jié)點(diǎn)i的鄰接節(jié)點(diǎn)中頻數(shù)最多的標(biāo)簽有多個(gè)，根據(jù)式(3)計(jì)算頻數(shù)相同的標(biāo)簽影響力，選擇影響力更大的標(biāo)簽更新該節(jié)點(diǎn)。若標(biāo)簽的影響力相同，則隨機(jī)選擇一個(gè)標(biāo)簽更新。

6) 如果每個(gè)節(jié)點(diǎn)的標(biāo)簽不再變化，則停止算法，具有相同標(biāo)簽的節(jié)點(diǎn)歸為同一個(gè)社區(qū)。否則，置t=t+1，且返回步驟(3)。

2.4 KLPA算法復(fù)雜度分析

假設(shè)網(wǎng)絡(luò)中有n個(gè)節(jié)點(diǎn)，m條邊，則KLPA算法時(shí)間復(fù)雜度分析如下：

1) 計(jì)算網(wǎng)絡(luò)中節(jié)點(diǎn)的k-shell值，時(shí)間復(fù)雜度為O(n)；

2) 種子節(jié)點(diǎn)集的標(biāo)簽初始化，時(shí)間復(fù)雜度為O(n)；

3) 網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)i，更新節(jié)點(diǎn)標(biāo)簽的時(shí)間復(fù)雜度為O(di)，因此迭代一次所需的時(shí)間復(fù)雜度為O(ndi)。

由上述分析可得，KLPA算法的時(shí)間復(fù)雜度為O(n+n+ndi)，與網(wǎng)絡(luò)規(guī)模成線性關(guān)系。

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

為了測(cè)試本文改進(jìn)算法的有效性，本節(jié)將KLPA算法與LPA算法、LPA-E算法進(jìn)行比較，并且選取3個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)詳細(xì)信息如表1所示。

表1 社會(huì)網(wǎng)絡(luò)的基本數(shù)據(jù)信息

3.1 實(shí)驗(yàn)評(píng)價(jià)方法

1) 模塊度[2]。Newman等提出的模塊度是一個(gè)可以衡量網(wǎng)絡(luò)社區(qū)劃分質(zhì)量?jī)?yōu)劣的指標(biāo)，其表達(dá)式如下：

2) 準(zhǔn)確率。對(duì)于已知社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)，準(zhǔn)確率可以衡量社區(qū)劃分結(jié)果中正確的節(jié)點(diǎn)占所有節(jié)點(diǎn)的比率。

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1 實(shí)驗(yàn)1

本實(shí)驗(yàn)在Karate、Dolphins網(wǎng)絡(luò)中運(yùn)行KLPA算法、LPA算法、LPA-E算法各100次，計(jì)算社區(qū)劃分結(jié)果的準(zhǔn)確率、模塊度以及模塊度方差值。模塊度可以客觀地評(píng)價(jià)網(wǎng)絡(luò)社區(qū)劃分的質(zhì)量，模塊度方差值的大小可以說明社區(qū)劃分結(jié)構(gòu)的波動(dòng)大小。因此采用模塊度方差值估計(jì)社區(qū)結(jié)構(gòu)的波動(dòng)大小，波動(dòng)越小則說明算法穩(wěn)定性越好。實(shí)驗(yàn)結(jié)果如表2、表3所示。在這兩個(gè)網(wǎng)絡(luò)中運(yùn)行KLPA算法，根據(jù)公式(1)計(jì)算得Karate、Dolphins網(wǎng)絡(luò)的種子節(jié)點(diǎn)集分別為Karate(M)=22，Dolphins(M)=36，因此在標(biāo)簽初始化時(shí)，只給種子節(jié)點(diǎn)集M中的節(jié)點(diǎn)分配不同的標(biāo)簽。

表2 Karate、Dolphins網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果準(zhǔn)確率比較 %

表3 Karate、Dolphins網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果模塊度值比較

由表2中可以看出，在Karate、Dolphins網(wǎng)絡(luò)上，通過與已知的社區(qū)劃分結(jié)果相比，KLPA算法的準(zhǔn)確率均高于LPA-E、LPA算法，這說明KLPA算法能以較高的準(zhǔn)確率發(fā)現(xiàn)真實(shí)的社區(qū)結(jié)構(gòu)，表明了KLPA算法能有效地檢測(cè)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。

由表3可以看出，在兩個(gè)真實(shí)網(wǎng)絡(luò)中KLPA算法的模塊度平均值均高于LPA-E、LPA算法，表明KLPA算法檢測(cè)的社區(qū)質(zhì)量有所提高；同時(shí)KLPA算法模塊度的方差值也較小，由此說明KLPA算法的劃分結(jié)果相對(duì)穩(wěn)定。

3.2.2 實(shí)驗(yàn)2

本實(shí)驗(yàn)在較大的數(shù)據(jù)集Cond-mat網(wǎng)絡(luò)上運(yùn)行KLPA算法、LPA算法、LPA-E算法各100次，驗(yàn)證KLPA算法是否可以有效的檢測(cè)社區(qū)結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果如表4所示。在Cond-mat網(wǎng)絡(luò)上運(yùn)行KLPA算法，根據(jù)式(1)計(jì)算得該網(wǎng)絡(luò)的種子節(jié)點(diǎn)集M=4 986。因此在標(biāo)簽初始化時(shí)，只給種子節(jié)點(diǎn)集M中的節(jié)點(diǎn)分配不同的標(biāo)簽。

表4 Cond-mat網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果模塊度值比較

由表4可以看出：相比LPA算法、LPA-E算法，KLPA算法所得的社區(qū)劃分結(jié)果的模塊度平均值略低于LPA-E算法，但模塊度的方差值略高于LPA-E算法，由此說明KLPA算法能夠在大型網(wǎng)絡(luò)上檢測(cè)到社區(qū)結(jié)構(gòu)，且算法的穩(wěn)定性好。

表5 Cond-mat網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果迭代次數(shù)比較

表5記錄了3種算法在Cond-mat網(wǎng)絡(luò)中運(yùn)行的迭代次數(shù)。比較結(jié)果可以看出，相比于LPA、LPA-E算法，KLPA算法的迭代次數(shù)大約減少了一半，由此說明KLPA算法的執(zhí)行效率更高。這是由于本文通過標(biāo)簽初始化和標(biāo)簽更新策略兩個(gè)方面改善了算法的隨機(jī)性，從而減少了算法的迭代次數(shù)，使得算法的執(zhí)行效率更高。

4 結(jié)束語

本文考慮了網(wǎng)絡(luò)中節(jié)點(diǎn)影響力的差異性對(duì)標(biāo)簽傳播的影響，提出基于節(jié)點(diǎn)影響力的標(biāo)簽傳播社區(qū)檢測(cè)算法KLPA。該算法借鑒k-shell分解方法衡量節(jié)點(diǎn)的影響力，通過計(jì)算節(jié)點(diǎn)k-shell的平均值K，選取節(jié)點(diǎn)k-shell值大于平均值K的節(jié)點(diǎn)作為種子節(jié)點(diǎn)集，標(biāo)簽初始化時(shí)只給種子節(jié)點(diǎn)分配不同的標(biāo)簽。在標(biāo)簽選擇過程中，考慮節(jié)點(diǎn)的鄰接節(jié)點(diǎn)中頻數(shù)最多的標(biāo)簽影響力，將該節(jié)點(diǎn)更新為頻數(shù)最多的標(biāo)簽中影響力最大的標(biāo)簽。通過實(shí)驗(yàn)證明了KLPA算法不僅具有線性時(shí)間復(fù)雜度，減少了隨機(jī)性，提高了算法的穩(wěn)定性，而且減少了算法的迭代次數(shù)，社區(qū)模塊度的值也有所提高。

KLPA算法在選擇種子節(jié)點(diǎn)時(shí)，以節(jié)點(diǎn)k-shell值的平均值作為閾值，沒有考慮算法對(duì)該閾值參數(shù)的值是否敏感，下一步將分析不同的節(jié)點(diǎn)影響力度量方法對(duì)標(biāo)簽傳播算法的影響。利用更加優(yōu)良的節(jié)點(diǎn)影響力度量方法選取網(wǎng)絡(luò)的種子節(jié)點(diǎn)，改進(jìn)標(biāo)簽傳播算法是未來研究的重點(diǎn)。