基于密度峰值的標(biāo)簽傳播算法?

吳衛(wèi)江 王星豪 潘雪玲 鄭藝峰 鄭 猋

（1.中國石油大學(xué)（北京）石油數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室 北京 102249）

（2.中國石油大學(xué)（北京）信息科學(xué)與信息工程學(xué)院 北京 102249）

（3.閩南師范大學(xué)數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室 漳州 363000）

（4.閩南師范大學(xué)計(jì)算機(jī)學(xué)院 漳州 363000）

1 引言

近年來，研究人員提出各種不同的復(fù)雜網(wǎng)絡(luò)的社區(qū)檢測方法［1］。根據(jù)求解策略，分為優(yōu)化方法和啟發(fā)式方法［2］。優(yōu)化方法通過設(shè)定目標(biāo)函數(shù)以迭代獲得最優(yōu)值，其代表：譜算法［3］和模塊化最大化算法［4～5］。啟發(fā)式方法［6］則通過設(shè)置啟發(fā)式規(guī)則來尋找社區(qū)的最優(yōu)劃分。隨著網(wǎng)絡(luò)規(guī)模日益龐大和復(fù)雜，社區(qū)檢測方法應(yīng)具備可伸縮性、適應(yīng)性、健壯性和簡單性等特點(diǎn)。

2007 年，Raghavan 等提出基于標(biāo)簽傳播的快速社區(qū)檢測算法LPA［7］，時(shí)間復(fù)雜度接近線性。不足之處，在更新節(jié)點(diǎn)標(biāo)簽的過程中，結(jié)果存在不確定性和隨機(jī)性。Zheng 等［8］提出一種社區(qū)檢測算法方法，采用改進(jìn)的標(biāo)記傳播和模糊C-均值，對(duì)每個(gè)群落中多樣性較大的頂點(diǎn)的標(biāo)記向量進(jìn)行修正，直至社區(qū)狀態(tài)最終穩(wěn)定。Xu 等［9］提出基于標(biāo)簽傳播的分布式時(shí)間鏈路預(yù)測算法，其受節(jié)點(diǎn)間交互的動(dòng)態(tài)特性控制。當(dāng)標(biāo)簽在相鄰節(jié)點(diǎn)之間傳播時(shí)，基于事件鏈路的權(quán)重進(jìn)行更新，聚合相同源節(jié)點(diǎn)的值，以評(píng)估預(yù)測網(wǎng)絡(luò)中鏈路得分。針對(duì)標(biāo)簽傳播算法在處理大規(guī)模網(wǎng)絡(luò)時(shí)的“monster”社區(qū)問題，BZDA等［10］設(shè)置增長曲線，改進(jìn)標(biāo)簽選擇機(jī)制。

針對(duì)上述問題，本文提出基于密度峰值的標(biāo)簽傳播算法（DPC-RWL）。首先，使用基于密度的社區(qū)檢測方法提取出社區(qū)的核心節(jié)點(diǎn)集。其次，利用相似度函數(shù)為社區(qū)中的每個(gè)節(jié)點(diǎn)賦權(quán)重值以有效解決標(biāo)簽傳播算法的不穩(wěn)定性問題。最后，結(jié)合標(biāo)簽傳播算法思想構(gòu)建目標(biāo)函數(shù)用以劃分社區(qū)。實(shí)驗(yàn)表明，DPC-RWL算法均取得較好實(shí)驗(yàn)效果。

2 相關(guān)知識(shí)

2.1 密度均值聚類算法

聚類的本質(zhì)是按照給定度量將數(shù)據(jù)樣本空間劃分成不同的簇，使得同簇內(nèi)的數(shù)據(jù)樣本具有較高相似性，不同簇間的數(shù)據(jù)樣本具有較大的差異性。密度峰值算法［11］由Alex Rodriguez 等提出，用以尋找被低密度區(qū)域分離的高密度區(qū)域，屬于無參數(shù)的方法。其基于如下假設(shè)：1）類中心點(diǎn)的密度大于鄰居節(jié)點(diǎn)的密度；2）類中心點(diǎn)與更高密度點(diǎn)之間的距離相對(duì)較大。

當(dāng)類中心節(jié)點(diǎn)確定后，需要將剩余的每個(gè)節(jié)點(diǎn)分配給比其密度大且距離最近的類中心節(jié)點(diǎn)。由此可見，其主要計(jì)算各個(gè)節(jié)點(diǎn)的局部密度和各個(gè)節(jié)點(diǎn)與高密度點(diǎn)之間的距離。

1）局部密度

其中，dist(xi,xj)表示節(jié)點(diǎn)xi到xj的距離，distcutoff為截?cái)嗑嚯x。

可見，對(duì)于數(shù)據(jù)樣本xi，其密度表示為與其之間的距離小于截?cái)嗑嚯x的數(shù)據(jù)樣本個(gè)數(shù)。

對(duì)于連續(xù)數(shù)據(jù)分布，數(shù)據(jù)樣本xi（i=1,2,…,n）的密度函數(shù)定義如下：

2）相對(duì)距離

給定數(shù)據(jù)樣本xi、xj和xk，其密度排列為：ρi>ρj>ρk。由式（3）可知，xi、xj和xk的距離排序?yàn)閐ist(xi,xk)>dist(xj,xk)>dist(xi,xj)。數(shù)據(jù)樣本空間中，相對(duì)距離可定義為

由式（4）可知，當(dāng)xi具有最大局部密度時(shí)，δi表示數(shù)據(jù)集中與距離最大的數(shù)據(jù)點(diǎn)與之間的距離（例如：xi與xk的距離）。否則，δi表示在所有局部密度大于xi數(shù)據(jù)點(diǎn)中，距離最小的數(shù)據(jù)點(diǎn)到xi之間的距離（例如：xi與xj的距離）。

數(shù)據(jù)點(diǎn)的分布情況如圖1（a）所示，可看出數(shù)據(jù)集包含兩個(gè)簇（分別用圓圈和方塊表示，其中噪聲點(diǎn)用三角表示）。從圖1（b）可知，在決策過程中，點(diǎn)1 和點(diǎn)10 的ρi和δi都相對(duì)較高，可標(biāo)記為中心點(diǎn)，而點(diǎn)26、27、28 的ρi相對(duì)較低但是δi相對(duì)較高，則標(biāo)記為噪聲。其他的點(diǎn)將被分配到它的最近鄰且密度比其大的數(shù)據(jù)點(diǎn)所在的簇中去。

圖1 密度峰值算法示例

2.2 節(jié)點(diǎn)重要性

節(jié)點(diǎn)重要性計(jì)算方法包括：度中心度［12］、聚類系數(shù)中心度［13］、中間中心度和基于節(jié)點(diǎn)相似性方法?；诠?jié)點(diǎn)相似性方法廣泛應(yīng)用于社區(qū)發(fā)現(xiàn)、協(xié)同過濾、信息檢索，其度量包括：歐幾里得距離、皮爾森相關(guān)系數(shù)、Jaccard Similarity和Adamic-Adar函數(shù)等。本文采用RA 函數(shù)（Resource allocation index）［14］，其效果優(yōu)于上述相似度函數(shù)，具體定義如下：

2.3 標(biāo)簽傳播算法

標(biāo)簽傳播算法具有收斂時(shí)間短，不需要輸入額外的參數(shù)的特點(diǎn)。對(duì)于網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)，使用其近鄰節(jié)點(diǎn)中數(shù)量最多的標(biāo)簽作為該節(jié)點(diǎn)的標(biāo)簽，不斷迭代，直到形成社區(qū)收斂為止。

3 基于密度峰值的標(biāo)簽傳播算法

在標(biāo)簽傳播過程中，未考慮節(jié)點(diǎn)重要性，導(dǎo)致標(biāo)簽?zāi)媪鳌榇?，DPC-RWL 算法采用基于密度的峰值聚類算法尋找數(shù)據(jù)空間中的核心節(jié)點(diǎn)，再分別計(jì)算每個(gè)節(jié)點(diǎn)和核心節(jié)點(diǎn)集之間權(quán)重，將權(quán)重最大值作為其權(quán)重值。最后，使用基于標(biāo)簽傳播算法思想的歸屬度函數(shù)以選擇最有影響的標(biāo)簽并更新節(jié)點(diǎn)標(biāo)簽。

3.1 核心節(jié)點(diǎn)集

給定復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集，采用密度峰值聚類算法提取數(shù)據(jù)節(jié)點(diǎn)的核心節(jié)點(diǎn)集，具體算法如下：

3.2 計(jì)算節(jié)點(diǎn)權(quán)重值

大多數(shù)社區(qū)檢測方法僅考慮節(jié)點(diǎn)與節(jié)點(diǎn)連接信息。為此，DPC-RWL 根據(jù)節(jié)點(diǎn)相似度和節(jié)點(diǎn)度為網(wǎng)絡(luò)中的節(jié)點(diǎn)分配權(quán)重，以提高社區(qū)檢測精度。

節(jié)點(diǎn)權(quán)重W可包括兩部分：其計(jì)算過程如下：

1）w1 可通過節(jié)點(diǎn)和核心節(jié)點(diǎn)集成員之間的相似度獲得。計(jì)算節(jié)點(diǎn)與核心集的每個(gè)成員之間的相似度值，選擇最大值為該節(jié)點(diǎn)賦值。本文利用RA指數(shù)計(jì)算節(jié)點(diǎn)相似度值，如下：

2）w2 通過計(jì)算節(jié)點(diǎn)到各個(gè)節(jié)點(diǎn)之間的平均路徑數(shù)獲得，即w2=（路徑條數(shù)之和/總結(jié)點(diǎn)數(shù)），總值越大則權(quán)重越大。其最終權(quán)重W=w1+w2。

3.3 歸屬度函數(shù)

傳統(tǒng)的標(biāo)簽傳播算法不足之處在于，具有強(qiáng)隨機(jī)性和弱魯棒性。為解決上述問題，提出基于節(jié)點(diǎn)重要性和節(jié)點(diǎn)路徑的歸屬度函數(shù)，以計(jì)算每個(gè)節(jié)點(diǎn)與其相鄰社區(qū)的歸屬度，并選擇歸屬度最大的社區(qū)標(biāo)簽作為其標(biāo)簽。主要有兩部分組成：

1）根據(jù)上述的節(jié)點(diǎn)權(quán)重進(jìn)行計(jì)算，定義如下：

其中，N(i)表示i節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集，j表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)，w(j)為j節(jié)點(diǎn)的權(quán)重值。

2）根據(jù)節(jié)點(diǎn)的路徑計(jì)算路徑數(shù)，在計(jì)算節(jié)點(diǎn)的親密度［15］時(shí)通常采用Katz函數(shù)，可區(qū)分不同的鄰居節(jié)點(diǎn)不同的影響力，對(duì)于短路徑賦予較大的權(quán)重，反之亦然。在根據(jù)RA 相似度函數(shù)，提出基于路徑度量的函數(shù)P(i,c)，定義如下：

其中，p表示節(jié)點(diǎn)i和j之間的路程，|p|表示路徑的長度，其范圍是1-α。p(i.c)值越大，則親密度越高。

綜上所述，給定節(jié)點(diǎn)i，其與近鄰節(jié)點(diǎn)的歸屬度函數(shù)定義如下：

其中，c表示i節(jié)點(diǎn)的鄰域節(jié)點(diǎn)，p(i,c)為社區(qū)c中節(jié)點(diǎn)i的路徑權(quán)重，w(i,c)是社區(qū)c中節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)權(quán)重值。

具體算法如下所示：

3.4 時(shí)間復(fù)雜度

本文主要從以下三個(gè)方面分析DPC-RWL 算法的時(shí)間復(fù)雜度：

1）在預(yù)處理階段：使用密度峰值聚類算法提取核心節(jié)點(diǎn)集，所有時(shí)間復(fù)雜度為O(n2)；

2）在計(jì)算節(jié)點(diǎn)權(quán)重值，則需要計(jì)算每個(gè)節(jié)點(diǎn)與核心節(jié)點(diǎn)的權(quán)重，故其時(shí)間復(fù)雜度為O(n2)；

3）在進(jìn)行節(jié)點(diǎn)的歸屬度計(jì)算，采用標(biāo)簽傳播的思想，故其時(shí)間復(fù)雜度為O(n)。

綜上，DPC-RWL算法的時(shí)間復(fù)雜度為O(n2)。

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

4.1 實(shí)驗(yàn)評(píng)估

本文方法運(yùn)行環(huán)境為：Windows10 操作系統(tǒng)，16GB 內(nèi)存，Intel（R）Core（TM）i7-8700。為驗(yàn)證算法的精確度，采用標(biāo)準(zhǔn)化互信息（NMI）對(duì)算法進(jìn)行評(píng)估，比較算法劃分結(jié)果與標(biāo)準(zhǔn)劃分結(jié)果之間的相似度。相似度越高，則社區(qū)劃分效果越好，其取值范圍是［0-1］。給定的兩個(gè)網(wǎng)絡(luò)劃分h1和h2，其計(jì)算公式如下：

其中，對(duì)于H為混合矩陣，其元素值Hij表示同時(shí)屬于i和j所在社區(qū)的節(jié)點(diǎn)數(shù)，Nh1表示劃分h1中社區(qū)的個(gè)數(shù)，Hi( )Hj表示H中第i行（j列）元素之和。

此外，本文還采用modularity 方法［16］評(píng)估社區(qū)檢測的結(jié)果，定義如下：

其中，m值表示社區(qū)的數(shù)量，L表示網(wǎng)絡(luò)中邊的總數(shù)，Ls表示模塊s中的邊的數(shù)量，ds表示模塊s中節(jié)點(diǎn)的總數(shù)。Q?[]-1,+1 ，Q→+1，表示社區(qū)劃分越好。

4.2 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)選取真實(shí)網(wǎng)絡(luò)和LFR人工基準(zhǔn)網(wǎng)絡(luò)［17］，采用空手道俱樂部網(wǎng)絡(luò)（Karate）、海豚社交網(wǎng)絡(luò)（Dolphins）等數(shù)據(jù)集，如表3所示。

表3 數(shù)據(jù)集信息

LFR 人工基準(zhǔn)網(wǎng)絡(luò)常用于社區(qū)發(fā)現(xiàn)研究中的模擬網(wǎng)絡(luò)，相關(guān)參數(shù)如表4 所示。本次實(shí)驗(yàn)采用6組LFR網(wǎng)絡(luò)，參數(shù)如表5所示。

表4 人工基準(zhǔn)網(wǎng)絡(luò)相關(guān)參數(shù)

表5 人工基準(zhǔn)網(wǎng)絡(luò)

4.3 對(duì)比實(shí)驗(yàn)

本節(jié)中，與LPA、LPAm、LPAm+算法進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果采用加權(quán)平均50次的實(shí)驗(yàn)方式得出。

真實(shí)網(wǎng)絡(luò)劃分結(jié)果如表6 和表7 所示。表6 使用modularity 方法進(jìn)行社區(qū)檢測，表7 則使用NMI進(jìn)行社區(qū)檢測。對(duì)比可知，DCP-RWL 算法在兩種社區(qū)檢測方法中都明顯優(yōu)于LPA、LPAm、LPAm+算法。

表6 真實(shí)網(wǎng)絡(luò)的模塊度

表7 真實(shí)網(wǎng)絡(luò)的NMI

LFR人工基準(zhǔn)網(wǎng)絡(luò)的NMI對(duì)比，每個(gè)算法運(yùn)行50 次，求其平均值做為最終的結(jié)果，如圖5 所示。圖中橫坐標(biāo)表示不同的mu 值（mu 值越大則表明社區(qū)結(jié)構(gòu)越模糊），縱坐標(biāo)表示NMI的值。

由圖2 可知，N1 和N2 的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為1000 個(gè)節(jié)點(diǎn)，隨著mu 值的不斷增大，NMI 值不斷下降。mu 為0.1-0.2 時(shí)，網(wǎng)絡(luò)結(jié)構(gòu)較為清楚且NMI 值相對(duì)較高。當(dāng)mu>0.5，所有算法的的NMI 均急速下降，mu 為0.8 時(shí)，傳統(tǒng)算法已經(jīng)無法識(shí)別網(wǎng)絡(luò)結(jié)構(gòu)，其他三種算法還具有一定的能力?？梢?，所提算法的NMI值均高于其他算法。

圖2 LFR-1000網(wǎng)絡(luò)的NMI對(duì)比

N3 和N4 的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)增加為2000 個(gè)節(jié)點(diǎn)。由圖3可知，mu為0.1～0.2時(shí)，四種算法的NMI值較高。當(dāng)mu>0.5，則所有算法的NMI 均開始下降。與圖2 相比較，當(dāng)mu>0.5 時(shí)，圖3 中的NMI 值 較低。但是，所提算法的NMI值依舊高于其他算法。

圖3 LFR-2000網(wǎng)絡(luò)NMI對(duì)比

當(dāng)N5 和N6 的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)增加為5000 個(gè)節(jié)點(diǎn)。由圖4 對(duì)比圖3 可知，其NMI 值的下降程度更大。但DPC-RWL 算法的NMI 值仍然高于其他三種算法。

圖4 LFR-5000網(wǎng)絡(luò)NMI對(duì)比

5 結(jié)語

針對(duì)標(biāo)簽傳播算法存在的隨機(jī)性問題，本文提出基于密度峰值的標(biāo)簽傳播算法（DPC-RWL）。首先，使用密度峰值聚類算法查找數(shù)據(jù)集中的核心節(jié)點(diǎn)集，再通過RA 指數(shù)和節(jié)點(diǎn)間的路徑長度為每個(gè)節(jié)點(diǎn)賦予權(quán)重值，最后在使用歸屬度函數(shù)求其每個(gè)節(jié)點(diǎn)與其相鄰社區(qū)的歸屬度值，選擇最大的作為最終的社區(qū)標(biāo)簽。實(shí)驗(yàn)表明，DPC-RWL 在真實(shí)數(shù)據(jù)集上所劃分社區(qū)質(zhì)量相對(duì)更高且社區(qū)劃分結(jié)果穩(wěn)定。在LFR人工基準(zhǔn)網(wǎng)絡(luò)中，當(dāng)mu的值比較大時(shí)，DPC-RWL算法準(zhǔn)確性更高。