結(jié)合熵有效性函數(shù)的FCM算法識(shí)別社團(tuán)結(jié)構(gòu)

賈寧寧，　封　筠

(石家莊鐵道大學(xué) 信息科學(xué)與技術(shù)學(xué)院,河北 石家莊　050043)

?

結(jié)合熵有效性函數(shù)的FCM算法識(shí)別社團(tuán)結(jié)構(gòu)

賈寧寧，封筠

(石家莊鐵道大學(xué) 信息科學(xué)與技術(shù)學(xué)院,河北 石家莊050043)

摘要：挖掘和發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)研究的基礎(chǔ)性問題。針對(duì)復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)往往具有重疊性，提出了結(jié)合熵有效性函數(shù)的模糊聚類(Fuzzy c-means, FCM)算法。首先基于信息熵提出了熵有效性函數(shù)，用于確定網(wǎng)絡(luò)的“最佳”聚類數(shù)；其次給出了聚類數(shù)范圍和兩個(gè)過濾條件；最后將三者與FCM算法相結(jié)合，應(yīng)用到Zachary’s karate club network、Dolphin social network和American college football network的社團(tuán)結(jié)構(gòu)檢測(cè)。為了進(jìn)一步體現(xiàn)熵有效性函數(shù)的優(yōu)越性，將熵有效性函數(shù)和模塊度函數(shù)，分別與k-means算法相結(jié)合，對(duì)3個(gè)網(wǎng)絡(luò)進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，熵有效性函數(shù)可以較準(zhǔn)確的找到“最佳”聚類數(shù)，且結(jié)合熵有效性函數(shù)的FCM算法劃分結(jié)果精確度都在90%以上。

關(guān)鍵詞：熵有效性函數(shù)；聚類數(shù)范圍；過濾條件；模糊聚類；社團(tuán)結(jié)構(gòu)

0引言

復(fù)雜網(wǎng)絡(luò)一般指由數(shù)量巨大的節(jié)點(diǎn)和節(jié)點(diǎn)之間錯(cuò)綜復(fù)雜的連邊共同構(gòu)成網(wǎng)絡(luò)，可刻畫Internet網(wǎng)、交通網(wǎng)、生物網(wǎng)和社會(huì)關(guān)系網(wǎng)等實(shí)際系統(tǒng)[1-2]。2002年Girvan和Newman首次提出社團(tuán)結(jié)構(gòu)，給出了社團(tuán)結(jié)構(gòu)的定性描述：社團(tuán)內(nèi)部聯(lián)系緊密，社團(tuán)之間聯(lián)系稀疏，并基于邊介數(shù)提出了GN算法[3]，在國際上掀起了一股社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)的熱潮。

根據(jù)節(jié)點(diǎn)能否同時(shí)屬于多個(gè)社團(tuán)，可將社團(tuán)分為非重疊社團(tuán)和重疊社團(tuán)。初期的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法對(duì)象為非重疊社團(tuán)，主要算法有譜方法[4-6]、GN算法[3]和Newman快速算法[7]。最近人們發(fā)現(xiàn)，這種硬劃分并不能真正反映真實(shí)世界中節(jié)點(diǎn)與社團(tuán)的實(shí)際關(guān)系，例如：在人際關(guān)系網(wǎng)中，每個(gè)人都可能會(huì)屬于家庭、工作單位、朋友圈子等多個(gè)社會(huì)團(tuán)體。在蛋白質(zhì)相互作用網(wǎng)絡(luò)中，一個(gè)節(jié)點(diǎn)可能會(huì)有多種生物功能，比如大部分蛋白質(zhì)都同時(shí)屬于多個(gè)蛋白質(zhì)復(fù)合物[1,8]。因此重疊社團(tuán)發(fā)現(xiàn)更符合真實(shí)世界的社團(tuán)組織規(guī)律，成為了近幾年社團(tuán)發(fā)現(xiàn)研究的新熱點(diǎn)。2005年P(guān)alla等[9]基于完全子圖提出了首個(gè)能夠發(fā)現(xiàn)重疊社團(tuán)的派系過濾算法(clique percolation method,CPM)。同年Adamcsek等[10]開發(fā)了一個(gè)基于CPM算法的免費(fèi)應(yīng)用軟件CFinder。張世華[11]利用譜方法將網(wǎng)絡(luò)空間轉(zhuǎn)換到特征空間，進(jìn)而結(jié)合模糊聚類算法(fuzzy c-means,FCM)識(shí)別復(fù)雜網(wǎng)絡(luò)中的重疊社團(tuán)。FCM算法屬于基于目標(biāo)函數(shù)的算法，具有原理簡單、解決問題范圍廣、可轉(zhuǎn)化為優(yōu)化問題。借助經(jīng)典數(shù)學(xué)的非線性規(guī)劃理論求解和易于實(shí)現(xiàn)的特點(diǎn)，使其在重疊社團(tuán)發(fā)現(xiàn)方面得到了廣泛關(guān)注。但FCM算法也存在一些問題：一是需要預(yù)先確定聚類數(shù)，破壞了算法的無監(jiān)督性和自適應(yīng)性；二是模糊加權(quán)指數(shù)的選擇缺少理論指導(dǎo)；三是對(duì)初始化敏感，容易陷入局部最小值，從而得不到全局最優(yōu)解[12]。

為了發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)的重疊社團(tuán)，在FCM算法的基礎(chǔ)上，針對(duì)FCM算法需要預(yù)先確定聚類數(shù)的問題提出了熵有效性函數(shù)，提高了FCM算法的無監(jiān)督性；對(duì)初始化敏感問題，將FCM算法初始化為隨機(jī)初始化隸屬度，改為采用度“最”大的節(jié)點(diǎn)作為初始中心點(diǎn)，降低了陷入局部最小值的概率。

1相關(guān)概念與算法

1.1熵有效性函數(shù)

熵的概念起源于熱力學(xué)，用來衡量系統(tǒng)的無序程度。Shannon利用熵定義了一個(gè)離散型隨機(jī)變量隨機(jī)性大小的程度，稱為信息熵[13]，如果一個(gè)隨機(jī)變量的隨機(jī)性越大，則用于表示該隨機(jī)變量的信息量就越大，反之亦然。熵在信息論中表示信源的平均不定度[14]，用Pi表示信源取第個(gè)符號(hào)的概率，信源所含信息熵表示形式為

(1)

受文獻(xiàn)[3]對(duì)社團(tuán)結(jié)構(gòu)的定性描述、文獻(xiàn)[12]中為確定模糊聚類算法的“最佳”聚類數(shù)而提出的基于粒度原理的有效性函數(shù)以及信息熵[13-14]概念的啟發(fā)，提出了基于信息熵的有效性函數(shù)，簡稱熵有效性函數(shù)，用于衡量FCM算法劃分結(jié)果的有效性，并確定“最佳”聚類數(shù)。

熵有效性函數(shù)由兩部分組成：社團(tuán)內(nèi)部熵和社團(tuán)之間熵，簡稱社團(tuán)內(nèi)熵和社團(tuán)間熵。由熵的概念可知，熵越小表明系統(tǒng)的無序程度越低，因此社團(tuán)內(nèi)熵越小表明社團(tuán)內(nèi)部聯(lián)系越緊密，社團(tuán)間熵越大表明社團(tuán)之間聯(lián)系越稀疏[13]。熵有效性函數(shù)定義為社團(tuán)內(nèi)熵與社團(tuán)間熵差，且熵有效性函數(shù)值越小表明劃分結(jié)果所得社團(tuán)結(jié)構(gòu)越明顯。

熵有效性函數(shù)

(2)

式中，H(inc)表示社團(tuán)內(nèi)熵；H(betc)表示社團(tuán)間熵。

在介紹社團(tuán)內(nèi)熵與社團(tuán)間熵之前，先介紹一下節(jié)點(diǎn)度概率，節(jié)點(diǎn)度概率為節(jié)點(diǎn)度的值比最大節(jié)點(diǎn)度值，如式(3)所示，通過節(jié)點(diǎn)度概率可以表明節(jié)點(diǎn)的重要度，重要度大的節(jié)點(diǎn)隨機(jī)性小，信息量小，與節(jié)點(diǎn)熵成正比關(guān)系。

(3)

式中，di表示節(jié)點(diǎn)i的度數(shù)；dmax表示網(wǎng)絡(luò)中節(jié)點(diǎn)度數(shù)的最大值。

社團(tuán)內(nèi)熵的求解方式為各節(jié)點(diǎn)熵之和，根據(jù)熵的定義式(1)，結(jié)合節(jié)點(diǎn)度概率式(3)，得到社團(tuán)內(nèi)熵為

(4)

式中，N是網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)；di是節(jié)點(diǎn)的度數(shù)；dmax是最大節(jié)點(diǎn)度數(shù)；PCm表示節(jié)點(diǎn)屬于社團(tuán)的概率，計(jì)算方法是社團(tuán)m的節(jié)點(diǎn)數(shù)除網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)。若節(jié)點(diǎn)i屬于多個(gè)社團(tuán)，則先求節(jié)點(diǎn)i屬于各社團(tuán)的概率，再求算術(shù)平均值。

社團(tuán)間熵的求解方式與社團(tuán)內(nèi)熵一致，在求解社團(tuán)間熵時(shí)，將社團(tuán)抽象為節(jié)點(diǎn)，社團(tuán)之間的連邊抽象為節(jié)點(diǎn)之間的連邊，由于在求解兩兩社團(tuán)之間的連邊時(shí)，每個(gè)社團(tuán)被計(jì)算了兩次，因此最后再除2。社團(tuán)間熵為

(5)

式中，lij表示社團(tuán)i與社團(tuán)j之間的連邊；lmax表示社團(tuán)間連邊數(shù)的最大值；Lin(i)表示社團(tuán)中邊數(shù)和。

1.2聚類數(shù)范圍

(6)

式中，N是網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)；dmax表示網(wǎng)絡(luò)中節(jié)點(diǎn)度數(shù)最大值；dmin表示網(wǎng)絡(luò)中節(jié)點(diǎn)度數(shù)最小值，若dmin小于2，令dmin為2。

1.3兩個(gè)過濾條件

考慮到聚類數(shù)范圍的最大聚類數(shù)和最小聚類數(shù)之間跨度較大，當(dāng)聚類數(shù)較大時(shí)，所得社團(tuán)中出現(xiàn)完全重疊的社團(tuán)的慨率較大；當(dāng)聚類數(shù)較小時(shí)，所得社團(tuán)可能會(huì)出現(xiàn)社團(tuán)之間存在較大重疊部分。因此針對(duì)以上兩個(gè)問題，對(duì)每個(gè)劃分結(jié)果，首先執(zhí)行兩個(gè)過濾條件：重疊社團(tuán)數(shù)比例和邊重疊率，再計(jì)算熵有效性函數(shù)值。兩個(gè)過濾條件定義如下：

重疊社團(tuán)數(shù)比例

(7)

邊重疊率

(8)

1.4譜方法與FCM算法

通過譜變換[6]可將網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)換為特征空間中的數(shù)據(jù)，給定一個(gè)網(wǎng)絡(luò)，可得該網(wǎng)絡(luò)的鄰接矩陣A=(aij)n×n和度矩陣D=(dii)，dii=∑kaik,利用廣義特征系統(tǒng)Ax=tDx的前K個(gè)特征向量組成特征矩陣，特征矩陣的每一行對(duì)應(yīng)于原網(wǎng)絡(luò)相應(yīng)各節(jié)點(diǎn)。再應(yīng)用FCM算法對(duì)特征空間中的數(shù)據(jù)進(jìn)行劃分，可得到相應(yīng)網(wǎng)絡(luò)的社團(tuán)劃分結(jié)果。

FCM是模式識(shí)別中常用的方法，該方法由Dunn[15]開發(fā)于1973年，Bezdek[16]于1983年對(duì)其進(jìn)行改進(jìn)。張世華[7]首先將FCM算法應(yīng)用于復(fù)雜網(wǎng)絡(luò)的重疊社團(tuán)發(fā)現(xiàn)。FCM算法的目標(biāo)函數(shù)為

(9)

(10)

(11)

1.5算法描述與時(shí)間復(fù)雜度分析

給定網(wǎng)絡(luò)的鄰接矩陣A=(aij)n×n，設(shè)置參數(shù)最大迭代次數(shù)lmax=100,閾值error=0.001算法具體流程如下：

(1) 初始化和譜映射：

step1,計(jì)算度矩陣D=(dii)，其中dii=∑kaik,k=1,2,3,…,n；

step2，由廣義特征系統(tǒng)Ax=tDx，得特征矩陣V=[e1,e2,…,en]；

step3，由聚類范圍式(6)初始化最大聚類數(shù)Cmax和最小聚類數(shù)Cmin，根據(jù)度矩陣D，選擇前最大Cmax個(gè)數(shù)據(jù)點(diǎn)作為初始中心點(diǎn)，構(gòu)成初始中心點(diǎn)矩陣Center。

(2) FCM和熵有效性函數(shù)：

主循環(huán)執(zhí)行c取值由Cmax遞減到Cmin

step1，根據(jù)特征矩陣V，形成c對(duì)應(yīng)的特征矩陣Ec=[e2,e3,…,ec]，并對(duì)Ec的行向量進(jìn)行L2規(guī)范化；

step2，內(nèi)循環(huán)l取值從1到lmax，根據(jù)式(10),式(11),式(9)更新隸屬度矩陣U，中心點(diǎn)矩陣center和目標(biāo)函數(shù)obj_fcn，直到obj_Fcn(l+1)-obj_Fcn(l)

step3，通過隸屬度矩陣U獲得聚類劃分結(jié)果，對(duì)劃分結(jié)果分別執(zhí)行兩個(gè)過濾條件式(7),式(8)，剔除無意義的結(jié)果；

step4，根據(jù)式(2),式(4),式(5)計(jì)算熵有效性函數(shù)值H(c)。

主循環(huán)結(jié)束

step5，熵有效性函數(shù)H(c)中最小值對(duì)應(yīng)的c值，即為“最佳”聚類數(shù)best_c，對(duì)應(yīng)的劃分結(jié)果即為改進(jìn)后算法的社團(tuán)劃分結(jié)果。

FCM算法中，每一次迭代過程中都要計(jì)算每一個(gè)數(shù)據(jù)點(diǎn)與所有類中心點(diǎn)的距離，然后計(jì)算隸屬度矩陣U，因此，如果數(shù)據(jù)集維數(shù)為p，計(jì)算距離的時(shí)間復(fù)雜度就為O(p)，將有N個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集聚類為c個(gè)類，總的時(shí)間復(fù)雜度就是O(pNc)[17]。而本文中的聚類數(shù)需要取到聚類范圍的最大值N/dmin,因此算法的時(shí)間復(fù)雜度是O(pN(N/dmin))，時(shí)間復(fù)雜度與網(wǎng)絡(luò)的最小節(jié)點(diǎn)度數(shù)成反比。

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

為了驗(yàn)證算法的有效性，將結(jié)合熵有效性函數(shù)的FCM算法應(yīng)用于Zachary’skaratenetwork、Dolphinsocialnetwork和Americancollegefootballnetwork。實(shí)驗(yàn)結(jié)果表明熵有效性函數(shù)求得的“最佳”聚類數(shù)與實(shí)際社團(tuán)數(shù)完全一致，且劃分情況與實(shí)際社團(tuán)結(jié)構(gòu)基本一致。

2.1Zachary’karateclubnetwork

著名的zachary’skarateclubnetwork被廣泛應(yīng)用于復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)[3]，它反映的是一所美國大學(xué)跆拳道俱樂部成員之間的社會(huì)關(guān)系。該數(shù)據(jù)集包括34個(gè)節(jié)點(diǎn)78條邊，其中節(jié)點(diǎn)代表成員，邊表示成員之間的社會(huì)關(guān)系。圖1(a)是網(wǎng)絡(luò)對(duì)應(yīng)的社團(tuán)內(nèi)熵、社團(tuán)間熵與熵有效性函數(shù)曲線，從圖中可以看出熵有效性函數(shù)非零最小值對(duì)應(yīng)的聚類數(shù)為2，與實(shí)際社團(tuán)數(shù)一致，近一步觀察可見，聚類數(shù)為2時(shí)，社團(tuán)內(nèi)熵與社團(tuán)間熵的差值最大，且社團(tuán)間熵的值為社團(tuán)間熵曲線的峰值。過濾條件rateoverlop過濾掉了c值7,8,10,11,12,13,14,15,16 ,17. 網(wǎng)絡(luò)結(jié)構(gòu)如圖1(b)所示，其中圓形和方形節(jié)點(diǎn)分別代表分裂后小俱樂部中各成員。圖1(c)是本文算法的劃分結(jié)果，從圖中可看出只有節(jié)點(diǎn)3劃分錯(cuò)誤， 近一步觀察可得節(jié)點(diǎn)3與兩個(gè)社團(tuán)的連邊數(shù)都是5，劃分正確率為33/34=97.1%。

圖1　Zachary’s karate club network劃分結(jié)果與熵有效性函數(shù)

2.2Dolphin social network

第二個(gè)數(shù)據(jù)是dolphin social network來自Newman個(gè)人網(wǎng)絡(luò)數(shù)據(jù)網(wǎng)站http://www-personal.umich.edu/～mejn/netdata/，該數(shù)據(jù)集包含62個(gè)節(jié)點(diǎn)159條邊。圖2(a)是該網(wǎng)絡(luò)的社團(tuán)內(nèi)熵、社團(tuán)間熵與熵有效性函數(shù)曲線圖，從圖2中可以看出熵有效性函數(shù)非零最小值對(duì)應(yīng)的聚類數(shù)是5, 重疊率rateoverlop過濾掉了c值8,9,10,11,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31。重疊社團(tuán)比例numoverlap過濾掉了c值12,13,14,15. 網(wǎng)絡(luò)實(shí)際社團(tuán)結(jié)構(gòu)如圖2(a)所示，其中方形、圓形分別代表一個(gè)社團(tuán)。圖2(c)表示本文算法對(duì)網(wǎng)絡(luò)的劃分結(jié)果，社團(tuán)編號(hào)從上到下從左到右依次為1,2,3,4,5。重疊節(jié)點(diǎn)為51,45,41,62,9,55,20,8。節(jié)點(diǎn)51是社團(tuán)1,3,4的重疊節(jié)點(diǎn)，節(jié)點(diǎn)9是社團(tuán)1,4的重疊節(jié)點(diǎn)，節(jié)點(diǎn)45,41,62是社團(tuán)3,4的重疊節(jié)點(diǎn)，節(jié)點(diǎn)20,8是社團(tuán)4,5的重疊節(jié)點(diǎn)，節(jié)點(diǎn)55是社團(tuán)2,5的重疊節(jié)點(diǎn)。若不計(jì)重疊節(jié)點(diǎn)社團(tuán)1,3,4與實(shí)際社團(tuán)1完全一致，2和5為實(shí)際社團(tuán)2完全一致，則節(jié)點(diǎn)劃分正確率為100%。

圖2　Dolphin social network劃分結(jié)果與熵有效性函數(shù)

2.3American college football network

最后一個(gè)數(shù)據(jù)American college football network代表美國大學(xué)生橄欖球隊(duì)比賽網(wǎng)絡(luò)[11]。該數(shù)據(jù)集包含115個(gè)節(jié)點(diǎn)616條邊，分別表示115個(gè)球隊(duì)和616場(chǎng)比賽。圖3(a)表示社團(tuán)內(nèi)熵、社團(tuán)間熵與熵有效性函數(shù)，熵有效性函數(shù)的非零最小值對(duì)應(yīng)的聚類數(shù)為 12，過濾條件numoverlap和rateoverlap分別過濾掉了c值13,14,15,16和9。網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)如圖3(b)所示，其中12個(gè)聯(lián)盟用不同的形狀和顏色深淺加以標(biāo)注，聯(lián)盟編號(hào)順序從上到下再從左到右依次為1,2,3,…,12。圖3(c)表示本文算法對(duì)網(wǎng)絡(luò)的劃分結(jié)果，7個(gè)社團(tuán)1,5,6,7,8,9,11包含了圖6(a)中對(duì)應(yīng)聯(lián)盟的所有節(jié)點(diǎn)。重疊節(jié)點(diǎn)依次為:6,13,43,81,83,113.節(jié)點(diǎn)29,59,60,64,81,83,91,98,111被錯(cuò)誤劃分, 可求得劃分精確率為106/115=92.2%。

圖3　American college football network劃分結(jié)果與熵有效性函數(shù)

對(duì)比分析三個(gè)網(wǎng)絡(luò)的聚類數(shù)范圍式(4)與實(shí)際社團(tuán)數(shù)，熵有效性函數(shù)求得的“最佳”聚類數(shù)和結(jié)合熵有效性函數(shù)的FCM算法對(duì)各網(wǎng)絡(luò)節(jié)點(diǎn)劃分正確率以及執(zhí)行時(shí)間，對(duì)比情況見表1。

表1　三個(gè)網(wǎng)絡(luò)聚類數(shù)范圍與實(shí)際聚類數(shù)及個(gè)別實(shí)驗(yàn)參數(shù)的對(duì)比

從表1中可以看出根據(jù)式(4)得到的三個(gè)網(wǎng)絡(luò)的聚類數(shù)范圍，基本包含實(shí)際社團(tuán)數(shù)，說明聚類數(shù)范圍式(4)具有較高準(zhǔn)確性，且基本能夠滿足計(jì)算需要。熵有效性函數(shù)求得的各網(wǎng)絡(luò)“最佳”聚類數(shù)中只有Dolphin social network與實(shí)際社團(tuán)數(shù)不一致，準(zhǔn)確度比較高，結(jié)合熵有效性函數(shù)的FCM算法對(duì)三個(gè)網(wǎng)絡(luò)劃分結(jié)果的正確率都在90%以上，表明算法具有較高有效性。從時(shí)間列可以看出，算法不會(huì)因?yàn)榫W(wǎng)絡(luò)規(guī)模的遞增而增長，而是與網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)度數(shù)的差值和社團(tuán)結(jié)構(gòu)本身有關(guān)。

為了衡量熵有效性函數(shù)的優(yōu)越性，將熵有效性函數(shù)與模塊度函數(shù)[18]相比較。模塊度函數(shù)的定義式為

(12)

式中，eii表示社團(tuán)i中包含的邊數(shù)占網(wǎng)絡(luò)總邊數(shù)的比例；ai表示與社團(tuán)i中邊相連的邊數(shù)占網(wǎng)絡(luò)總邊數(shù)的比例。

由于模塊度函數(shù)只適用于非重疊社團(tuán)，此處利用k-means算法[19]對(duì)兩種評(píng)價(jià)函數(shù)進(jìn)行比較，k-means算法的目標(biāo)函數(shù)為

(13)

式中，xk表示第j個(gè)集合中的第k個(gè)數(shù)據(jù)點(diǎn)；mj表示第j個(gè)中心點(diǎn)；‖xk-mj‖2表示第j個(gè)集合中所有數(shù)據(jù)點(diǎn)到中心點(diǎn)mj的歐氏距離平方和。

綜觀圖4三個(gè)網(wǎng)絡(luò)在k-means算法下模塊度函數(shù)和熵有效性函數(shù)對(duì)比，可知，模塊度函數(shù)求的得三個(gè)網(wǎng)絡(luò)的聚類數(shù)分別為4、5和11，熵有效性函數(shù)對(duì)三個(gè)網(wǎng)絡(luò)的聚類數(shù)分別是2、5和12。熵有效性函數(shù)準(zhǔn)確地找到了Zachary’s karate club network和American college football network的實(shí)際社團(tuán)數(shù)，而模塊度函數(shù)確定的聚類數(shù)與實(shí)際社團(tuán)數(shù)均不相同。

圖4　三個(gè)網(wǎng)絡(luò)在k-means算法下模塊度函數(shù)和熵有效性函數(shù)對(duì)比

對(duì)結(jié)合熵有效性函數(shù)的k-means算法和結(jié)合模塊度函數(shù)的k-means算法的實(shí)驗(yàn)性能進(jìn)行了對(duì)比分析，見表2。聚類數(shù)方面，熵有效性函數(shù)求的的聚類數(shù)與實(shí)際社團(tuán)數(shù)相符程度較高；節(jié)點(diǎn)準(zhǔn)確率方面，結(jié)合熵有效性函數(shù)的k-means算法在Zachary’s karate network社團(tuán)劃分中，錯(cuò)誤劃分節(jié)點(diǎn)為3，節(jié)點(diǎn)3與兩個(gè)社團(tuán)的連邊數(shù)都為5；時(shí)間方面來看，熵有效性函數(shù)較占優(yōu)勢(shì)。

表2　k-means算法下兩種函數(shù)的實(shí)驗(yàn)性能對(duì)比

注：表中Q表示模塊度函數(shù)，H表示熵有效性函數(shù)。

3結(jié)語

傳統(tǒng)的FCM算法需要預(yù)先指定聚類數(shù)，從而影響了算法的無監(jiān)督性，且不恰當(dāng)?shù)木垲悢?shù)會(huì)影響聚類結(jié)果。本文提出了結(jié)合熵有效性函數(shù)的FCM算法，避免了需要根據(jù)先驗(yàn)知識(shí)指定聚類數(shù)的問題，接著又給出了聚類數(shù)范圍和兩個(gè)過濾條件，提高了算法的執(zhí)行效率。將結(jié)合熵有效性函數(shù)的FCM算法應(yīng)用于三個(gè)經(jīng)典網(wǎng)絡(luò)的重疊社團(tuán)檢測(cè)，實(shí)驗(yàn)結(jié)果表明，熵有效性函數(shù)能夠較準(zhǔn)確地找到“最佳”聚類數(shù)，且算法社團(tuán)結(jié)構(gòu)劃分的精確率都在90%以上，從而驗(yàn)證了算法的有效性和可行性。由于聚類范圍依賴于節(jié)點(diǎn)度數(shù)，一定程度上影響了運(yùn)行時(shí)間，有待近一步改進(jìn)。但從k-means算法角度看，熵有效性函數(shù)在時(shí)間方面、聚類數(shù)方面和節(jié)點(diǎn)準(zhǔn)確率方面較優(yōu)于模塊度函數(shù)，且熵有效性函數(shù)既適用于非重疊社團(tuán)又適用于重疊社團(tuán)。

參考文獻(xiàn)

[1]駱志剛,丁凡,蔣曉舟,等.復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法研究新進(jìn)展[J].國防科技大學(xué)學(xué)報(bào), 2011, 33(1) : 47-52.

[2]賈寧寧,封 筠.復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)[J].河北省科學(xué)院學(xué)報(bào), 2013, 30(2) : 54-57.

[3]GIRVANM,NEWMANMEJ.Communitystructureinsocialandbiologicalnetworks[J].PNatlAcadSciUSA,2002,99(12) : 7812-7826.

[4]張燕平,王楊,趙姝.應(yīng)用Normal矩陣譜平分法的多社團(tuán)發(fā)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用, 2010,46(27) : 43-45.

[5]張聰, 沈惠璋.基于譜方法的復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的模塊度[J].系統(tǒng)工程理論與實(shí)踐, 2013,33(5) : 1231-1239.

[6]VERMAD,MEILA.Acomparisonofspectralclusteringalgorithms[R].Washington:UWCSE, 2003.

[7]NEWMANMEJ.FastAlgorithmforDetectingCommunityStructureinNetworks[J].PhysRevE, 2004,69(6):066133.

[8]劉大有,金弟,何東曉,等.復(fù)雜網(wǎng)絡(luò)社團(tuán)挖據(jù)綜述[J].計(jì)算機(jī)研究與發(fā)展,2013,50(10) : 2140-2153.

[9]PALLAG,DERENYII,FARKASI,etal.Uncoveringtheoverlappingcommunitystructureofcomplexnetworksinnatureandsociety[J].Nature, 2005,435(7043) : 814-818.

[10]ADAMCSEK B, PALLA G, FARKAS I, et al. CFinder:locating clique and overlapping modules in biological networks[J]. BIOINFORMATICS APPLICATIONS NOTE, 2005,00(00) : 1-2.

[11]ZHANG S, WANG R, ZHANG X. Identification of overlapping community structure in complex networks using fuzzy c-means clustering[J].Physical A, 2007,374(1):483-490.

[12]陳東輝. 基于目標(biāo)函數(shù)的模糊聚類算法關(guān)鍵技術(shù)研究[D].西安:西安電子科技大學(xué)計(jì)算機(jī)學(xué)院,2012.

[13]孫茜雅.基于最小熵聚類的社團(tuán)檢測(cè)算法[J].電子科技,2012,25(3):13-16.

[14]鄧小龍,王柏,吳斌,等.基于信息熵的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分建模和驗(yàn)證[J].計(jì)算機(jī)研究與發(fā)展,2012,49(4):725-734.

[15]DUNN J C A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters[J]. Cybernet. 1973,3(3): 32-57.

[16]BEZDEK J C.Pattern recognition with fuzzy objective function algorithms[M]. New York：Plenum Press, 1981.

[17]呂曉云,李星毅,施化吉.基于約簡數(shù)據(jù)集的FCM聚類算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2010,31(18):4062-4064.

[18]NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E.2004, 69:96-113.

[19]MACQUEE J B. Some Methods for classification and Analysis of Multivariate Observations[C]//Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley:University of California Press, 1967:281-297.

FCM Combined with Validity Measure Function of Entropy to Identity Community Structure

Jia Ningning，F(xiàn)eng Jun

(School of Information Science and Technology，Shijiazhuang Tiedao University，Shijiazhuang 050043，China)

Abstract:Mining and identifying community structure in complex networks is a fundamental issue in complex network research. In view of there are often overlapping communities in complex network, an improved Fuzzy c-means(FCM) method based on validity measure function of entropy is proposed. Firstly, devise a validity measure function of entropy, and use to determine the “best” clustering number of a network. Secondly, point out a range of clustering number and two filter conditions. Finally, combine them with FCM to detect communities in Zachary's karate club network, Dolphin social network and American college football network. In order to further demonstrate the superiority of validity measure function of entropy effectiveness, combine validity measure function of entropy and modularity function with k-means method, respectively, on the three networks. Experimental results show that the validity measure function of entropy could accurately find the actual clustering number, and the improved FCM method's accuracy of clustering is above 90%.

Key words:validity measure function of entropy；clustering number range；filter condition；fuzzy c-means；community structure

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：2095-0373(2016)01-0103-08

作者簡介：賈寧寧(1989-),女,河北邯鄲人,碩士研究生,研究方向:復(fù)雜網(wǎng)絡(luò)。E-mail:ning891221@163.com

基金項(xiàng)目:河北省自然科學(xué)基金項(xiàng)目(F2013210109)

收稿日期：2014-08-29責(zé)任編輯:劉憲福

DOI:10.13319/j.cnki.sjztddxxbzrb.2016.01.19

賈寧寧，封筠.結(jié)合熵有效性函數(shù)的FCM算法識(shí)別社團(tuán)結(jié)構(gòu)[J].石家莊鐵道大學(xué)學(xué)報(bào):自然科學(xué)版,2016,29(1):103-110.