融合K-shell和標簽熵的重疊社區發現算法

陳 晶，劉江川，魏娜娜*

（1.燕山大學信息科學與工程學院，河北秦皇島 066004；2.河北省計算機虛擬技術與系統集成重點實驗室（燕山大學），河北秦皇島 066004；3.河北省軟件工程重點實驗室（燕山大學），河北秦皇島 066004）

0 引言

隨著對復雜網絡社區發現算法的深入研究，社區發現算法為信息推薦、信息傳播、精準營銷等方面的應用提供了基礎。社區發現算法分為靜態算法和動態算法，其中靜態算法包括重疊社區發現和非重疊社區發現兩類。與非重疊社區發現相比，重疊社區發現更符合現實復雜網絡，但存在著時間復雜度和空間復雜度較高的問題。為此，如何降低社區發現算法的時間復雜度并提高社區發現結果的穩定性研究已逐步引起了諸多學者的關注。為此，本文提出了一種基于標簽傳播思想的重疊社區發現算法OCKELP（Overlapping Community detection algorithm combining

K

-shell and label Entropy in Label Propagation），該算法融合了

K

-shell 和標簽熵的特性，具有較低的時間復雜度和穩定的社區發現結果。本文的主要工作如下：1）提出了針對核心層節點賦標簽的思想。該思想基于

K

-shell 算法對網絡進行初始化處理，并針對網絡中

k

值最高的節點賦予標簽。通過對核心層節點賦予標簽的過程，可以將網絡進行初步的劃分，減少網絡初始化時間。

2）對網絡中所有節點計算其標簽熵，并按照標簽熵的升序異步進行標簽傳播，增強了標簽傳播時的穩定性。

3）針對標簽傳播過程，引入了綜合影響力，考慮節點間局部關系和節點所屬的全局關系，提高了標簽傳播結果的準確性。

1 相關工作

針對大規模復雜網絡進行社區發現有助于分析群體特征，因此，許多學者從不同的角度對社區發現問題展開了研究。社區發現的概念由Newman 等提出，將社區結構定義為社區內部節點連接緊密，社區間節點連接稀疏。由于復雜網絡的規模巨大，為了簡化和分析網絡結構，將圖論引入復雜網絡。把社交網絡個體以及個體間的關系抽象為圖中的節點和邊。2002 年，Girvan 等提出了基于圖分割的GN（Girvan-Newman）算法，該算法提出了邊介數的概念，對網絡中所有的邊計算其邊介數，并依次刪除邊介數最高的邊，直到社區不可分割。楊立文提出了一種改進的GN 算法，采用粗粒度與細粒度并行的方法計算邊介數。Whites 等使用譜技術將組合圖劃分問題簡化為幾何向量空間劃分問題，利用拉普拉斯矩陣得到特征向量，對特征向量進行聚類使得

Q

值最大化，從而得到社區劃分。Yang 等提出了基于層次聚類的JGN（the improved Jaccard similarity coefficient in GN）算法，通過對所有節點計算改進的Jaccard 相似系數，并刪除擁有最小相似系數的節點間的連邊而得到社區結構。

標簽傳播算法是一種半監督學習方法，由Zhu 等提出。隨后，Raghavan 等提出了RAK（Raghavan Albert Kumara）算法，將其應用到非重疊社區發現中，該算法具有線性時間復雜度，但RAK 算法的隨機性較強、魯棒性較弱。Sun 等提出了CenLP（Centrality-based Label Propagation）算法，該算法通過計算每個節點的局部密度和高密度鄰居的相似度，改進了節點更新順序和相似關系。Xie 等提出了LabelRank 算法，該算法通過引入4 個算子使得LPA（Label Propagation Algorithm）的穩定性得到了提升。Blondel 等提出了Louvain 算法，該算法使用模塊度優化的方式為節點劃分社區。薛青提出了一種基于修剪策略的改進Louvain 算法PRULOU（improvement of louvain algorithm based on pruning in complex networks），該算法利用修剪策略消除了Louvain 算法中的社區劃分震蕩和模塊度震蕩問題。Waltman 等提出了SLM（Smart Local Moving）算法，通過分割社區，將節點集從一個社區移動到另一個社區，不斷搜索模塊度增益的可能性，從而進行大規模網絡社區發現。

重疊社區發現CPM（Clique Percolation Method）由Palla等提出，其核心是通過尋找極大完全子圖進行重疊社區發現。Gregory在RAK 算法的基礎上提出了重疊社區發現算法（Community Overlap PRopagation Algorithm，COPRA），該算法通過引入參數

v

，使得每個節點最多可以隸屬于

v

個社區。Wu等提出了平衡多標簽傳播算法（Balanced Multi-Label Propagation Algorithm，BMLPA），引入了平衡歸屬系數，使得節點理論上可以屬于無限個社區。沈海燕等在COPRA 的基礎上借鑒了CPM 算法的極大子團方式將標簽初始化過程的時間縮減，并在標簽傳播過程中引入了影響力因素減少了算法的隨機性。鄧琨等提出了一種基于多核心標簽傳播的重疊社區識別（Overlapping community detection in complex networks based on Multi Kernel Label Propagation，OMKLP）方法，采用多個核心節點的方式進行標簽傳播。由于不需要預先設置參數，增強了算法的穩定性。Lu 等提出了LPANNI（Label Propagation Algorithm with Neighbor Node Influence），該算法加入了鄰居節點影響力，并按照節點重要性升序更新節點標簽。Cheng 等提出了基于局部擴展的局部鄰域信息重疊社區識別算法（local-expansion-based Overlapping-Community detection algorithm using Local-Neighborhood information，OCLN）來大規模復雜網絡，該算法在社區擴展時僅考慮了社區中的關鍵鄰居。Shi 等提出了COLBN（overlapping community discovery algorithm based on label propagation），根據參考節點劃分初始社區，選擇重疊節點中的參考節點劃分重疊社區。Tang 等在SLPA（Speakerlistener Label Propagation Algorithm）的基礎上提出了基于局部和全局屬性衡量節點影響的度量方法，通過刪除

k

個影響力最小的重疊節點來識別重疊社區。

2 本文算法

2.1 相關技術

COPRA 定義了一個參數

v

，規定社區內節點最多隸屬于

v

個社區，并為每個節點在初始時刻定義一組標簽(

c

，

b

)。其中，

b

是歸屬系數，

c

為社區標簽，每個節點可以擁有多組標簽，并且該節點所擁有的所有標簽的歸屬系數和為1，歸屬系數定義如式（1）所示：

其中：

b

(

c

，

y

)表示上一次迭代后

x

節點的鄰居節點的標簽信息；

N

(

x

)為節點

x

的鄰居節點集。

K

-shell 算法是由Kitsak 等提出的

k

核分解法，其核心思想是對復雜網絡進行粗粒度劃分，從而找出重要性高的節點。該算法的前提條件是默認圖中至少存在度為1 的節點。經過

k

核分解后，對應度為

k

時被刪除的節點記為

K

-shell。該算法將網絡進行了層次劃分，從全局來看，把網絡劃分為1-shell 層到

K

max-shell 層，其中1-shell 層為影響力最小的節點集，

K

max-shell 層為網絡中影響力最大的節點集。

為了解決標簽傳播算法穩定性差的問題，Zhao 等基于信息論提出了標簽熵的概念，并將標簽傳播順序按照標簽熵從小到大的順序傳播，提高了算法的穩定性。標簽熵的定義如式（2）所示：

2.2 標簽初始化階段

重疊社區發現算法的初始化過程大多是對網絡中所有節點進行賦予標簽操作，隨著網絡規模的增加，運行時間會迅速增長。因此，本文提出的OCKELP 采用了針對網絡進行

K

-shell 分解處理，得到核心層節點的預處理方式。其中，核心層節點的定義如式（3）所示：

其中：

CoreNodes

表示核心層節點，

node

(

k

=max(

k

))表示取

k

值最大的節點作為核心層節點。在大多數網絡中，大部分節點屬于影響力較小的節點，而少數節點是影響力較大的節點，利用

K

-shell 算法得到的核心層節點具有較大的影響力。對核心層節點賦予標簽，經過少數幾次迭代后，就可獲得社區劃分的初始結果和較高的時間效率。

2.3 標簽更新順序

標簽傳播重疊社區發現算法在標簽更新時采取的是隨機更新策略，其結果會導致社區發現結果的隨機性大。相關研究表明，標簽在節點中更新順序會極大影響結果的隨機性，所以本文引入了標簽熵，來解決標簽傳播算法穩定性差的問題。

圖1 兩個社區的強關聯社區圖Fig.1 Strongly connected community graph of two communities

此外，為了避免標簽震蕩，本文算法采用異步更新規則。即

t

時刻節點

v

更新時與

t

時刻未更新的鄰居節點標簽和

t

時刻已更新的鄰居節點標簽有關，如式（4）所示：

2.4 標簽選擇過程

大多數標簽傳播算法在進行標簽選擇時，未考慮節點間的相似度和節點在網絡中的影響力，為此，本文融合Jaccard相似度和

K

-shell 算法的

k

值，綜合考慮節點間的相似度和節點所屬社區層次的影響，將其加入標簽更新中，使得在進行標簽選擇時，考慮了節點間相似性和節點本身的影響力，降低了隨機性，提高了社區發現結果的穩定性和準確性。將Jaccard 相似度以及層次信息

k

值融合為綜合影響力，如式（5）所示：

利用

k

值作為系數去放大節點間的相似度，將節點的層次信息與局部信息融合，構成綜合影響力

CompreInf

，將

CompreInf

值引入到標簽更新中，如式（6）所示：

需要注意的是，當標簽更新選擇結束后，還需要對節點所擁有的從屬系數集進行歸一化，如式（7）所示：

其中：

C

表示

A

節點所擁有的社區標簽集合。

3 OCKELP實現

3.1 算法基本步驟

OCKELP 的具體步驟如下：

步驟1 對網絡進行初始化，利用

K

-shell 算法得到

k

值最高的節點集，賦予這些節點不同的標簽對(

c

，1)，其中1 為初始從屬系數。

步驟2 初始化各個節點的標簽熵，并按升序排序。

步驟3 采用異步更新的方式，根據式（5）計算出節點間的綜合影響力，根據式（6）得到節點所含有的標簽的從屬系數，并利用式（7）進行歸一化。對節點計算其標簽熵，刪除從屬系數小于1/

v

的標簽。如果該節點所有標簽的從屬系數均小于1/

v

，則選擇從屬系數最大的標簽，當出現最大值有多個時，執行步驟4，再利用式（7）進行歸一化。

步驟4 從多個候選標簽中選擇一個作為該節點的標簽。

步驟5 算法滿足終止條件時結束，并將標簽相同的節點合并成一個社區；否則，繼續執行步驟3 和步驟4。

3.2 算法偽代碼

OCKELP 由網絡初始化和標簽傳播兩部分組成，算法偽代碼如下：

算法1 網絡初始化算法。

輸入 社區網絡圖

G

（

V，E

）。輸出 初始化后的社區網絡圖

init_G

（

V，E

），部分節點具有標簽。

根據算法1 可知，首先遍歷網絡中的節點并求出相應的度值，其次根據

K

-shell 算法，得到每個節點對應的

k

值，找出擁有最大

k

值的節點即核心層節點賦予其標簽。由于僅對核心層節點賦予標簽，可以降低對所有節點賦予標簽的時間，提高了標簽傳播階段的效率。

第二部分是標簽傳播，基于算法1 對初始化后的社區進行標簽傳播，偽代碼描述如下所示。

算法2 標簽傳播。

輸入 初始化后的社區網絡圖

init_G

（

V，E

），參數

v

。輸出 社區信息

communities

。

3.3 算法時間復雜度分析

假設

n

代表節點數，

m

為邊數，

v

表示節點最多可以隸屬的社區個數。初始化算法主要是由

K

-shell 算法以及遍歷網絡節點找出擁有最大

k

值的節點賦予標簽組成。初始化算法第2）～6）行以及第8）～12）行都對網絡中

n

個節點進行了遍歷，這兩部分的時間復雜度都為

O

(

n

)，所以初始化算法整體的時間復雜度也為

O

(

n

)。

4 實驗與結果分析

4.1 評價指標

在真實網絡數據集上，實驗采用重疊社區模塊度EQ（ExtendQ）作為評價指標；在人工網絡數據集上，采取重疊社區歸一化互信息（Normalized Mutual Information，NMI）值作為評價指標。

1）重疊模塊度EQ。

Nicosia 等和Shen 等分別提出了重疊社區模塊度Qov 和EQ，EQ 描述如式（8）所示：

其中：

m

為社區中的總邊數；

O

、

O

分別代表節點

v

和節點

w

屬于的社區數量；

k

、

k

分別代表節點

v

和節點

w

的度。當每個節點最多只屬于一個社區時，

EQ

等價于

Q

，當所有節點都屬于同一個社區時，

EQ

=0。

2）重疊社區的歸一化互信息NMI。

為了檢測重疊社區發現結果的質量，Lancichinetti 等提出了識別重疊社區發現與真實社區匹配程度的指標NMI，如式（9）所示：

其中：

X

代表真實社區；

Y

代表經過社區發現算法后的社區；

H

(

X

|

Y

)為歸一化條件熵。

McDaid 等認為Lancichinetti 等提出的NMI 在極端情況下表現不理想，因此對NMI 定義進行了改進，定義如式（10）所示：

4.2 實驗數據集

真實網絡數據集來源于斯坦福大學的大型網絡數據集和Newman 教授的個人數據網站。表1 展示出真實網絡數據集的相關信息。舉例說明：Karate 數據集提供了TXT 文檔和GML 文檔，其中TXT 文檔提供節點集和邊集；GML 文檔可利用gephi 將數據集可視化，展示出真實社區劃分的結果。

表1 真實網絡數據集Tab 1 Real network datasets

Lancichinetti 等提出了LFR 基準網絡，由于該基準網絡與現實網絡極為相似，并且具有真實的社區劃分結構，因此，本文采用LFR基準網絡作為人工網絡數據集對OCKELP 進行實驗驗證。LFR基準網絡的基本參數描述如表2所示。

表2 LFR基準網絡參數描述Tab 2 LFR benchmark network parameter description

利用LFR 生成了4 個人工網絡數據集進行實驗對比，4個人工網絡數據集具體參數如表3 所示。

表3 四個LFR基準網絡參數Tab 3 Four LFR benchmark network parameters

4.3 實驗結果分析

在真實網絡數據集上，將所提出的OCKELP 算法與COPRA、OMKLP、SLPA、MNMF（Modularized Nonnegative Matrix Factorization）、NNSED（Non-Negative Symmetric Encoder-Decoder）進 行 對 比。由 于COPRA 和SLPA 穩定性不好，所以本實驗分別取COPRA、SLPA 運行20次結果的平均值。

Karate 數據集是空手道俱樂部網絡，含有34 個節點和78條邊，該空手道俱樂部真實社區分布，如表4 所示。

表4 Karate數據集網絡真實劃分Tab 4 Real partition of Karate dataset network

從表4 和圖2 可以發現，OCKELP 在Karate 上的實驗結果除了節點10 歸屬，其他節點歸屬都與Karate 網絡真實劃分一致。節點10 被劃分到了兩個社區中，其原因是節點10 在兩個社區的聯系都較為緊密，不容易確定其歸屬社區。

圖2 Karate網絡實驗結果Fig.2 Results of Karate network experiment

采用真實網絡對EQ 值進行驗證，結果如表5 所示。從表5 可知，OCKELP 在Karate、Polbooks、Internet 數據集上，EQ值都優于其他算法；在Dolphins 網絡中僅次于OMKLP 算法，并且相差很小；在Football 網絡和Email 網絡中EQ 值僅次于MNMF 算法。原因是：由于數據集規模較小，存在一些聯系過于密切的節點，導致標簽選擇時，影響力因素的作用被削弱。在規模較大的網絡中，OCKELP 表現最優，說明了OCKELP 在標簽選擇時，通過增加影響力因素可以提高社區發現結果的準確性。綜上所述，OCKELP 在大多數真實網絡數據集中能夠獲得準確的社區劃分結果，獲得更高的EQ 值。

表5 不同算法的EQ值比較結果Tab 5 Comparison results of EQ values of different algorithms

在人工網絡數據集中，由于MNMF、NNSED算法無法識別非連通圖，所以OCKELP僅與COPRA、OMKLP、SLPA進行比較。

在R1 網絡中，驗證了重疊節點隸屬社區的數量對NMI值的影響。此時

mu

值為0.1，R1 網絡的社區結構比較清晰。如圖3 所示，OMKLP 算法表現整體較為平穩，

om

的增加對于其影響不大，但其他算法的識別準確度要低于本文算法OCKELP。SLPA 初始時NMI 值較高，但隨著

om

的增加，NMI下降趨勢較為明顯，穩定性較差。COPRA 的識別準確度較低，穩定性一般。本文算法OCKELP 除了在

om

=4 時NMI 值略低于OMKLP 算法之外，在其他

om

取值中都有著較好的結果。雖然隨著

om

值的增大，出現了NMI 值下降的情況，但總體趨勢平穩，沒有出現由于重疊節點所隸屬社區數的增多而導致NMI 值快速下降的情況。

圖3 R1網絡中的NMI值（mu=0.1）Fig.3 NMI values in R1 network（mu=0.1）

R2 網絡除了

mu

值改變外，其余參數不變。

mu

值為0.3，由于

mu

值增加使得R2 網絡的社區結構變得較為模糊，所以在R2 網絡的實驗中，社區發現結果的NMI 值整體呈現下降趨勢，如圖4 所示。OMKLP、COPRA 隨著

om

值的增加，NMI 值逐漸降低，而SLPA 識別準確度一直較低。OCKELP的識別準確度最優，且隨著

om

值的增加，NMI 值變化不大，保持著較為平穩的趨勢。

圖4 R2網絡中的NMI值（mu=0.3）Fig.4 NMI values in R2 network（mu=0.3）

在R3 網絡中，主要驗證了

mu

值對NMI 值的影響。

mu

值是體現社區結構清晰程度的參數，隨著

mu

值的增加，社區結構逐漸弱化，意味著邊緣節點和社區內部節點的標簽熵影響力變強。如圖5 所示，OMKLP、COPRA、SLPA 在

mu

=0.1 時得到的NMI 值都比較高，但隨著社區結構逐漸模糊，NMI 值下降速率很快，尤其是COPRA、SLPA，在

mu

=0.5 時，幾乎觀察不到社區結構，算法的穩定性較差。OCKELP 的NMI 值要優于其他三個算法，雖然隨著

mu

值增加有所下降，但是下降速率很慢，說明OCKELP 具有良好的穩定性，可有效識別模糊社區結構。

圖5 R3網絡中的NMI值（on=100）Fig.5 NMI values in R3 network（on=100）

在R4 網絡中，除了重疊節點數量從100 變為200 以外，其他參數與R3 網絡保持一致，其原因是為了驗證重疊節點數量對社區發現結果的影響。如圖6 所示，對比R3 網絡，所有算法都受到了

on

的影響，NMI 值整體上呈現降低的趨勢，說明了重疊節點數量的增加會影響重疊社區發現的質量。SLPA、COPRA 在

on

=200，

mu

=0.5 時已無法挖掘出社區的有效信息。

on

對OMKLP 算法影響不大，與R3 網絡中整體趨勢相近。OCKELP 在不同的

mu

值下相較于其他三個算法具有最優的NMI 值，

on

對OCKELP 的影響不明顯，整體趨勢較為平穩。

圖6 R4網絡中的NMI值（on=200）Fig.6 NMI values in R4 network（on=200）

綜上可知，在真實網絡數據集中，OCKELP 在大多數網絡中重疊社區發現結果的EQ 值最優。在人工合成數據集中，

om

與

on

的增加對OCKLEP 算法影響不大。隨著

mu

值的增加，OCKELP 的NMI 值呈現了下降的趨勢，但相較于OMKLP、SLPA、COPRA 下降趨勢不明顯，其主要原因是：標簽傳播算法對于節點間連接緊密程度的敏感性較高，對于社區的清晰程度有著較大的依賴。實驗結果表明，OCKELP 比OMKLP、SLPA、COPRA 有著更好的穩定性，在EQ 和NMI 值上，OCKELP 具有較高的社區劃分質量和穩定的社區劃分結果。

5 結語

本文提出了融合

K

-shell 和標簽熵的標簽傳播重疊社區發現算法OCKELP。首先，利用

K

-shell 算法進行標簽初始化，按照標簽熵從小到大的順序進行標簽更新；其次，在標簽選擇階段提出了綜合影響力，將社區層次信息和節點局部信息融合。在真實網絡數據集和人工網絡數據集上進行了實驗對比，實驗結果證明了OCKELP 的穩定性和有效性。

在未來的工作中將會進行如下的深入研究：1）將本文算法拓展為動態社區發現算法，從而可以對動態社區進行社區發現；2）將本文算法拓展到有向有權圖中。