有向網(wǎng)絡(luò)下的CoDA社區(qū)發(fā)現(xiàn)算法評(píng)估

郭 松，張冬雯，許云峰，楊玉林，鄭雅潔，柳晨光

(河北科技大學(xué)信息科學(xué)與工程學(xué)院，河北石家莊 050018)

有向網(wǎng)絡(luò)下的CoDA社區(qū)發(fā)現(xiàn)算法評(píng)估

郭 松，張冬雯，許云峰，楊玉林，鄭雅潔，柳晨光

(河北科技大學(xué)信息科學(xué)與工程學(xué)院，河北石家莊 050018)

CoDA算法是一種基于概率模型的能識(shí)別二分結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法。為了驗(yàn)證該算法的社區(qū)劃分效果，采用信息檢索領(lǐng)域的F-measure標(biāo)準(zhǔn)，對(duì)有向網(wǎng)絡(luò)下重疊社區(qū)和非重疊社區(qū)的CoDA社區(qū)發(fā)現(xiàn)算法進(jìn)行評(píng)估。F-measure標(biāo)準(zhǔn)中F1-measure值的大小能反映CoDA算法社區(qū)劃分效果的優(yōu)劣。實(shí)驗(yàn)所用的數(shù)據(jù)集由LFR Benchmark工具生成，數(shù)據(jù)集中節(jié)點(diǎn)數(shù)最小為100，最大為20 000，每增加100節(jié)點(diǎn)對(duì)CoDA算法社區(qū)劃分效果評(píng)估一次。分析實(shí)驗(yàn)結(jié)果可以得出，當(dāng)節(jié)點(diǎn)數(shù)小于1 600時(shí)，CoDA算法的劃分效果較好。當(dāng)節(jié)點(diǎn)數(shù)大于1 600時(shí)，隨著節(jié)點(diǎn)個(gè)數(shù)增多，CoDA算法社區(qū)劃分效果逐漸變差。由此說(shuō)明，基于概率模型的CoDA算法適用于小規(guī)模社交網(wǎng)絡(luò)社區(qū)的劃分。

算法理論；社區(qū)發(fā)現(xiàn)；CoDA算法；有向網(wǎng)絡(luò)；評(píng)估；F-measure

社區(qū)發(fā)現(xiàn)是在給定網(wǎng)絡(luò)中，將物理對(duì)象或抽象對(duì)象的集合分組為類(lèi)似對(duì)象組成的多個(gè)社區(qū)。社區(qū)發(fā)現(xiàn)可以應(yīng)用在許多領(lǐng)域，例如，在商業(yè)領(lǐng)域，社區(qū)發(fā)現(xiàn)可以用于對(duì)不同的客戶(hù)群分組，尋找潛在市場(chǎng)；在生物領(lǐng)域，社區(qū)發(fā)現(xiàn)可以用于對(duì)動(dòng)植物分類(lèi)和對(duì)基因分類(lèi)，獲取對(duì)種群固有結(jié)構(gòu)的認(rèn)識(shí)；在因特網(wǎng)領(lǐng)域，社區(qū)發(fā)現(xiàn)可以用來(lái)在網(wǎng)上進(jìn)行文檔歸類(lèi)，修正錯(cuò)誤信息；在保險(xiǎn)領(lǐng)域，社區(qū)發(fā)現(xiàn)可以用來(lái)對(duì)保險(xiǎn)單持有者的分組識(shí)別汽車(chē)保險(xiǎn)欺詐等。因此，社區(qū)發(fā)現(xiàn)算法在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用。

目前，許多學(xué)者從事社區(qū)發(fā)現(xiàn)研究，由于他們對(duì)節(jié)點(diǎn)集或者邊集進(jìn)行劃分時(shí)采取了不同標(biāo)準(zhǔn)，提出了多種多樣的社區(qū)發(fā)現(xiàn)算法。無(wú)向網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)算法分為圖論分區(qū)法[1-4]、鏈接分區(qū)法[5-7]、局部擴(kuò)張和優(yōu)化分區(qū)法[8-10]、模糊劃分法[11-13]和基于代理的分區(qū)法[14-15]5類(lèi)。隨著無(wú)向網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)算法的逐漸成熟，一些學(xué)者嘗試將無(wú)向網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法擴(kuò)展到有向網(wǎng)絡(luò)，以期利用已有的方法解決新問(wèn)題。例如，無(wú)向網(wǎng)絡(luò)中的DOCNet算法采用聚集系數(shù)計(jì)算節(jié)點(diǎn)的重要性，F(xiàn)AGIOLO[16]改進(jìn)了DOCNet算法，并將其擴(kuò)展到有向網(wǎng)絡(luò)中。NEWMAN 等[1]在無(wú)向網(wǎng)絡(luò)中建立了模塊度優(yōu)化算法——譜二分法，然后將其擴(kuò)展到有向網(wǎng)絡(luò)中，并提出有向網(wǎng)絡(luò)中模塊度的概念。NICOSIA 等[17]將有向網(wǎng)絡(luò)中模塊度概念進(jìn)行了擴(kuò)展，并將重疊社區(qū)考慮在內(nèi)。

隨著社區(qū)發(fā)現(xiàn)算法的不斷增多，如何衡量算法的優(yōu)劣成為了一個(gè)重要的問(wèn)題，因此，對(duì)社區(qū)發(fā)現(xiàn)算法的評(píng)估也成為了研究者關(guān)注的問(wèn)題。目前常用的社區(qū)發(fā)現(xiàn)算法評(píng)估方法可分為外部評(píng)估法和內(nèi)部評(píng)估法兩大類(lèi)。外部評(píng)估法是基于一種預(yù)先指定的結(jié)構(gòu)，反映了人們對(duì)數(shù)據(jù)集社區(qū)結(jié)構(gòu)的直觀認(rèn)識(shí)，主要包括正確率(Accuracy)[18]、Rand系數(shù)(Rand Index)[19]、Jaccard系數(shù)(Jaccard Index)[20]等指標(biāo)。內(nèi)部評(píng)估法是利用未知社區(qū)結(jié)構(gòu)固有特征和量值來(lái)評(píng)估一個(gè)社區(qū)發(fā)現(xiàn)算法的社區(qū)劃分效果，主要包括模塊度(Modularity)[1]和Coverage[21]等指標(biāo)。

CoDA(communities through directed affiliations)社區(qū)發(fā)現(xiàn)算法[22]是一個(gè)新的社區(qū)發(fā)現(xiàn)算法，它能對(duì)一種新型的網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行社區(qū)劃分。本文主要用F-measure標(biāo)準(zhǔn)對(duì)CoDA社區(qū)發(fā)現(xiàn)算法進(jìn)行詳細(xì)評(píng)估，以分析CoDA算法在不同節(jié)點(diǎn)數(shù)據(jù)集下社區(qū)劃分結(jié)果的變化規(guī)律。

1 CoDA社區(qū)發(fā)現(xiàn)算法的概述及實(shí)現(xiàn)

圖1 兩種類(lèi)型的網(wǎng)絡(luò)和兩種類(lèi)型的社區(qū)結(jié)構(gòu)Fig.1 Two types of networks and two types of community structures

CoDA社區(qū)發(fā)現(xiàn)算法是由斯坦福大學(xué)的Jaewon Yang等提出的，該算法引起關(guān)注的原因是它對(duì)社區(qū)結(jié)構(gòu)提出了一個(gè)更加新穎、全面的定義：有相似的連接模式的節(jié)點(diǎn)，即便它們不相連也可以組成一個(gè)社區(qū)。新的社區(qū)結(jié)構(gòu)的概念源于結(jié)構(gòu)對(duì)等的社會(huì)網(wǎng)絡(luò)文化，這一文化是指具有社會(huì)同質(zhì)性的節(jié)點(diǎn)不僅包括能連接到彼此的節(jié)點(diǎn)(即內(nèi)部組連接)，還包括以適當(dāng)方式連接到網(wǎng)絡(luò)中其他部分的節(jié)點(diǎn)(外部連接)。圖1表示出了兩種不同的社區(qū)概念。其中傳統(tǒng)的內(nèi)聚社區(qū)由社區(qū)內(nèi)部鏈接占據(jù)主導(dǎo)地位，且其內(nèi)部節(jié)點(diǎn)以雙向邊形式鏈接；而二分社區(qū)由社區(qū)間的單向鏈接占據(jù)主導(dǎo)地位。

CoDA社區(qū)發(fā)現(xiàn)算法在兩方面較為先進(jìn)：第一，該算法不僅可以發(fā)現(xiàn)內(nèi)聚社區(qū)還可以成功地發(fā)現(xiàn)二分社區(qū)；第二，該算法可以成功發(fā)現(xiàn)有向網(wǎng)絡(luò)中的重疊社區(qū)。

設(shè)B(V,C,M)是一個(gè)二分圖。其中V是節(jié)點(diǎn)集，C是社區(qū)集，M是將V和C連接在一起的邊集。該模型可以通過(guò)概率p(u,v)生成從節(jié)點(diǎn)u∈V到節(jié)點(diǎn)v∈V的有向邊，生成一個(gè)有向圖G(V,E)，其中E為邊的集合:

(1)

通過(guò)將有向關(guān)系網(wǎng)絡(luò)模型擬合到G(V,E)識(shí)別社區(qū)，即，使用最大似然法找到關(guān)系圖B和所有社區(qū)c∈C的概率集合{Pc}。

(2)

取對(duì)數(shù)得：

(3)

引入變量Muc和Lvc表示節(jié)點(diǎn)成員資格。用Muc表示節(jié)點(diǎn)u是否具有社區(qū)c的鏈出成員資格，取值為0或者1；Lvc表示節(jié)點(diǎn)v是否具有社區(qū)c的鏈入成員資格，取值為0或者1。因此，式(1)可以表示為

(4)

其中Cuv={c|(u,c),(c,v)∈M}，如果Cuv=?，則基礎(chǔ)邊緣概率為p(u,v)=1/|V|。

(1-pc)MucLvc表示只有當(dāng)節(jié)點(diǎn)u有社區(qū)c的鏈出成員資格，節(jié)點(diǎn)v有社區(qū)c的鏈入成員資格時(shí)取值為(1-pc)，否則為1。則∏c(1-pc)MucLvc只要其中一個(gè)社區(qū)c0使Muc0Lvc0=1，則∏c(1-pc)MucLvc≠1，則p(u,v)≠0。只要存在一個(gè)社區(qū)c0，節(jié)點(diǎn)u有其鏈入成員資格，節(jié)點(diǎn)v有其鏈出成員資格，就有可能存在有向邊〈u,v〉,且其概率可用式(4) 表示。

令1-pc=exp(-ac)，其中ac≥0。代入式(4)得，

(5)

(6)

(7)

式(3)可轉(zhuǎn)化為連續(xù)優(yōu)化問(wèn)題：

(8)

其中

(9)

使用最大似然法求出l(F,H)=logP(G|F,H)，取得最大值時(shí)的非負(fù)關(guān)系矩陣，來(lái)擬合有向關(guān)系網(wǎng)絡(luò)模型，以達(dá)到社區(qū)劃分的目的。

2 評(píng)估方法

評(píng)估方法借鑒了信息檢索領(lǐng)域中的F-measure標(biāo)準(zhǔn)[23]。F-measure包含準(zhǔn)確率和召回率兩方面。其中準(zhǔn)確率是檢索出相關(guān)文檔數(shù)與檢索出的文檔數(shù)的比率，衡量系統(tǒng)的查準(zhǔn)率；召回率是指檢索出的相關(guān)文檔數(shù)和文檔庫(kù)中所有相關(guān)文檔數(shù)的比率，衡量系統(tǒng)的查全率。本文將F-measure標(biāo)準(zhǔn)中的文檔數(shù)替換為節(jié)點(diǎn)對(duì)個(gè)數(shù)，進(jìn)而將F-measure標(biāo)準(zhǔn)應(yīng)用到社區(qū)發(fā)現(xiàn)算法的評(píng)估領(lǐng)域。F-measure可以很好地刻畫(huà)某社區(qū)發(fā)現(xiàn)算法對(duì)社交網(wǎng)絡(luò)的社區(qū)劃分結(jié)果與標(biāo)準(zhǔn)數(shù)據(jù)集中社區(qū)劃分結(jié)果的差異，在此用F-measure標(biāo)準(zhǔn)對(duì)CoDA社區(qū)發(fā)現(xiàn)算法進(jìn)行評(píng)估。

社區(qū)中節(jié)點(diǎn)對(duì)的歸屬情況見(jiàn)表1。其中：a表示原始數(shù)據(jù)集中屬于同一個(gè)真實(shí)社區(qū)，社區(qū)劃分后也屬于同一個(gè)社區(qū)中的節(jié)點(diǎn)對(duì)數(shù)目；b表示原始數(shù)據(jù)集中不屬于同一個(gè)真實(shí)社區(qū)，社區(qū)劃分后卻劃分到同一個(gè)社區(qū)中的節(jié)點(diǎn)對(duì)數(shù)目；c表示原始數(shù)據(jù)集中屬于同一個(gè)真實(shí)社區(qū)，社區(qū)劃分后卻沒(méi)被劃分到同一個(gè)社區(qū)中的節(jié)點(diǎn)

表1 社區(qū)劃分結(jié)果

對(duì)數(shù)目；d表示原始數(shù)據(jù)集中即不屬于同一個(gè)真實(shí)社區(qū)，社區(qū)劃分后也不屬于同一個(gè)社區(qū)中的節(jié)點(diǎn)對(duì)數(shù)目。

準(zhǔn)確率(Precision)是輸出結(jié)果中被劃分到同一社區(qū)的2個(gè)節(jié)點(diǎn)組成的節(jié)點(diǎn)對(duì)在數(shù)據(jù)集中屬于同一真實(shí)社區(qū)的比例，計(jì)算公式如式(10)所示：

(10)

召回率(Recall)是輸出結(jié)果中被劃分到同一社區(qū)中的2個(gè)節(jié)點(diǎn)且在數(shù)據(jù)集中屬于同一真實(shí)社區(qū)的節(jié)點(diǎn)對(duì)占劃分結(jié)果中社區(qū)內(nèi)所有節(jié)點(diǎn)對(duì)的比例，計(jì)算公式如式(11)所示：

(11)

準(zhǔn)確率與召回率都只能反映算法單方面的性質(zhì)，且這2個(gè)參數(shù)往往有相反的變化趨勢(shì)，而F1-measure 將準(zhǔn)確率與召回率進(jìn)行綜合考慮，能夠反映算法的綜合性能。其定義如式(12)所示:

(12)

2.1 評(píng)估程序流程圖

圖2 評(píng)估程序流程圖Fig.2 Flow chart of evaluation procedure

評(píng)估程序流程圖如圖2所示，本程序采用Java語(yǔ)言實(shí)現(xiàn)。該評(píng)估方法為外部評(píng)估法，其特點(diǎn)是標(biāo)準(zhǔn)社區(qū)結(jié)構(gòu)已知。首先，讀取數(shù)據(jù)集中的標(biāo)準(zhǔn)社區(qū)結(jié)構(gòu)文件，得到標(biāo)準(zhǔn)社區(qū)結(jié)構(gòu)中社區(qū)編號(hào)與其包含節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系HashMap〈String, LinkedList〈String〉〉communities。其次，根據(jù)得到的標(biāo)準(zhǔn)社區(qū)情況communities分社區(qū)遍歷，構(gòu)造標(biāo)準(zhǔn)社區(qū)中的節(jié)點(diǎn)對(duì)HashSet〈String〉nodePairInReal。然后，讀取被某算法處理后的社區(qū)情況，構(gòu)造處理后社區(qū)中的節(jié)點(diǎn)對(duì)nodePairInBack，在此過(guò)程中判斷每個(gè)節(jié)點(diǎn)是否包含在真實(shí)社區(qū)的節(jié)點(diǎn)對(duì) nodePairInReal之中，如果存在，則構(gòu)造既包含在真實(shí)社區(qū)中又在某算法處理后的社區(qū)中的節(jié)點(diǎn)對(duì)nodePairCorrect，同時(shí)，將此節(jié)點(diǎn)從nodePairInReal中移除。其中節(jié)點(diǎn)對(duì)指位于同一社區(qū)中的2個(gè)節(jié)點(diǎn)的組合。其中nodePairCorrect對(duì)應(yīng)表1中a，nodePairInBack對(duì)應(yīng)表1中b，nodePairInReal對(duì)應(yīng)表1中c。最后根據(jù)式(10)—式(12)依次計(jì)算出準(zhǔn)確率、召回率和 F1-measure的值。

2.2 有向網(wǎng)絡(luò)下重疊社區(qū)CoDA算法的評(píng)估

實(shí)驗(yàn)所用有向網(wǎng)絡(luò)下重疊社區(qū)的標(biāo)準(zhǔn)數(shù)據(jù)集由LFRBenchmark[24]生成。數(shù)據(jù)集中節(jié)點(diǎn)平均度數(shù)為 10，最大度數(shù)為50，混合參數(shù)為0.2，社區(qū)最小尺寸為20，最大尺寸為100，40%的重疊節(jié)點(diǎn)，且每個(gè)重疊節(jié)點(diǎn)同時(shí)屬于 4 個(gè)社區(qū)。節(jié)點(diǎn)數(shù)從100 到20 000，每100個(gè)節(jié)點(diǎn)進(jìn)行一次測(cè)試。評(píng)估結(jié)果如圖3和圖4所示。其中圖3表示鏈入成員的評(píng)估結(jié)果，圖4表示鏈出成員的評(píng)估結(jié)果。

圖3 鏈入成員評(píng)估結(jié)果圖Fig.3 Evaluation result of incoming members

圖4 鏈出成員評(píng)估結(jié)果圖Fig.4 Evaluation result of outgoing members

通過(guò)實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，在有向網(wǎng)絡(luò)帶重疊社區(qū)的情況下，相同節(jié)點(diǎn)數(shù)據(jù)集的鏈入成員資格和鏈出成員資格之間的準(zhǔn)確率、召回率和F1-measure幾乎相等。數(shù)據(jù)集節(jié)點(diǎn)數(shù)在1 600以?xún)?nèi)時(shí)，CoDA社區(qū)發(fā)現(xiàn)算法的社區(qū)劃分效果比較好，F(xiàn)1-measure在0.4以上。鏈入成員在節(jié)點(diǎn)為700時(shí)CoDA社區(qū)劃分效果最好，此時(shí)F1-measure達(dá)到0.524；鏈出成員在節(jié)點(diǎn)為1 200時(shí)CoDA社區(qū)劃分效果最好，此時(shí)F1-measure達(dá)到0.506。當(dāng)數(shù)據(jù)集節(jié)點(diǎn)數(shù)超過(guò)1 700時(shí)，隨著節(jié)點(diǎn)的不斷增多，召回率不斷升高，且趨近于1；但是準(zhǔn)確率不斷下降，且趨近于0.1；F1-measure呈明顯下降趨勢(shì)，其值趨近與0.1。當(dāng)節(jié)點(diǎn)數(shù)超過(guò)10 000時(shí)，F(xiàn)1-measure一直處于0.1以下，故圖中未給出評(píng)估結(jié)果。

2.3 有向網(wǎng)絡(luò)下非重疊社區(qū)CoDA算法的評(píng)估

數(shù)據(jù)集生成過(guò)程及數(shù)據(jù)集節(jié)點(diǎn)數(shù)的選取同2.2，節(jié)點(diǎn)平均度數(shù)、最大度數(shù)、混合參數(shù)、社區(qū)最小尺寸和最大尺寸等沒(méi)有改變，只將重疊節(jié)點(diǎn)的個(gè)數(shù)和每個(gè)重疊節(jié)點(diǎn)屬于的社區(qū)數(shù)調(diào)整為0。評(píng)估結(jié)果如圖5和圖6所示。

圖5 鏈入成員評(píng)估結(jié)果圖Fig.5 Evaluation result of incoming members

圖6 鏈出成員評(píng)估結(jié)果圖Fig.6 Evaluation result of outgoing members

通過(guò)對(duì)有向網(wǎng)絡(luò)下非重疊社區(qū)CoDA算法的評(píng)估可以發(fā)現(xiàn)，在相同節(jié)點(diǎn)數(shù)據(jù)集下，鏈入成員資格和鏈出成員資格之間的準(zhǔn)確率、召回率和F1-measure幾乎相等。隨著節(jié)點(diǎn)的不斷增多，召回率不斷升高，準(zhǔn)確率和F1-measure在不斷下降。這說(shuō)明隨著節(jié)點(diǎn)的增多，標(biāo)準(zhǔn)社區(qū)結(jié)構(gòu)中不在同一社區(qū)的節(jié)點(diǎn)對(duì)經(jīng)過(guò)CoDA算法處理后，被劃分到同一社區(qū)的數(shù)量越來(lái)越多。標(biāo)準(zhǔn)社區(qū)結(jié)構(gòu)中在同一社區(qū)的節(jié)點(diǎn)對(duì)經(jīng)過(guò)CoDA算法處理后，被劃分到2個(gè)不同社區(qū)的數(shù)量越來(lái)越少。到達(dá)10 000節(jié)點(diǎn)后，幾乎所有屬于同一ci社區(qū)的節(jié)點(diǎn)對(duì)都不會(huì)被劃分到不同的社區(qū)內(nèi)。數(shù)據(jù)集節(jié)點(diǎn)數(shù)量較小時(shí)，其綜合性能較好；隨著數(shù)據(jù)集節(jié)點(diǎn)數(shù)量的增多，其綜合性能在逐漸變差。

分別對(duì)比有向網(wǎng)絡(luò)下的重疊社區(qū)和非重疊社區(qū)的CoDA社區(qū)發(fā)現(xiàn)算法實(shí)驗(yàn)結(jié)果可知，相同節(jié)點(diǎn)的數(shù)據(jù)集下，重疊社區(qū)和非重疊社區(qū)之間的準(zhǔn)確率、召回率和F1-measure相差很小，這說(shuō)明CoDA社區(qū)發(fā)現(xiàn)算法在分別處理重疊社區(qū)和非重疊社區(qū)時(shí)，其穩(wěn)定性非常好。

3 結(jié) 論

1) 將信息檢索領(lǐng)域中的F-measure評(píng)價(jià)標(biāo)準(zhǔn)應(yīng)用于社區(qū)發(fā)現(xiàn)算法的評(píng)估領(lǐng)域。既屬于標(biāo)準(zhǔn)社區(qū)又屬于某算法劃分后，社區(qū)中的節(jié)點(diǎn)對(duì)數(shù)對(duì)應(yīng)F-measure評(píng)價(jià)標(biāo)準(zhǔn)中檢索出的相關(guān)文檔數(shù)替換為算法劃分后，社區(qū)中的節(jié)點(diǎn)對(duì)數(shù)對(duì)應(yīng)該標(biāo)準(zhǔn)中檢索出的文檔數(shù)，真實(shí)社區(qū)中的節(jié)點(diǎn)對(duì)數(shù)對(duì)應(yīng)該標(biāo)準(zhǔn)中文檔庫(kù)中所有相關(guān)文檔數(shù)。通過(guò)實(shí)驗(yàn)可知，F(xiàn)-measure可以很好地刻畫(huà)某社區(qū)發(fā)現(xiàn)算法對(duì)社交網(wǎng)絡(luò)的社區(qū)劃分結(jié)果與標(biāo)準(zhǔn)數(shù)據(jù)集中社區(qū)劃分結(jié)果的差異，因此可以將該標(biāo)準(zhǔn)應(yīng)用到有向網(wǎng)絡(luò)下重疊社區(qū)和非重疊社區(qū)的挖掘算法評(píng)估領(lǐng)域。

2)在研究社交網(wǎng)絡(luò)結(jié)構(gòu)的過(guò)程中，一個(gè)準(zhǔn)確的社區(qū)概念至關(guān)重要。傳統(tǒng)模型認(rèn)為“社區(qū)”是密集連接節(jié)點(diǎn)的集合。CoDA算法考慮了二分社區(qū)結(jié)構(gòu)，它將一組在網(wǎng)絡(luò)中沒(méi)有直接鏈接，但鏈接在同一個(gè)坐標(biāo)的節(jié)點(diǎn)組合在一起。該算法能識(shí)別有向網(wǎng)絡(luò)下的重疊二分社區(qū)。當(dāng)數(shù)據(jù)集節(jié)點(diǎn)數(shù)小于1 600時(shí)，CoDA算法社區(qū)劃分效果較好且穩(wěn)定，但是當(dāng)節(jié)點(diǎn)數(shù)超過(guò)該值時(shí)，隨著數(shù)據(jù)集節(jié)點(diǎn)數(shù)的增多，社區(qū)劃分效果逐漸變差。因此，基于概率模型的CoDA社區(qū)發(fā)現(xiàn)算法適用于數(shù)據(jù)集規(guī)模較小時(shí)社交網(wǎng)絡(luò)的劃分，不適用于大規(guī)模社交網(wǎng)絡(luò)的社區(qū)劃分。

/References:

[1] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69:026113.

[2] YANG J, LESKOVEC J. Overlapping community detection at scale: A nonnegative matrix factorization approach[C]// Proceedings of the Sixth ACM International Conference on Web Search and Data Mining. New York:ACM,2013:587-596.

[3] MAKINO K, UNO T. New algorithms for enumerating all maximal cliques[C]//9th Scandinavian Workshop on Algorithm Theory. Berlin:Springer, 2004:260-272.

[4] PALLA G, DERéNYI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435:814-818.

[5] EVANS T S, LAMBIOTTE R. Line graphs, link partitions, and overlapping communities[J]. Physical Review E, 2009, 80:016105.

[6] AHN Y Y, BAGROW J P, LEHMANN S. Communities and hierarchical organization of links in complex networks[J]. Nature, 2009, 466:761-764.

[7] WU Zhihao, LIN Youfang, WAN Huaiyu, et al. A fast and reasonable method for community detection with adjustable extent of overlapping[C]// 2010 International Conference on Intelligent Systems and Knowledge Engineering (ISKE).[S.l.]: IEEE Xplore, 2010:376-379.

[8] ANDREA L, FILIPPO R, RAMASCO J J, et al. Finding statistically significant communities in networks[J]. Inorganic Materials, 2002, 38(4):336-338.

[9] LANCICHINETTI A, FORTUNATO S, KERTéSZ J. Detecting the overlapping and hierarchical community structure of complex networks[J]. New Journal of Physics, 2008, 11(3):19-44.

[10]SHEN Huawei, CHENG Xueqi, CAI Kai, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A:Statistical Mechanics & Its Applications, 2009, 388(8):1706-1712.

[11]LU Yinghua, MA Tinghuai, YIN Changhong, et al. Implementation of the fuzzy C-means clustering algorithm in meteorological data[J]. International Journal of Database Theory & Application, 2013, 6(6):1-18.

[12]NEPUSZ T, PETRCZI A, NéGYESSY L, et al. Fuzzy communities and the concept of bridgeness in complex networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2008, 77:016107.

[13]PSORAKIS I, ROBERTS S, EBDEN M, et al. Overlapping community detection using Bayesian non-negative matrix factorization[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2011, 83:066114.

[14]XIE J, SZYMANSKI B K, LIU X M. SLPA: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C]//2011 IEEE 11th International Conference on Data Mining Workshops(ICDMW). Vancouver: IEEE, 2011:344-349.

[15]RHOUMA D, ROMDHANE L B. An efficient algorithm for community mining with overlap in social networks[J]. Expert Systems with Applications, 2014, 41(9):4309-4321.

[16]FAGIOLO G. Clustering in complex directed networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2007, 76:026107.

[17]NICOSIA V, MANGIONI G, CARCHIOLO V, et al. Extending the definition of modularity to directed graphs with overlapping communities[J]. Journal of Statistical Mechanics Theory & Experiment, 2009 (3):3166-3168.

[18]STEINHAEUSER K, CHAWLA N V. Identifying and evaluating community structure in complex networks[J]. Pattern Recognition Letters, 2010, 31(5):413-421.

[19]RAND W M. Objective criteria for the evaluation of clustering methods[J]. Journal of the American Statistical Association, 1971, 66:846-850.

[20]BEN-HUR A, ELISSEEFF A, GUYON I. A stability based method for discovering structure in clustered data[J]. Pacific Symposium on Biocomputing Pacific Symposium on Biocomputing, 2002(7):6-17.

[21]BRANDES U, GAERTLER M, WAGNER D. Experiments on Graph Clustering Algorithms[M]. Berlin: Springer, 2003:568-579.

[22]YANG J, MCAULEY J, LESKOVEC J. Detecting cohesive and 2-mode communities indirected and undirected networks[C]// Proceedings of the 7th ACM International Conference on Web Search and Data Mining. New York:WSDM, 2014:323-332.

[23]萬(wàn)里. 時(shí)間序列中的知識(shí)發(fā)現(xiàn):基于頻繁模式發(fā)現(xiàn)的分類(lèi)和聚類(lèi)方法研究[D]. 北京:北京郵電大學(xué), 2009. WAN Li. Knowledge Discovery in Time Series：Researches on Classification and Clustering Based on Frequent Pattern Discovery[D]. Beijing: Beijing University of Posts and Telecommunications, 2009.

[24]LANCICHINETTI A, FORTUNATO S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2009, 80:016118.

Evaluation of the CoDA community detection algorithm based on directed network

GUO Song, ZHANG Dongwen, XU Yunfeng, YANG Yulin, ZHENG Yajie, LIU Chenguang

(School of Information Science and Engineering, Hebei University of Science and Technology, Shijiazhuang, Hebei 050018, China)

CoDA (Communities through Directed Affiliations) algorithm is a kind of community detection algorithm which can successfully detect 2-mode communities based on probability model. TheF-measure criterion, for information retrieval, is adapted to the evaluation of CoDA algorithm in directed networks with overlapping communities or non-overlapping communities. The value ofF1-measure inF-measure criterion can reflect whether CoDA algorithm performs well or not. The data sets used in the experiment is generated by the LFR Benchmark tool. The minimum number of nodes in data set is 100 and the maximum is 20 000, and evaluated experiment is conducted when every 100 nodes is added. The results show that CoDA algorithm performs well when the number of nodes is bellow 1 600. CoDA algorithm's performance becomes worse with the increase of the number of nodes, which proves the CoDA algorithm based on probability model is applicable to the community detection of small-scale networks.

theory of algorithm; community detection; CoDA algorithm; directed networks; evaluate;F-measure

1008-1542(2017)02-0169-07

10.7535/hbkd.2017yx02011

2016-09-23；

2017-03-06；責(zé)任編輯：陳書(shū)欣

國(guó)家自然科學(xué)基金(71271076)

郭 松(1991—)，男，河北石家莊人，碩士研究生，主要從事聚類(lèi)、社區(qū)發(fā)現(xiàn)方面的研究。

張冬雯教授。E-mail：zdwwtx@163.com

TP391.1

A

郭 松，張冬雯，許云峰，等.有向網(wǎng)絡(luò)下的CoDA社區(qū)發(fā)現(xiàn)算法評(píng)估[J].河北科技大學(xué)學(xué)報(bào),2017,38(2):169-175.

GUO Song,ZHANG Dongwen,XU Yunfeng，et al.Evaluation of the CoDA community detection algorithm based on directed network[J].Journal of Hebei University of Science and Technology,2017,38(2):169-175.