基于圖熵聚類的重疊社區發現算法

施歡歡　印安濤

摘要：圖聚類算法是數據挖掘和復雜網絡研究中的一個關鍵環節。基于密度、層次劃分的方法已經被廣泛應用于流行病學、新陳代謝和科學引文寫作中。盡管上述的聚類方法適用于復雜網絡的社區發現，但精度受到限制，其中一個最大的挑戰是重疊社區的生成。為填補這·缺口，提出了一種利用圖熵搜索局部最優的聚類方法。與傳統的基于密度的種子生長式方法不同，在每一次迭代中，引入圖熵來衡量圖結構的模塊度，并為種子的選擇提供了隨機選擇、基于節點的度和基于節點的聚類系數3種方案。經過自下而上迭代的聚類，引入準確率和召回率等評價指標評估聚類結果的精確度，證明了算法的有效性。

關鍵詞：圖聚類算法；圖熵；復雜網絡；重疊社區

復雜網絡在當今社會隨處可見，往往蘊含著重要的信息。復雜網絡規模龐大，節點連接復雜，直接對其進行研究比較困難。對復雜網絡中的社區結構進行研究，已成為當下的流行趨勢。社區結構經常重疊，存在同屬于幾個社區的節點。與此同時，許多社區結構會遞歸組合成一個層次結構。現存的方法忽視了社區的相互關系及其重疊，然而對于這部分的研究具有重要的實際意義。無論是尋找熱門的微博話題，還是醫學上對功能相關蛋白質組的尋覓，對社區結構的關系及重疊社區的深入探究都將影響巨大。

文章首先借鑒信息論中信息熵的概念，根據信息熵的公式定義節點熵和圖熵的公式。圖熵是節點熵的總和，作為聚類的模塊度的度量，圖熵越低則表明圖中模塊度越高。據此文章提出一種基于圖熵聚類的重疊社區發現算法，把圖熵作為種子生長的聚類過程中添加或刪除節點的依據。實驗部分，為種子的選擇提供了隨機選擇、基于節點的度和基于節點的聚類系數3種解決方案，并對實驗結果進行分析對比。

1 相關工作

很多聚類算法被運用到復雜網絡的社區發現中，可以被總結為三大類：基于密度的方法、層次方法和基于劃分的方法。

1.1 基于密度的方法

基于密度的方法發掘網絡中內部連接密集的子圖，根據對象周圍的密度不斷增長聚類。典型的例子是發現完全子圖的最大團算法。相對密集的子圖通過使用密度閥值或者結合滲透的小規模團被確定。選取種子作為初始節點，通過可替換的密度函數擴張這些種子。Mc0DE通過計算每個節點v的核心聚類系數給v設置權重，核心聚類系數是節點v和v的k個核心鄰居的密度，能夠放大內部連接密切的區域。算法選取權重最高的節點，通過遞歸地納入不違背閥值的鄰居節點擴大聚類。該方法需要預先設定閥值，這是基于密度的種子生長方法的缺陷。

1.2 層次方法

層次聚類方法創建層次以分解網絡，能夠幫助了解整個網絡功能組織的結構，因此被廣泛運用到復雜網絡的分析中。自底向上的凝聚算法初始時把每個節點都看作一個獨立的聚類，通過迭代合并兩個最近或最相似的集合完成最終的聚類。與之相反，自頂向下的分裂算法把整個圖看成一個聚類，然后遞歸地將單個大聚類分割成眾多小聚類。凝聚算法中兩個聚類的距離或相似度需要嚴格計算。分裂算法的挑戰是找到精確的分割點，其中使用最廣泛的是GN算法。

1.3 基于劃分的方法

劃分方法首先創建k個劃分，然后利用循環定位技術將對象從一個劃分移到另一個劃分來幫助改善劃分質量。為了達到全局最優，基于劃分的方法需要窮舉所有可能的分區。最常見的是k均值算法，每個聚類都用該聚類中對象的均值表示。

2 問題定義

盡管上述的聚類方法適用于復雜網絡的社區發現，但精度受到限制，其中一個最大的挑戰是重疊社區的生成。一個節點可能屬于不同的社區，所以要求聚類方法能夠分配節點到多個不同的聚類中。但一般的基于劃分的方法和層次方法總是產生不相交的集合，因此只有基于密度的方法適用于挖掘重疊聚類。與傳統的基于密度的方法不同，文章引入圖熵來衡量圖結構的模塊度。把熵的概念運用到圖中，可以定義每個節點的節點熵并計算整個圖的圖熵度量圖的模塊度。圖熵越低表示模塊度越高，因此圖熵可以作為在種子生長的聚類過程中添加或刪除節點的依據。

對于無向圖G=（V，E），假設G是由一群聚類組成，其中一個聚類是G=（y，E）。G內部節點連接密集，G外部節點連接稀疏。對于G中任意一個節點v，v有在y內的鄰居和在y外的鄰居，定義v的內連接為從v到V內鄰居節點的邊數，定義v的外連接為從v到V外鄰居節點的邊數。定義p_i（D為節點v的內連接率，公式表達為：（1）

其中|N（v）|為節點v的所有鄰居節點數，n為節點v的內連接數。則v的外連接率p₀（v）公式表達為：

p₀（v）=1-p_i（v） （2）

對于節點v，它的熵值取決于它的內連接和外連接的分布概率，參考信息熵，定義v的節點熵公式為：

e（v）=-p_i（v）long₂p_i（v）-p₀（v）long₂p₀（v） （3）

其中0≤p_i（v）≤1，因此可以得到e（v）和p_i（v）的關系圖像如圖1所示。

根據圖1，當節點v的所有鄰居節點全部在聚類內部或全部在聚類外部時，節點v的熵值最小，即e（v）=0；當節點v的鄰居節點均勻分布在聚類內部和聚類外部時，節點v的熵值最大，即e（v）=1。

圖熵定義為圖G=（V，E）中所有節點的節點熵之和，公式表達為（4）

圖熵是基于密度的定義，可以有效衡量聚類質量。圖熵越低表明圖中節點內連接率越高，外連接率越低。通過最小化圖熵的值不斷增加或刪除節點后得到的聚類就是一個社區。

3 算法

基于圖熵的聚類算法是一種種子生長型算法，通過反復最小化圖熵的值發掘局部最優聚類。如圖2所示，圓圈區域為聚類內部，加入節點d后，熵值減少，因此節點d被納入聚類；加入節點e后，熵值增加，節點e被拒絕納入聚類。

初始時單個種子是一個聚類，然后通過最小化圖熵的方式生長成最終聚類。算法詳細偽代碼如下：

算法：SeedGrowthEntropy

輸入：圖G=（V，E）

輸出：聚類集合列表（包括重疊聚類）。

Step 1：圖中的每一個節點都是候選種子。從候選種子中選取一部分節點作為種子節點并存入種子集中。

Step 2：從種子集中選取一個種子，加入它的所有鄰居節點形成一個聚類。

Step 3：迭代移除聚類內的鄰居節點如果移除能降低熵值。

Step 4：迭代添加當前聚類外的邊界節點如果添加能降低熵值。

Step 5：輸出具有最小圖熵值的聚類并從種子集中刪除該種子。

Step 6：重復step2、step3、step4和step5直到種子集中沒有種子剩余。

熵值聚類的主要思想是通過模塊化函數（圖熵）搜索局部最優社區。由于每次聚類結果輸出后都不會刪除聚類節點而是刪除種子集中的種子節點，確保了每個種子的生長都是從所有節點中進行選擇的。一個節點可能在多個種子生長時被選中，因此該算法能夠輸出重疊聚類，對應的就是重疊社區。種子的選擇就變得比較重要，既能讓選擇的種子的聚類結果覆蓋大部分網絡，又能提高算法的運行效率。根據復雜網絡中無標度的特征，網絡中小部分節點連接稠密，大部分節點連接稀疏。如果選取的種子是連接稀疏的節點，這樣的聚類沒有意義。因此種子的選擇可以基于節點的度或者節點的聚類系數。度越大或者聚類系數越大的節點更有機會是一個好種子。

4 評估方法和實驗結果

文章進行了多組實驗對算法進行評估，種子的選擇分為隨機選擇、基于節點的度和基于節點的聚類系數3種方式。算法由Java語言實現。

4.1 實驗數據

文章僅考慮無向圖數據集，使用亞馬遜合買產品網絡和它的地面實況社區。數據集來自于斯坦福大學提供的復雜網絡分析平臺SNAP（Stanford Network Analysis Project）中的Stanford Large Network Dataset Collection部分（http：//snap.stanford.edu/data/index.html）。如果商品i經常和商品j一起被買，那么網絡中i和j之間就有一條無向邊相連，很多件商品和邊共同構成復雜網絡。亞馬遜提供的每個商品決定了每個地面實況社區。地面實況是指“ground-truth”，是搜集到的準確客觀的數據，用于驗證實驗結果的準確性。認為產品類別中每個連接的部分是一個獨立的ground-truth社區，移除掉節點數少于3的社區后，一共有75491個真實社區。數據詳細情況如表1所示。

4.2 評價標準

falsef-measure直接比較每個輸出聚類和網絡中的真實社區，量化輸出聚類和每個功能模塊的匹配度，能夠評估聚類結果的精確度。對于基于圖熵聚類算法輸出的一個聚類c.和網絡中一個真實社區p_i，召回率（recall）也叫作真陽性或敏感度，定義為c_i和p_i公共節點數占p_i點數的比率，公式表達為：

recall=|c_i∩p_i|/|p_i| （5）

準確度（precision）也叫作陽性預測值，定義為c_i和p_i公共節點數占c_i節點數的比率，公式表達為：

precision=|c_i∩p_i|/|c_i| （6）

f-measure的值f-recall為recall和precision的調和平均數，公式表達為：（7）

關于f-score，對每個輸出聚類c從真實社區列表中搜索最匹配的社區p_i進行計算。然后求出所有最佳匹配的f-score的平均值作為聚類算法的精確度評價標準。

4.3 實驗結果和分析

一種情況下種子的選擇是隨機的，但是潛在的聚類核心更適合做種子，因此考慮兩種不同的基于節點連通性的方法來尋找網絡中的局部核心。第一種方法基于節點的度，第二個方法基于節點的聚類系數。在種子選擇中，分配具有較高度或者較高聚類系數的節點較高的優先級。文章對以上3種情況分別進行實驗。

以基于度的方法為例，實驗結果如圖3所示，聚類結果保存在.txt文件中，每一行是一個聚類。一共有33178行，表明算法生成了33178個社區（剔除節點數少于3個的社區）。社區的大小和個數分布如圖4所示（橫軸表示社區大小，縱軸表示社區個數）。可以看出，小規模社區分布眾多，隨著社區規模的增長，社區個數急速下降，最大的社區規模為324。

為了驗證重疊社區，以輸出結果中的c₁，c₂和c₃3個聚類為例，3個聚類規模大小不一，節點信息見表2，其中數字串為商品編號。圖5中（a），（b），（c）分別為c₁，c₂和c₃3個聚類各自的力導向圖，（d）為3個聚類一起時的力導向圖，（d）中深色節點為重疊節點，表明算法確實發現了重疊社區。根據3種情況的實驗結果，得到如表3所示的結果。

從表3中看出，和隨機選取的種子集相比，基于節點的度的種子集得到的社區數量更少但規模更大，而基于聚類系數的種子集得到的社區數量更大但規模更小。度高的節點由于接入更多的間接鄰居而影響很大一塊區域，所以社區規模大一些；而聚類系數高的節點限制了接入的鄰居個數導致社區規模小一些。宏觀看3個方均f-score差不多，基于度的結果更好一些，基于聚類系數的略差些，隨機選取排在最后，都維持在0.4左右，考慮到社區的基數比較大，這個結果足以表明基于圖熵的聚類方法具有良好的精確度。

5 結語

文章提出一種基于圖熵聚類的重疊社區發現算法，旨在發現給定復雜網絡中的絕大部分社區，包括重疊社區。算法引入圖熵的概念來衡量子圖的模塊化程度，通過最小化圖熵搜索局部最優的方法自底向上發掘所有社區，并且能夠發現重疊社區。文章首先介紹了被運用到復雜網絡的社區發現的聚類算法，主要分為三大類：基于密度的方法、層次方法和基于劃分的方法。然后介紹了節點熵和圖熵的概念。最后詳細描述了基于圖熵聚類的算法，并為種子的選擇提供了隨機選擇、基于節點的度和基于節點的聚類系數3種解決方案。實驗結果表明提出的算法有很好的效率，可以有效解決提出的問題，具有重要的實際意義。