基于密度峰值的標簽傳播算法?

吳衛江 王星豪 潘雪玲 鄭藝峰 鄭 猋

（1.中國石油大學（北京）石油數據挖掘北京市重點實驗室 北京 102249）

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

（3.閩南師范大學數據科學與智能應用福建省高等學校重點實驗室 漳州 363000）

（4.閩南師范大學計算機學院 漳州 363000）

1 引言

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

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

針對上述問題，本文提出基于密度峰值的標簽傳播算法（DPC-RWL）。首先，使用基于密度的社區檢測方法提取出社區的核心節點集。其次，利用相似度函數為社區中的每個節點賦權重值以有效解決標簽傳播算法的不穩定性問題。最后，結合標簽傳播算法思想構建目標函數用以劃分社區。實驗表明，DPC-RWL算法均取得較好實驗效果。

2 相關知識

2.1 密度均值聚類算法

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

當類中心節點確定后，需要將剩余的每個節點分配給比其密度大且距離最近的類中心節點。由此可見，其主要計算各個節點的局部密度和各個節點與高密度點之間的距離。

1）局部密度

其中，dist(xi,xj)表示節點xi到xj的距離，distcutoff為截斷距離。

可見，對于數據樣本xi，其密度表示為與其之間的距離小于截斷距離的數據樣本個數。

對于連續數據分布，數據樣本xi（i=1,2,…,n）的密度函數定義如下：

2）相對距離

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

由式（4）可知，當xi具有最大局部密度時，δi表示數據集中與距離最大的數據點與之間的距離（例如：xi與xk的距離）。否則，δi表示在所有局部密度大于xi數據點中，距離最小的數據點到xi之間的距離（例如：xi與xj的距離）。

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

圖1 密度峰值算法示例

2.2 節點重要性

節點重要性計算方法包括：度中心度［12］、聚類系數中心度［13］、中間中心度和基于節點相似性方法。基于節點相似性方法廣泛應用于社區發現、協同過濾、信息檢索，其度量包括：歐幾里得距離、皮爾森相關系數、Jaccard Similarity和Adamic-Adar函數等。本文采用RA 函數（Resource allocation index）［14］，其效果優于上述相似度函數，具體定義如下：

2.3 標簽傳播算法

標簽傳播算法具有收斂時間短，不需要輸入額外的參數的特點。對于網絡中每一個節點，使用其近鄰節點中數量最多的標簽作為該節點的標簽，不斷迭代，直到形成社區收斂為止。

3 基于密度峰值的標簽傳播算法

在標簽傳播過程中，未考慮節點重要性，導致標簽逆流。為此，DPC-RWL 算法采用基于密度的峰值聚類算法尋找數據空間中的核心節點，再分別計算每個節點和核心節點集之間權重，將權重最大值作為其權重值。最后，使用基于標簽傳播算法思想的歸屬度函數以選擇最有影響的標簽并更新節點標簽。

3.1 核心節點集

給定復雜網絡數據集，采用密度峰值聚類算法提取數據節點的核心節點集，具體算法如下：

3.2 計算節點權重值

大多數社區檢測方法僅考慮節點與節點連接信息。為此，DPC-RWL 根據節點相似度和節點度為網絡中的節點分配權重，以提高社區檢測精度。

節點權重W可包括兩部分：其計算過程如下：

1）w1 可通過節點和核心節點集成員之間的相似度獲得。計算節點與核心集的每個成員之間的相似度值，選擇最大值為該節點賦值。本文利用RA指數計算節點相似度值，如下：

2）w2 通過計算節點到各個節點之間的平均路徑數獲得，即w2=（路徑條數之和/總結點數），總值越大則權重越大。其最終權重W=w1+w2。

3.3 歸屬度函數

傳統的標簽傳播算法不足之處在于，具有強隨機性和弱魯棒性。為解決上述問題，提出基于節點重要性和節點路徑的歸屬度函數，以計算每個節點與其相鄰社區的歸屬度，并選擇歸屬度最大的社區標簽作為其標簽。主要有兩部分組成：

1）根據上述的節點權重進行計算，定義如下：

其中，N(i)表示i節點的鄰居節點集，j表示節點i的鄰居節點，w(j)為j節點的權重值。

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

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

綜上所述，給定節點i，其與近鄰節點的歸屬度函數定義如下：

其中，c表示i節點的鄰域節點，p(i,c)為社區c中節點i的路徑權重，w(i,c)是社區c中節點i的鄰居節點權重值。

具體算法如下所示：

3.4 時間復雜度

本文主要從以下三個方面分析DPC-RWL 算法的時間復雜度：

1）在預處理階段：使用密度峰值聚類算法提取核心節點集，所有時間復雜度為O(n2)；

2）在計算節點權重值，則需要計算每個節點與核心節點的權重，故其時間復雜度為O(n2)；

3）在進行節點的歸屬度計算，采用標簽傳播的思想，故其時間復雜度為O(n)。

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

4 實驗

4.1 實驗評估

本文方法運行環境為：Windows10 操作系統，16GB 內存，Intel（R）Core（TM）i7-8700。為驗證算法的精確度，采用標準化互信息（NMI）對算法進行評估，比較算法劃分結果與標準劃分結果之間的相似度。相似度越高，則社區劃分效果越好，其取值范圍是［0-1］。給定的兩個網絡劃分h1和h2，其計算公式如下：

其中，對于H為混合矩陣，其元素值Hij表示同時屬于i和j所在社區的節點數，Nh1表示劃分h1中社區的個數，Hi( )Hj表示H中第i行（j列）元素之和。

此外，本文還采用modularity 方法［16］評估社區檢測的結果，定義如下：

其中，m值表示社區的數量，L表示網絡中邊的總數，Ls表示模塊s中的邊的數量，ds表示模塊s中節點的總數。Q?[]-1,+1 ，Q→+1，表示社區劃分越好。

4.2 實驗數據

實驗選取真實網絡和LFR人工基準網絡［17］，采用空手道俱樂部網絡（Karate）、海豚社交網絡（Dolphins）等數據集，如表3所示。

表3 數據集信息

LFR 人工基準網絡常用于社區發現研究中的模擬網絡，相關參數如表4 所示。本次實驗采用6組LFR網絡，參數如表5所示。

表4 人工基準網絡相關參數

表5 人工基準網絡

4.3 對比實驗

本節中，與LPA、LPAm、LPAm+算法進行對比，實驗結果采用加權平均50次的實驗方式得出。

真實網絡劃分結果如表6 和表7 所示。表6 使用modularity 方法進行社區檢測，表7 則使用NMI進行社區檢測。對比可知，DCP-RWL 算法在兩種社區檢測方法中都明顯優于LPA、LPAm、LPAm+算法。

表6 真實網絡的模塊度

表7 真實網絡的NMI

LFR人工基準網絡的NMI對比，每個算法運行50 次，求其平均值做為最終的結果，如圖5 所示。圖中橫坐標表示不同的mu 值（mu 值越大則表明社區結構越模糊），縱坐標表示NMI的值。

由圖2 可知，N1 和N2 的網絡節點數為1000 個節點，隨著mu 值的不斷增大，NMI 值不斷下降。mu 為0.1-0.2 時，網絡結構較為清楚且NMI 值相對較高。當mu>0.5，所有算法的的NMI 均急速下降，mu 為0.8 時，傳統算法已經無法識別網絡結構，其他三種算法還具有一定的能力。可見，所提算法的NMI值均高于其他算法。

圖2 LFR-1000網絡的NMI對比

N3 和N4 的網絡節點數增加為2000 個節點。由圖3可知，mu為0.1～0.2時，四種算法的NMI值較高。當mu>0.5，則所有算法的NMI 均開始下降。與圖2 相比較，當mu>0.5 時，圖3 中的NMI 值 較低。但是，所提算法的NMI值依舊高于其他算法。

圖3 LFR-2000網絡NMI對比

當N5 和N6 的網絡節點數增加為5000 個節點。由圖4 對比圖3 可知，其NMI 值的下降程度更大。但DPC-RWL 算法的NMI 值仍然高于其他三種算法。

圖4 LFR-5000網絡NMI對比

5 結語

針對標簽傳播算法存在的隨機性問題，本文提出基于密度峰值的標簽傳播算法（DPC-RWL）。首先，使用密度峰值聚類算法查找數據集中的核心節點集，再通過RA 指數和節點間的路徑長度為每個節點賦予權重值，最后在使用歸屬度函數求其每個節點與其相鄰社區的歸屬度值，選擇最大的作為最終的社區標簽。實驗表明，DPC-RWL 在真實數據集上所劃分社區質量相對更高且社區劃分結果穩定。在LFR人工基準網絡中，當mu的值比較大時，DPC-RWL算法準確性更高。