融合K-shell和標簽熵的重疊社區(qū)發(fā)現(xiàn)算法

陳 晶，劉江川，魏娜娜*

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

0 引言

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

K

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

K

-shell 和標簽熵的特性，具有較低的時間復(fù)雜度和穩(wěn)定的社區(qū)發(fā)現(xiàn)結(jié)果。本文的主要工作如下：1）提出了針對核心層節(jié)點賦標簽的思想。該思想基于

K

-shell 算法對網(wǎng)絡(luò)進行初始化處理，并針對網(wǎng)絡(luò)中

k

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

2）對網(wǎng)絡(luò)中所有節(jié)點計算其標簽熵，并按照標簽熵的升序異步進行標簽傳播，增強了標簽傳播時的穩(wěn)定性。

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

1 相關(guān)工作

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

Q

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

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

重疊社區(qū)發(fā)現(xiàn)CPM（Clique Percolation Method）由Palla等提出，其核心是通過尋找極大完全子圖進行重疊社區(qū)發(fā)現(xiàn)。Gregory在RAK 算法的基礎(chǔ)上提出了重疊社區(qū)發(fā)現(xiàn)算法（Community Overlap PRopagation Algorithm，COPRA），該算法通過引入?yún)?shù)

v

，使得每個節(jié)點最多可以隸屬于

v

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

k

個影響力最小的重疊節(jié)點來識別重疊社區(qū)。

2 本文算法

2.1 相關(guān)技術(shù)

COPRA 定義了一個參數(shù)

v

，規(guī)定社區(qū)內(nèi)節(jié)點最多隸屬于

v

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

c

，

b

)。其中，

b

是歸屬系數(shù)，

c

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

其中：

b

(

c

，

y

)表示上一次迭代后

x

節(jié)點的鄰居節(jié)點的標簽信息；

N

(

x

)為節(jié)點

x

的鄰居節(jié)點集。

K

-shell 算法是由Kitsak 等提出的

k

核分解法，其核心思想是對復(fù)雜網(wǎng)絡(luò)進行粗粒度劃分，從而找出重要性高的節(jié)點。該算法的前提條件是默認圖中至少存在度為1 的節(jié)點。經(jīng)過

k

核分解后，對應(yīng)度為

k

時被刪除的節(jié)點記為

K

-shell。該算法將網(wǎng)絡(luò)進行了層次劃分，從全局來看，把網(wǎng)絡(luò)劃分為1-shell 層到

K

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

K

max-shell 層為網(wǎng)絡(luò)中影響力最大的節(jié)點集。

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

2.2 標簽初始化階段

重疊社區(qū)發(fā)現(xiàn)算法的初始化過程大多是對網(wǎng)絡(luò)中所有節(jié)點進行賦予標簽操作，隨著網(wǎng)絡(luò)規(guī)模的增加，運行時間會迅速增長。因此，本文提出的OCKELP 采用了針對網(wǎng)絡(luò)進行

K

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

其中：

CoreNodes

表示核心層節(jié)點，

node

(

k

=max(

k

))表示取

k

值最大的節(jié)點作為核心層節(jié)點。在大多數(shù)網(wǎng)絡(luò)中，大部分節(jié)點屬于影響力較小的節(jié)點，而少數(shù)節(jié)點是影響力較大的節(jié)點，利用

K

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

2.3 標簽更新順序

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

圖1 兩個社區(qū)的強關(guān)聯(lián)社區(qū)圖Fig.1 Strongly connected community graph of two communities

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

t

時刻節(jié)點

v

更新時與

t

時刻未更新的鄰居節(jié)點標簽和

t

時刻已更新的鄰居節(jié)點標簽有關(guān)，如式（4）所示：

2.4 標簽選擇過程

大多數(shù)標簽傳播算法在進行標簽選擇時，未考慮節(jié)點間的相似度和節(jié)點在網(wǎng)絡(luò)中的影響力，為此，本文融合Jaccard相似度和

K

-shell 算法的

k

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

k

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

利用

k

值作為系數(shù)去放大節(jié)點間的相似度，將節(jié)點的層次信息與局部信息融合，構(gòu)成綜合影響力

CompreInf

，將

CompreInf

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

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

其中：

C

表示

A

節(jié)點所擁有的社區(qū)標簽集合。

3 OCKELP實現(xiàn)

3.1 算法基本步驟

OCKELP 的具體步驟如下：

步驟1 對網(wǎng)絡(luò)進行初始化，利用

K

-shell 算法得到

k

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

c

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

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

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

v

的標簽。如果該節(jié)點所有標簽的從屬系數(shù)均小于1/

v

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

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

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

3.2 算法偽代碼

OCKELP 由網(wǎng)絡(luò)初始化和標簽傳播兩部分組成，算法偽代碼如下：

算法1 網(wǎng)絡(luò)初始化算法。

輸入 社區(qū)網(wǎng)絡(luò)圖

G

（

V，E

）。輸出 初始化后的社區(qū)網(wǎng)絡(luò)圖

init_G

（

V，E

），部分節(jié)點具有標簽。

根據(jù)算法1 可知，首先遍歷網(wǎng)絡(luò)中的節(jié)點并求出相應(yīng)的度值，其次根據(jù)

K

-shell 算法，得到每個節(jié)點對應(yīng)的

k

值，找出擁有最大

k

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

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

算法2 標簽傳播。

輸入 初始化后的社區(qū)網(wǎng)絡(luò)圖

init_G

（

V，E

），參數(shù)

v

。輸出 社區(qū)信息

communities

。

3.3 算法時間復(fù)雜度分析

假設(shè)

n

代表節(jié)點數(shù)，

m

為邊數(shù)，

v

表示節(jié)點最多可以隸屬的社區(qū)個數(shù)。初始化算法主要是由

K

-shell 算法以及遍歷網(wǎng)絡(luò)節(jié)點找出擁有最大

k

值的節(jié)點賦予標簽組成。初始化算法第2）～6）行以及第8）～12）行都對網(wǎng)絡(luò)中

n

個節(jié)點進行了遍歷，這兩部分的時間復(fù)雜度都為

O

(

n

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

O

(

n

)。

4 實驗與結(jié)果分析

4.1 評價指標

在真實網(wǎng)絡(luò)數(shù)據(jù)集上，實驗采用重疊社區(qū)模塊度EQ（ExtendQ）作為評價指標；在人工網(wǎng)絡(luò)數(shù)據(jù)集上，采取重疊社區(qū)歸一化互信息（Normalized Mutual Information，NMI）值作為評價指標。

1）重疊模塊度EQ。

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

其中：

m

為社區(qū)中的總邊數(shù)；

O

、

O

分別代表節(jié)點

v

和節(jié)點

w

屬于的社區(qū)數(shù)量；

k

、

k

分別代表節(jié)點

v

和節(jié)點

w

的度。當每個節(jié)點最多只屬于一個社區(qū)時，

EQ

等價于

Q

，當所有節(jié)點都屬于同一個社區(qū)時，

EQ

=0。

2）重疊社區(qū)的歸一化互信息NMI。

為了檢測重疊社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量，Lancichinetti 等提出了識別重疊社區(qū)發(fā)現(xiàn)與真實社區(qū)匹配程度的指標NMI，如式（9）所示：

其中：

X

代表真實社區(qū)；

Y

代表經(jīng)過社區(qū)發(fā)現(xiàn)算法后的社區(qū)；

H

(

X

|

Y

)為歸一化條件熵。

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

4.2 實驗數(shù)據(jù)集

真實網(wǎng)絡(luò)數(shù)據(jù)集來源于斯坦福大學的大型網(wǎng)絡(luò)數(shù)據(jù)集和Newman 教授的個人數(shù)據(jù)網(wǎng)站。表1 展示出真實網(wǎng)絡(luò)數(shù)據(jù)集的相關(guān)信息。舉例說明：Karate 數(shù)據(jù)集提供了TXT 文檔和GML 文檔，其中TXT 文檔提供節(jié)點集和邊集；GML 文檔可利用gephi 將數(shù)據(jù)集可視化，展示出真實社區(qū)劃分的結(jié)果。

表1 真實網(wǎng)絡(luò)數(shù)據(jù)集Tab 1 Real network datasets

Lancichinetti 等提出了LFR 基準網(wǎng)絡(luò)，由于該基準網(wǎng)絡(luò)與現(xiàn)實網(wǎng)絡(luò)極為相似，并且具有真實的社區(qū)劃分結(jié)構(gòu)，因此，本文采用LFR基準網(wǎng)絡(luò)作為人工網(wǎng)絡(luò)數(shù)據(jù)集對OCKELP 進行實驗驗證。LFR基準網(wǎng)絡(luò)的基本參數(shù)描述如表2所示。

表2 LFR基準網(wǎng)絡(luò)參數(shù)描述Tab 2 LFR benchmark network parameter description

利用LFR 生成了4 個人工網(wǎng)絡(luò)數(shù)據(jù)集進行實驗對比，4個人工網(wǎng)絡(luò)數(shù)據(jù)集具體參數(shù)如表3 所示。

表3 四個LFR基準網(wǎng)絡(luò)參數(shù)Tab 3 Four LFR benchmark network parameters

4.3 實驗結(jié)果分析

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

Karate 數(shù)據(jù)集是空手道俱樂部網(wǎng)絡(luò)，含有34 個節(jié)點和78條邊，該空手道俱樂部真實社區(qū)分布，如表4 所示。

表4 Karate數(shù)據(jù)集網(wǎng)絡(luò)真實劃分Tab 4 Real partition of Karate dataset network

從表4 和圖2 可以發(fā)現(xiàn)，OCKELP 在Karate 上的實驗結(jié)果除了節(jié)點10 歸屬，其他節(jié)點歸屬都與Karate 網(wǎng)絡(luò)真實劃分一致。節(jié)點10 被劃分到了兩個社區(qū)中，其原因是節(jié)點10 在兩個社區(qū)的聯(lián)系都較為緊密，不容易確定其歸屬社區(qū)。

圖2 Karate網(wǎng)絡(luò)實驗結(jié)果Fig.2 Results of Karate network experiment

采用真實網(wǎng)絡(luò)對EQ 值進行驗證，結(jié)果如表5 所示。從表5 可知，OCKELP 在Karate、Polbooks、Internet 數(shù)據(jù)集上，EQ值都優(yōu)于其他算法；在Dolphins 網(wǎng)絡(luò)中僅次于OMKLP 算法，并且相差很?。辉贔ootball 網(wǎng)絡(luò)和Email 網(wǎng)絡(luò)中EQ 值僅次于MNMF 算法。原因是：由于數(shù)據(jù)集規(guī)模較小，存在一些聯(lián)系過于密切的節(jié)點，導致標簽選擇時，影響力因素的作用被削弱。在規(guī)模較大的網(wǎng)絡(luò)中，OCKELP 表現(xiàn)最優(yōu)，說明了OCKELP 在標簽選擇時，通過增加影響力因素可以提高社區(qū)發(fā)現(xiàn)結(jié)果的準確性。綜上所述，OCKELP 在大多數(shù)真實網(wǎng)絡(luò)數(shù)據(jù)集中能夠獲得準確的社區(qū)劃分結(jié)果，獲得更高的EQ 值。

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

在人工網(wǎng)絡(luò)數(shù)據(jù)集中，由于MNMF、NNSED算法無法識別非連通圖，所以O(shè)CKELP僅與COPRA、OMKLP、SLPA進行比較。

在R1 網(wǎng)絡(luò)中，驗證了重疊節(jié)點隸屬社區(qū)的數(shù)量對NMI值的影響。此時

mu

值為0.1，R1 網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)比較清晰。如圖3 所示，OMKLP 算法表現(xiàn)整體較為平穩(wěn)，

om

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

om

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

om

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

om

取值中都有著較好的結(jié)果。雖然隨著

om

值的增大，出現(xiàn)了NMI 值下降的情況，但總體趨勢平穩(wěn)，沒有出現(xiàn)由于重疊節(jié)點所隸屬社區(qū)數(shù)的增多而導致NMI 值快速下降的情況。

圖3 R1網(wǎng)絡(luò)中的NMI值（mu=0.1）Fig.3 NMI values in R1 network（mu=0.1）

R2 網(wǎng)絡(luò)除了

mu

值改變外，其余參數(shù)不變。

mu

值為0.3，由于

mu

值增加使得R2 網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)變得較為模糊，所以在R2 網(wǎng)絡(luò)的實驗中，社區(qū)發(fā)現(xiàn)結(jié)果的NMI 值整體呈現(xiàn)下降趨勢，如圖4 所示。OMKLP、COPRA 隨著

om

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

om

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

圖4 R2網(wǎng)絡(luò)中的NMI值（mu=0.3）Fig.4 NMI values in R2 network（mu=0.3）

在R3 網(wǎng)絡(luò)中，主要驗證了

mu

值對NMI 值的影響。

mu

值是體現(xiàn)社區(qū)結(jié)構(gòu)清晰程度的參數(shù)，隨著

mu

值的增加，社區(qū)結(jié)構(gòu)逐漸弱化，意味著邊緣節(jié)點和社區(qū)內(nèi)部節(jié)點的標簽熵影響力變強。如圖5 所示，OMKLP、COPRA、SLPA 在

mu

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

mu

=0.5 時，幾乎觀察不到社區(qū)結(jié)構(gòu)，算法的穩(wěn)定性較差。OCKELP 的NMI 值要優(yōu)于其他三個算法，雖然隨著

mu

值增加有所下降，但是下降速率很慢，說明OCKELP 具有良好的穩(wěn)定性，可有效識別模糊社區(qū)結(jié)構(gòu)。

圖5 R3網(wǎng)絡(luò)中的NMI值（on=100）Fig.5 NMI values in R3 network（on=100）

在R4 網(wǎng)絡(luò)中，除了重疊節(jié)點數(shù)量從100 變?yōu)?00 以外，其他參數(shù)與R3 網(wǎng)絡(luò)保持一致，其原因是為了驗證重疊節(jié)點數(shù)量對社區(qū)發(fā)現(xiàn)結(jié)果的影響。如圖6 所示，對比R3 網(wǎng)絡(luò)，所有算法都受到了

on

的影響，NMI 值整體上呈現(xiàn)降低的趨勢，說明了重疊節(jié)點數(shù)量的增加會影響重疊社區(qū)發(fā)現(xiàn)的質(zhì)量。SLPA、COPRA 在

on

=200，

mu

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

on

對OMKLP 算法影響不大，與R3 網(wǎng)絡(luò)中整體趨勢相近。OCKELP 在不同的

mu

值下相較于其他三個算法具有最優(yōu)的NMI 值，

on

對OCKELP 的影響不明顯，整體趨勢較為平穩(wěn)。

圖6 R4網(wǎng)絡(luò)中的NMI值（on=200）Fig.6 NMI values in R4 network（on=200）

綜上可知，在真實網(wǎng)絡(luò)數(shù)據(jù)集中，OCKELP 在大多數(shù)網(wǎng)絡(luò)中重疊社區(qū)發(fā)現(xiàn)結(jié)果的EQ 值最優(yōu)。在人工合成數(shù)據(jù)集中，

om

與

on

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

mu

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

5 結(jié)語

本文提出了融合

K

-shell 和標簽熵的標簽傳播重疊社區(qū)發(fā)現(xiàn)算法OCKELP。首先，利用

K

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

在未來的工作中將會進行如下的深入研究：1）將本文算法拓展為動態(tài)社區(qū)發(fā)現(xiàn)算法，從而可以對動態(tài)社區(qū)進行社區(qū)發(fā)現(xiàn)；2）將本文算法拓展到有向有權(quán)圖中。