施歡歡　印安濤

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

關鍵詞：圖聚類算法；圖熵；復雜網(wǎng)絡；重疊社區(qū)

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

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

1 相關工作

很多聚類算法被運用到復雜網(wǎng)絡的社區(qū)發(fā)現(xiàn)中，可以被總結為三大類：基于密度的方法、層次方法和基于劃分的方法。

1.1 基于密度的方法

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

1.2 層次方法

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

1.3 基于劃分的方法

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

2 問題定義

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

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

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

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

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

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所示。

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

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

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

3 算法

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

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

算法：SeedGrowthEntropy

輸入：圖G=（V，E）

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

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

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

Step 3：迭代移除聚類內(nèi)的鄰居節(jié)點如果移除能降低熵值。

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

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

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

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

4 評估方法和實驗結果

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

4.1 實驗數(shù)據(jù)

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

4.2 評價標準

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

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

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

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

f-measure的值f-recall為recall和precision的調(diào)和平均數(shù)，公式表達為：（7）

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

4.3 實驗結果和分析

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

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

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

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

5 結語

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