賈寧寧，　封　筠

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

?

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

賈寧寧，封筠

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

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

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

0引言

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

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

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

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

1.1熵有效性函數(shù)

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

(1)

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

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

熵有效性函數(shù)

(2)

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

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

(3)

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

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

(4)

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

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

(5)

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

1.2聚類數(shù)范圍

(6)

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

1.3兩個過濾條件

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

重疊社團數(shù)比例

(7)

邊重疊率

(8)

1.4譜方法與FCM算法

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

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

(9)

(10)

(11)

1.5算法描述與時間復雜度分析

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

(1) 初始化和譜映射：

step1,計算度矩陣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個數(shù)據(jù)點作為初始中心點，構(gòu)成初始中心點矩陣Center。

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

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

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

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

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

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

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

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

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

2實驗結(jié)果分析

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

2.1Zachary’karateclubnetwork

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

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

2.2Dolphin social network

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

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

2.3American college football network

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

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

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

表1　三個網(wǎng)絡(luò)聚類數(shù)范圍與實際聚類數(shù)及個別實驗參數(shù)的對比

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

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

(12)

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

由于模塊度函數(shù)只適用于非重疊社團，此處利用k-means算法[19]對兩種評價函數(shù)進行比較，k-means算法的目標函數(shù)為

(13)

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

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

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

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

表2　k-means算法下兩種函數(shù)的實驗性能對比

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

3結(jié)語

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

參考文獻

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

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

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

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

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

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

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

[8]劉大有,金弟,何東曉,等.復雜網(wǎng)絡(luò)社團挖據(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]陳東輝. 基于目標函數(shù)的模糊聚類算法關(guān)鍵技術(shù)研究[D].西安:西安電子科技大學計算機學院,2012.

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

[14]鄧小龍,王柏,吳斌,等.基于信息熵的復雜網(wǎng)絡(luò)社團劃分建模和驗證[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].計算機工程與設(shè)計,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

中圖分類號：TP393

文獻標志碼：A

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

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

基金項目:河北省自然科學基金項目(F2013210109)

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

DOI:10.13319/j.cnki.sjztddxxbzrb.2016.01.19

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