基于加權聚類集成的標簽傳播算法

張美琴，白亮，王俊斌

現實世界中存在各種各樣的復雜系統，網絡則是這些系統的普遍存在形式，如人際關系網，因特網、大型電力網格等。為了能清晰地發現網絡中的信息，需要挖掘網絡的社區結構。 社區結構是復雜網絡的一個重要特性，整個網絡是由若干個“社區”構成的，每個社區內部的節點之間的連接相對非常緊密，而各個社區之間的連接卻比較稀疏。利用網絡的拓撲結構，能更準確地發現社區。網絡社區結構的發現，有助于更好地了解社區結構、理解網絡的功能和特性、預測復雜網絡的行為，在社會網絡、信息推薦、精準營銷等領域都有很大的應用價值。

目前提出的代表性社區發現算法有潛在空間算法[1]、譜聚類算法[2-3]、模塊最大化算法[4-8]、標簽傳播算法等，根據不同的科學需要，這些算法有不同的社區定義或類定義[9]。其中，由Raghavan等[10]在2007年提出的標簽傳播算法(LPA)由于其擁有線性時間復雜度而被廣泛應用于處理大規模網絡。然而，該算法中每個節點的標簽更新取決于其鄰居節點，更新效果受節點初始輸入和標簽更新順序的影響。因此LPA算法的最終結果存在不確定性，影響了社區劃分的準確性和穩定性。基于LPA結果的不穩定性，眾多學者提出了對LPA 的改進算法[11?18]。例如，Barber等[11]在 2009年提出使用模塊度最大化的變體作為約束的LPA算法(LPAm)，該算法將標簽傳播算法轉化為等價優化問題處理； Liu等[12]在2010年針對LPAm算法可能會出現社區劃分陷入局部極大值的問題，提出一種改進的標簽傳播算法(LPAm+)，其核心是將LPAm算法與多步貪婪凝聚算法(MSG)融合，最大限度地減少模塊空間，避免出現局部最大值； Xie等在2011年發表的文獻[13]中提出了針對提高社區檢測速度和提高社區質量的改進LPA算法； He等[14]在2014年使用了PageRank來衡量網絡中節點的重要性，提出了基于節點重要性的LPA算法； Sun等[15]在2015年提出基于中心的標簽傳播算法(CenLP)，通過高密度鄰居節點的相似性使節點按特定順序更新標簽； Li等[16]在2017年提出改進的LPA算法Stepping LPA-S算法，它通過模塊度和目標函數DN來度量節點或子網的相似性，其標簽通過相似性進行傳播，最終獲得了比LPA更準確的結果。

雖然已有多種改進的LPA算法被提出，但依然存在穩定性和精確性不高的問題[17?18]。聚類集成技術正是解決聚類算法結果不穩定和不精確的重要方法之一。目前，多種聚類集成技術也已得到發展[19?21]。因此，本文通過將聚類集成技術與標簽傳播算法融合，提出了基于加權聚類集成的標簽傳播算法。該算法通過引入模塊度來評估每次LPA結果的重要性，加強了每個基聚類的有效性，最后采用聚類集成技術實現提高社區發現結果的穩定性和準確性。

1 基于加權聚類集成的標簽傳播算法

1.1 標簽傳播算法(LPA)

標簽傳播算法(LPA)的核心思想是每個節點的標簽通過其出現次數最多的鄰居節點的標簽來決定自身的標簽，通過不斷迭代，節點的標簽變化達到穩定后，將最終具有相同標簽的節點劃分為一個社區，完成社區劃分。其最大的特點是簡單、高效，缺點是每次迭代結果不穩定，準確率不高。在文獻[10]中給出了該算法的具體描述如下。

1)為所有節點初始化一個唯一的標簽，每個標簽代表一個社區。

2)產生隨機遍歷順序遍歷所有節點，每個節點選擇其出現次數最多的鄰居節點標簽來更新自身的標簽，以此達到標簽的傳播。

3)若存在節點的鄰居節點標簽數出現多個最大值，則隨機選其中一個最大值所對應的標簽來更新該節點的標簽。重復2)，直到標簽更新穩定，停止迭代。

4)將具有相同標簽的節點劃分為一個社區。

該算法的時間復雜度為O(n+m)O(n+m)，其中，n代表為結點分配標簽的時間，m代表每次迭代更新的時間。

1.2 基于加權聚類集成的標簽傳播算法

在介紹本文提出的新算法之前，首先給出網絡、模塊度、基聚類集、節點加權相似性度量等相關概念如下。

第t次運行標簽傳播算法所產生的單個聚類結果為一個基聚類，將多個標簽傳播算法的結果融合來代替單個標簽傳播算法的結果，使用聚類集成技術從結果集中發現最一致的結果。然而，聚類集成的結果會受到單個基聚類質量的影響，為了提高聚類結果的穩定性，因此提出加權相似性度量。

基于以上定義，提出基于加權聚類集成的標簽傳播算法。 用LPA算法對復雜網絡進行次聚類，聚類產生的結果形成一個的基聚類集矩陣，然后根據定義4融入模塊度在基聚類集上求出一個維的節點加權相似性矩陣，最后通過層次聚類算法產生最終的結果。其聚類過程如圖1所示。

圖1 算法框架Fig. 1 The framework of the proposed algorithm

具體算法步驟如下：

2 實驗分析

2.1 實驗數據

為了驗證本文提出的算法的有效性，選取了5個不同規模的真實網絡數據集，分別為football、dolphins、karate、web、word 數據集。其中football數據集是由美國橄欖球聯賽中球隊的比賽關系構成的網絡，共包含115支球隊。Dolphins數據集是由新西蘭的一個海豚群體組成的海豚關系網，網絡中的邊表示兩只海豚之間的頻繁接觸次數。Karate數據集是一個由34個空手道俱樂部成員之間的關系構成的社會網絡，網絡中的邊表示兩個俱樂部成員經常出現在俱樂部活動之外的其他場合的次數。Web數據集是某網站上所有網頁構成的關系網，節點代表網頁，邊代表超鏈接。Word數據集是名詞形容詞搭配網絡。數據集的信息描述如表1所示。

表 1 數據集描述Table 1 Description of network data sets

2.2 評價指標

本文使用標準互信息(normalized mutual information， NMI)和調整蘭德系數(adjusted rand Index，ARI)來評價最終聚類質量。

標準互信息(NMI)和調整蘭德系數(ARI)常常用于社區劃分質量的評價，能有效衡量給定社區劃分結果與真實網絡劃分的相似程度。NMI的定義為

ARI的定義為

2.3 實驗結果分析

為了測試新算法的有效性，使其分別與5個現有的LPA的改進算法在真實數據集上進行了比較測試，這些LPA的改進算法包括LPA[10]、LPA_S[16]、LPAm[11]、LPAm+[12]、BGLL[18]。分別從NMI和ARI兩個評價指標將新算法與經典算法進行了比較，每個算法在每個數據集上都運行了100次，實驗結果如表2～3所示。通過對實驗結果的對比分析顯示，新算法的實驗效果在football、dolphins、web、word 數據集上都有明顯的提高，即其社區劃分更接近于真實社區的劃分，尤其是在 dolphins 數據集，該算法的效果較其他算法高出10%多。雖然在karate數據集上新算法的實驗結果并非最高，但也表明新算法在大部分數據集上的表現仍然具有很大優勢。同時，對于算法本身的性能的測評中，由于該算法只涉及因運行LPA算法次數的差異所形成的基聚類集的維度的不同對算法最終結果所造成的影響，因此本文也對運行不同次標簽傳播算法得出的最終社區劃分結果進行了實驗，實驗結果表明，隨著運行次數的增多，社區劃分結果越穩定，且運行到一定次數時，社區劃分效果均能趨于平穩。綜上所述，本文提出的基于加權聚類集成的標簽傳播算法較其他算法在NMI和ARI上都有良好的表現，且算法本身表現也收斂，因此新算法能在社區劃分的結果上更接近于實際社區劃分情況，提高了社區發現的精確性。

表 2 不同算法的 NMI值比較Table 2 Clustering results of different algorithms with respect to NMI

表 3 不同算法的 ARI值比較Table 3 Clustering results of different algorithms with respect to ARI

3 結束語

本文主要利用聚類集成技術對LPA進行了改進，提出了基于加權聚類集成的標簽傳播算法。該算法首先執行多次LPA產生多個標簽傳播結果作為基聚類集，并計算出每次LPA結果的模塊度值作為對應基聚類的權重，然后計算出融入權值后的節點相似性矩陣，最后采用層次聚類方法得到最終的社區劃分結果。在真實網絡數據集上的實驗結果表明，新算法在NMI和ARI兩個評價指標上效果都有所提高，表明新算法可以獲得更好的社區發現結果，提高了社區發現的精確性。