馬 秀，冀慶斌

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

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

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

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

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

1 相關工作

1.1 標簽傳播算法的隨機性問題

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

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

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

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

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

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

2 基于節(jié)點影響力的標簽傳播社區(qū)檢測算法

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

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

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

M={i|ki>K}

(1)

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

2.2 節(jié)點標簽更新策略

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

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

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

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

2.3 KLPA算法實現(xiàn)

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

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

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

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

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

3) 隨機排列網(wǎng)絡中的節(jié)點形成序列V；

4) 對網(wǎng)絡中每個節(jié)點i，i∈V，標簽更新規(guī)則如下：

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

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

2.4 KLPA算法復雜度分析

假設網(wǎng)絡中有n個節(jié)點，m條邊，則KLPA算法時間復雜度分析如下：

1) 計算網(wǎng)絡中節(jié)點的k-shell值，時間復雜度為O(n)；

2) 種子節(jié)點集的標簽初始化，時間復雜度為O(n)；

3) 網(wǎng)絡中每個節(jié)點i，更新節(jié)點標簽的時間復雜度為O(di)，因此迭代一次所需的時間復雜度為O(ndi)。

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

3 實驗

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

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

3.1 實驗評價方法

1) 模塊度[2]。Newman等提出的模塊度是一個可以衡量網(wǎng)絡社區(qū)劃分質(zhì)量優(yōu)劣的指標，其表達式如下：

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

3.2 實驗結果與分析

3.2.1 實驗1

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

表2 Karate、Dolphins網(wǎng)絡實驗結果準確率比較 %

表3 Karate、Dolphins網(wǎng)絡實驗結果模塊度值比較

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

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

3.2.2 實驗2

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

表4 Cond-mat網(wǎng)絡實驗結果模塊度值比較

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

表5 Cond-mat網(wǎng)絡實驗結果迭代次數(shù)比較

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

4 結束語

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

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