基于圖熵聚類的重疊社區(qū)發(fā)現(xiàn)算法

施歡歡　印安濤

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

關(guān)鍵詞：圖聚類算法；圖熵；復(fù)雜網(wǎng)絡(luò)；重疊社區(qū)

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

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

1 相關(guān)工作

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

1.1 基于密度的方法

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

1.2 層次方法

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

1.3 基于劃分的方法

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

2 問(wèn)題定義

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

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

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

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

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

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）的關(guān)系圖像如圖1所示。

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

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

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

3 算法

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

初始時(shí)單個(gè)種子是一個(gè)聚類，然后通過(guò)最小化圖熵的方式生長(zhǎng)成最終聚類。算法詳細(xì)偽代碼如下：

算法：SeedGrowthEntropy

輸入：圖G=（V，E）

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

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

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

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

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

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

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

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

4 評(píng)估方法和實(shí)驗(yàn)結(jié)果

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

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

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

4.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

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

準(zhǔn)確度（precision）也叫作陽(yáng)性預(yù)測(cè)值，定義為c_i和p_i公共節(jié)點(diǎn)數(shù)占c_i節(jié)點(diǎn)數(shù)的比率，公式表達(dá)為：

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

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

關(guān)于f-score，對(duì)每個(gè)輸出聚類c從真實(shí)社區(qū)列表中搜索最匹配的社區(qū)p_i進(jìn)行計(jì)算。然后求出所有最佳匹配的f-score的平均值作為聚類算法的精確度評(píng)價(jià)標(biāo)準(zhǔn)。

4.3 實(shí)驗(yàn)結(jié)果和分析

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

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

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

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

5 結(jié)語(yǔ)

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