基于稠密子圖的社區(qū)發(fā)現(xiàn)算法

鄭文萍，張浩杰，王杰

(1.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006； 2.山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，山西 太原 030006)

?

基于稠密子圖的社區(qū)發(fā)現(xiàn)算法

鄭文萍1,2，張浩杰1，王杰1,2

(1.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006； 2.山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，山西 太原 030006)

摘要：基于密度的圖聚類算法在社區(qū)發(fā)現(xiàn)中得到了廣泛應(yīng)用，然而由于其通過(guò)搜索網(wǎng)絡(luò)中局部稠密子圖來(lái)識(shí)別社區(qū)，使得大量結(jié)點(diǎn)因不能構(gòu)成稠密子圖而未被聚類。針對(duì)此問(wèn)題，給出了一種基于稠密子圖的軟聚類算法(community detection based dense subgraphs，BDSG)。首先給出一種中心社區(qū)發(fā)現(xiàn)方法；進(jìn)而定義了一種結(jié)點(diǎn)的社區(qū)歸屬度，并給出中心社區(qū)擴(kuò)展策略；最終得到聚類結(jié)果。通過(guò)與CPM(clique percolation method)、k-dense算法在空手道俱樂(lè)部、海豚社交網(wǎng)絡(luò)、大學(xué)生足球網(wǎng)絡(luò)、電子郵件網(wǎng)絡(luò)和合作網(wǎng)絡(luò)等數(shù)據(jù)進(jìn)行比較，表明BDSG算法在模塊性指標(biāo)與時(shí)間效率方面體現(xiàn)了良好性能, 同時(shí)中心社區(qū)擴(kuò)展策略能在一定程度上提高CPM、k-dense等基于密度算法的聚類有效性。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；社區(qū)發(fā)現(xiàn)；圖聚類；軟聚類；密度；中心擴(kuò)展策略；點(diǎn)介數(shù)；模塊性

近年來(lái)，對(duì)各種復(fù)雜網(wǎng)絡(luò)的研究是許多領(lǐng)域的研究熱點(diǎn)之一[1-3]，如生物網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、電子郵件網(wǎng)絡(luò)、引文網(wǎng)絡(luò)等已成為眾多學(xué)者的主要研究對(duì)象。大量研究表明，復(fù)雜網(wǎng)絡(luò)中存在著一種普遍特征——社區(qū)結(jié)構(gòu)[4]。復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)[5]不僅有助于深入研究整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、功能模塊以及動(dòng)力學(xué)特性，同時(shí)在生物蛋白質(zhì)的性能與互作用的分析[6]、社會(huì)組織結(jié)構(gòu)的網(wǎng)絡(luò)分析[7]、搜索引擎[8]及推薦系統(tǒng)[9]等方面均有廣泛的應(yīng)用前景，因此具有十分重要的理論意義和應(yīng)用價(jià)值。

目前，社區(qū)發(fā)現(xiàn)算法的研究主要分為基于圖劃分的聚類算法[10-11]、基于譜分析的聚類算法[12]、基于層次的聚類算法[13]和基于密度的聚類算法[14]等。其中基于密度的聚類算法通過(guò)搜索網(wǎng)絡(luò)中稠密子圖[15]能較好地發(fā)現(xiàn)網(wǎng)絡(luò)中的功能模塊，因此在社區(qū)發(fā)現(xiàn)中得到了廣泛應(yīng)用。2005年，Palla等[16]提出派系過(guò)濾算法(clique percolation method，CPM)，首先挖掘網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)大于k的所有派系(完全圖)，然后將重疊結(jié)點(diǎn)大于k-1的派系合并得到k派系社區(qū)。2006年，Saito等[17]提出k-dense子圖結(jié)構(gòu)，通過(guò)尋找網(wǎng)絡(luò)中的k-dense結(jié)構(gòu)進(jìn)行社區(qū)檢測(cè)。2009年，Sun等[18]以CPM為基礎(chǔ)，通過(guò)改進(jìn)尋找派系的方法提高算法效率，提出迭代派系過(guò)濾算法(iterative-clique percolation method，ICPM)。2010年，Liu等[19]提出基于極大團(tuán)的聚類算法(clustering-based on maximal cliques，CMC)，通過(guò)搜索網(wǎng)絡(luò)中的所有極大團(tuán)，并依據(jù)相互連接度合并重疊率較高的極大團(tuán)得到網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。由于這些算法要搜索網(wǎng)絡(luò)中的相對(duì)稠密子圖來(lái)進(jìn)行聚類，當(dāng)網(wǎng)絡(luò)中存在包含大量結(jié)點(diǎn)的稀疏子圖時(shí)，這些結(jié)點(diǎn)可能最終成為未聚類結(jié)點(diǎn)，造成了聚類結(jié)果的不完全覆蓋。這些未聚類結(jié)點(diǎn)構(gòu)成的稀疏子圖可能具有某種功能，或者與某些稠密子圖共同行使功能，因此需要對(duì)網(wǎng)絡(luò)中的部分未聚類結(jié)點(diǎn)進(jìn)行進(jìn)一步分析，判斷其是否屬于某一社區(qū)或形成新的社區(qū)。

針對(duì)基于密度算法中大量未聚類結(jié)點(diǎn)問(wèn)題，提出一種基于稠密子圖的社區(qū)發(fā)現(xiàn)算法(community detection based on dense subgraphs，BDSG)。首先通過(guò)搜索網(wǎng)絡(luò)中的相對(duì)稠密子圖得到中心社區(qū)；對(duì)于未聚類結(jié)點(diǎn)，定義了結(jié)點(diǎn)v對(duì)社區(qū)C的歸屬度b(v,C)來(lái)度量結(jié)點(diǎn)和社區(qū)的連接傾向程度；基于歸屬度，給出一種中心社區(qū)擴(kuò)展策略(core community extended strategy, CE)，對(duì)未聚類結(jié)點(diǎn)進(jìn)一步處理。BDSG算法中，一個(gè)結(jié)點(diǎn)可能屬于多個(gè)社區(qū)，是一種軟聚類方法。通過(guò)在空手道俱樂(lè)部、海豚社交網(wǎng)絡(luò)、大學(xué)生足球網(wǎng)絡(luò)、電子郵件網(wǎng)絡(luò)和合作網(wǎng)絡(luò)5個(gè)真實(shí)網(wǎng)絡(luò)上與CPM、k-dense算法進(jìn)行比較，評(píng)估和分析BDSG算法在未聚類結(jié)點(diǎn)分配和社區(qū)模塊性等方面的性能表現(xiàn)。基于歸屬度的中心社區(qū)擴(kuò)展策略也將應(yīng)用在CPM、k-dense等基于密度的圖聚類算法中，對(duì)未聚類結(jié)點(diǎn)進(jìn)一步處理，以提高聚類有效性。

1背景知識(shí)

(1)

通常一個(gè)結(jié)點(diǎn)的點(diǎn)介數(shù)越大，則該結(jié)點(diǎn)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響越大。點(diǎn)介數(shù)是網(wǎng)絡(luò)中結(jié)點(diǎn)重要性度量指標(biāo)之一。

2結(jié)點(diǎn)對(duì)社區(qū)的歸屬度定義

基于密度的圖聚類算法中可能存在大量不屬于任何已有社區(qū)的未聚類結(jié)點(diǎn)，為了將這些結(jié)點(diǎn)聚類到合適的社區(qū)，需要定義未聚類結(jié)點(diǎn)和社區(qū)的關(guān)聯(lián)強(qiáng)度，稱為結(jié)點(diǎn)v對(duì)于社區(qū)C的歸屬度b(v,C)。歸屬度的定義對(duì)聚類結(jié)果的影響至關(guān)重要，結(jié)點(diǎn)v對(duì)于社區(qū)C的歸屬度越大，則結(jié)點(diǎn)v屬于社區(qū)C的可能性越大。

圖1　空手道俱樂(lè)部中未聚類結(jié)點(diǎn)分析Fig.1　The analysis of subordinate vertices in zachary’s karate club

因此，度量未聚類結(jié)點(diǎn)和已有社區(qū)的歸屬度，需要綜合考慮該結(jié)點(diǎn)與一個(gè)社區(qū)關(guān)聯(lián)邊數(shù)以及社區(qū)內(nèi)該結(jié)點(diǎn)的相鄰結(jié)點(diǎn)的重要性。為了更準(zhǔn)確地表示未聚類結(jié)點(diǎn)和社區(qū)的關(guān)系，首先給出結(jié)點(diǎn)v對(duì)社區(qū)C的歸屬度定義：

(2)

表1不同α值時(shí)聚類結(jié)果的比較

Table 1The comparison of the clustering results among differentα

數(shù)據(jù)集未聚類節(jié)點(diǎn)Qα=0.8α=1α=0.8α=1空手道俱樂(lè)部130.82050.7179海豚社交網(wǎng)絡(luò)010.77350.7610大學(xué)生足球網(wǎng)絡(luò)000.63900.6150電子郵件網(wǎng)絡(luò)34410.72240.7151合作網(wǎng)絡(luò)6576610.78280.6473

3基于稠密子圖的社區(qū)發(fā)現(xiàn)算法

基于稠密子圖的社區(qū)發(fā)現(xiàn)算法(BDSG)主要由2部分構(gòu)成：首先通過(guò)搜索網(wǎng)絡(luò)中大于指定密度閾值d的稠密子圖得到網(wǎng)絡(luò)中心社區(qū)，確定聚類個(gè)數(shù)k，不屬于任何一個(gè)中心社區(qū)的結(jié)點(diǎn)為未聚類結(jié)點(diǎn)；根據(jù)式(2)計(jì)算未聚類結(jié)點(diǎn)與已有社區(qū)的歸屬度，將一些未聚類結(jié)點(diǎn)劃分到歸屬度大于指定閾值的社區(qū)中，對(duì)當(dāng)前中心社區(qū)進(jìn)行擴(kuò)展；更新剩余未聚類結(jié)點(diǎn)的歸屬度，若網(wǎng)絡(luò)中所有未聚類結(jié)點(diǎn)對(duì)任意社區(qū)的歸屬度都小于設(shè)定閾值，則算法結(jié)束。

3.1確定聚類個(gè)數(shù)

首先，尋找網(wǎng)絡(luò)中的子圖密度大于指定閾值d的所有稠密子圖。圖2給出了d=0.9時(shí)，算法得到的4個(gè)稠密子圖，分別記為U1、U2、U3和U4。

進(jìn)行稠密子圖合并操作后可得到2個(gè)初始中心社區(qū)：C1=[U1∪U2]G，C2=[U3∪U4]G，聚類個(gè)數(shù)k=2。

算法確定了聚類個(gè)數(shù)和初始中心社區(qū)數(shù)之后，不屬于任何中心社區(qū)的結(jié)點(diǎn)就是未聚類結(jié)點(diǎn)。由于初始中心社區(qū)尋找過(guò)程中關(guān)注于網(wǎng)絡(luò)中相對(duì)稠密的子圖，網(wǎng)絡(luò)中存在大量未聚類結(jié)點(diǎn)，需要設(shè)計(jì)合理的中心社區(qū)擴(kuò)展策略，對(duì)未聚類結(jié)點(diǎn)進(jìn)一步處理。

3.2中心社區(qū)擴(kuò)展策略

算法1中心社區(qū)擴(kuò)展算法 (core community extended strategy，CE)

圖3給出了BDSG算法在空手道俱樂(lè)部數(shù)據(jù)集上的聚類結(jié)果，共得到2個(gè)社區(qū)，空白結(jié)點(diǎn)表示未聚類結(jié)點(diǎn)。

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

為了分析研究BDSG算法在真實(shí)網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)的有效性，將BDSG算法分別應(yīng)用于空手道俱樂(lè)部(Karate)[23]、海豚社交網(wǎng)絡(luò)(Dolphin)[24]、大學(xué)生足球網(wǎng)絡(luò)(Football)[25]、電子郵件網(wǎng)絡(luò)(Email)[26]和合作網(wǎng)絡(luò)(NetScience)[27]等5個(gè)數(shù)據(jù)集。實(shí)驗(yàn)所用計(jì)算機(jī)配置為Inter Core i5 CPU 2.5 GHz，6 GB內(nèi)存，Windows 7操作系統(tǒng)。程序采用java編程語(yǔ)言并在Eclipse環(huán)境下運(yùn)行。依經(jīng)驗(yàn)選擇密度閾值d=0.9，調(diào)節(jié)參數(shù)α=0.8。

圖3～5分別給出了本文BDSG算法在空手道俱樂(lè)部、海豚社交網(wǎng)絡(luò)和大學(xué)生足球網(wǎng)絡(luò)的聚類結(jié)果。表2給出了BDSG算法與CPM、k-dense算法分別在聚類個(gè)數(shù)、未聚類結(jié)點(diǎn)數(shù)、社區(qū)模塊性(Q)[28]以及運(yùn)行時(shí)間等方面的比較結(jié)果。

圖3　BDSG算法在空手道俱樂(lè)部得到的聚類結(jié)果Fig.3　Clustering results on zachary’s karate club obtained by BDSG

圖4　BDSG算法在海豚社交網(wǎng)絡(luò)上得到的聚類結(jié)果Fig.4　Clustering results on dolphins social network obtained by BDSG

圖5　BDSG算法在大學(xué)生足球網(wǎng)絡(luò)上得到的聚類結(jié)果Fig.5　Clustering results on college football network obtained by BDSG

數(shù)據(jù)集頂點(diǎn)數(shù)邊數(shù)原始社區(qū)個(gè)數(shù)算法聚類個(gè)數(shù)未聚類節(jié)點(diǎn)數(shù)Q運(yùn)行時(shí)間/ms空手道俱樂(lè)部34782BDSG210.820593CPM3220.192387k-dense2220.2948129CPM+CE330.4102117k-dense+CE210.8205165海豚社交網(wǎng)絡(luò)621592BDSG400.7735149CPM4340.4088175k-dense43404088568CPM+CE4160.5911202k-dense+CE4160.5911599大學(xué)生足球網(wǎng)絡(luò)11561312BDSG1200.6390480CPM1320.5951920k-dense1220.63701860CPM+CE1300.60101028k-dense+CE1200.64801986電子郵件網(wǎng)絡(luò)11335451—BDSG28340.722460797CPM555620.2687592410k-dense65580.251755240CPM+CE553410.2897601835k-dense+CE6140.503463938合作網(wǎng)絡(luò)15892742—BDSG1346570.782821273CPM1598430.520197161k-dense918430.730515352CPM+CE1596880.5675120927k-dense+CE917900.763123451

實(shí)驗(yàn)結(jié)果表明BDSG算法在這些網(wǎng)絡(luò)數(shù)據(jù)上均具有較好的性能表現(xiàn)。BDSG算法在空手道俱樂(lè)部和大學(xué)生足球網(wǎng)絡(luò)上所得到社區(qū)個(gè)數(shù)與網(wǎng)絡(luò)實(shí)際的社區(qū)個(gè)數(shù)相同，而電子郵件網(wǎng)絡(luò)和合作網(wǎng)絡(luò)缺乏原始社區(qū)個(gè)數(shù)信息，無(wú)法進(jìn)行比較；海豚社交網(wǎng)絡(luò)和大學(xué)生足球網(wǎng)絡(luò)中，BDSG算法所用時(shí)間明顯少于CPM與k-dense算法；在電子郵件網(wǎng)絡(luò)和合作網(wǎng)絡(luò)中，BDSG運(yùn)行時(shí)間比k-dense算法慢，但最終未聚類結(jié)點(diǎn)數(shù)少于k-dense算法；在這些實(shí)驗(yàn)數(shù)據(jù)集上，本算法所產(chǎn)生的未聚類結(jié)點(diǎn)個(gè)數(shù)明顯較少、社區(qū)模塊性較高。

此外，本文給出的中心社區(qū)擴(kuò)展算法也可應(yīng)用于CPM、k-dense等算法以處理未聚類節(jié)點(diǎn)，提高聚類性能。實(shí)驗(yàn)結(jié)果(見(jiàn)表2)表明CPM與k-dense算法的聚類有效性均顯著提高。在空手道俱樂(lè)部、海豚社交網(wǎng)絡(luò)、電子郵件網(wǎng)絡(luò)和合作網(wǎng)絡(luò)中，在CPM與k-dense算法運(yùn)行時(shí)間略有增大的情況下，CE算法的加入使得其未聚類結(jié)點(diǎn)個(gè)數(shù)降幅較大，社區(qū)模塊性具有較為明顯的提高。同時(shí)CPM與k-dense算法在加入擴(kuò)展策略CE之后與BDSG算法相比， BDSG算法在未聚類結(jié)點(diǎn)數(shù)以及社區(qū)模塊性方面優(yōu)勢(shì)依然較為明顯。

綜上所述，BDSG算法在空手道俱樂(lè)部、海豚社交網(wǎng)絡(luò)、大學(xué)生足球網(wǎng)絡(luò)、電子郵件網(wǎng)絡(luò)和合作網(wǎng)絡(luò)等數(shù)據(jù)集上，與CPM、k-dense算法相比運(yùn)行時(shí)間較短、未聚類結(jié)點(diǎn)個(gè)數(shù)較少、社區(qū)模塊性較高，具有良好的聚類性能。同時(shí)，中心社區(qū)擴(kuò)展算法可以有效地提高CPM、k-dense算法的聚類性能，該算法也可用于其他非結(jié)點(diǎn)完全覆蓋算法。

5結(jié)束語(yǔ)

本文提出一種基于稠密子圖的圖聚類算法BDSG，解決了基于密度算法中大量未聚類結(jié)點(diǎn)問(wèn)題。通過(guò)搜索網(wǎng)絡(luò)中的相對(duì)稠密子圖得到中心社區(qū)；通過(guò)定義結(jié)點(diǎn)對(duì)社區(qū)的歸屬度來(lái)度量結(jié)點(diǎn)和社區(qū)連接傾向性，進(jìn)而給出一種中心社區(qū)擴(kuò)展策略對(duì)中心社區(qū)外結(jié)點(diǎn)進(jìn)行聚類。通過(guò)與CPM、k-dense算法在5個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行分析比較，結(jié)果表明，BDSG算法在未聚類結(jié)點(diǎn)個(gè)數(shù)、模塊性及運(yùn)行時(shí)間方面均表現(xiàn)出較好的性能。同時(shí)中心社區(qū)擴(kuò)展策略與其他算法相結(jié)合，對(duì)提高CPM、k-dense等算法的聚類性能具有一定的適用性。

參考文獻(xiàn):

[1]FORTUNATO S. Community detection in graphs[J]. Physics reports, 2010, 486(3/4/5): 75-174.

[2]NEPUSZ T, YU Haiyuan, PACCANARO A. Detecting overlapping protein complexes in protein-protein interaction networks[J]. Nature methods, 2012, 9(5): 471-472.

[3]DEYLAMI H A, ASADPOUR M. Link prediction in social networks using hierarchical community detection[C]//Proceedings of the 7th conference on information and knowledge technology. Urmia, Iran, 2015: 1-5.

[4]SCHAEFFER S E. Graph clustering[J]. Computer science review, 2007, 1(1): 27-64.

[5]楊博, 劉大有, LIU Jiming, 等. 復(fù)雜網(wǎng)絡(luò)聚類方法[J]. 軟件學(xué)報(bào), 2009, 20(1): 54-66.

YANG Bo, LIU Dayou, LIU Jiming, et al. Complex network clustering algorithms[J]. Journal of software, 2009, 20(1): 54-66.

[6]冀俊忠, 劉志軍, 劉紅欣, 等. 蛋白質(zhì)相互作用網(wǎng)絡(luò)功能模塊檢測(cè)的研究綜述[J]. 自動(dòng)化學(xué)報(bào), 2014, 40(4): 577-593.

JI Junzhong, LIU Zhijun, LIU Hongxin, et al. An overview of research on functional module detection for protein-protein interaction networks[J]. Acta automatica sinica, 2014, 40(4): 577-593.

[7]PALLA G, BARABáSI A L, VICSEK T. Quantifying social group evolution[J]. Nature, 2007, 446(7136): 664-667.

[8]SIDIROPOULOS A, PALLIS G, KATSAROS D, et al. Prefetching in content distribution networks via web communities identification and outsourcing[J]. World wide web, 2008, 11(1): 39-70.

[9]陳克寒, 韓盼盼, 吳健. 基于用戶聚類的異構(gòu)社交網(wǎng)絡(luò)推薦算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(2): 349-359.

CHEN Kehan, HAN Panpan, WU Jian. User clustering based social network recommendation[J]. Chinese journal of computers, 2013, 36(2): 349-359.

[10]FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972-976.

[11]NEWMAN M E J. Community detection and graph partitioning[J]. Europhysics letters, 2013, 103(2): 28003.

[12]NEWMAN M E J. Spectral methods for community detection and graph partitioning[J]. Physical review E, 2013, 88(4): 042822.

[13]LIN Chuncheng, KANG Jiarong, CHEN J Y. An integer programming approach and visual analysis for detecting hierarchical community structures in social networks[J]. Information sciences, 2015, 299: 296-311.

[14]REN Jun, WANG Jianxin, LI Min, et al. Identifying protein complexes based on density and modularity in protein-protein interaction network[J]. BMC systems biology, 2013, 7(S4): S12.

[15]LI Xiaoli, FOO C S, NG S K. Discovering protein complexes in dense reliable neighborhoods of protein interaction networks[C]//Proceedings of the computational systems bioinformatics conference. San Diego, USA, 2007, 6: 157-168.

[16]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.

[17]SAITO K, YAMADA T, KAZAMA K. Extracting communities from complex networks by the k-dense method[J]. IEICE transactions on fundamentals of electronics, communications and computer sciences, 2008, E91-A(11): 3304-3311.

[18]SUN Penggang, GAO Lin. Fast algorithms for detecting overlapping functional modules in protein-protein interaction networks[C]//Proceedings of the IEEE computational intelligence in bioinformatics and computational biology. Nashville, TN, USA, 2009: 247-254.

[19]LIU Guimei, WONG L, CHUA H N. Complex discovery from weighted PPI networks[J]. Bioinformatics, 2009, 25(15): 1891-1897.

[20]BADER G D, HOGUE C W V. An automated method for finding molecular complexes in large protein interaction networks[J]. BMC bioinformatics, 2003, 4(1): 2.

[21]FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35-41.

[22]CUI Yaizu, WANG Xingyuan, EUSTACE J. Detecting community structure via the maximal sub-graphs and belonging degrees in complex networks[J]. Physica A: statistical mechanics and its applications, 2014, 416: 198-207.

[23]ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of anthropological research, 1977, 33(4): 452-473.

[24]LUSSEAU D, SCHNEIDER K, BOISSEAU O J, et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations: Can geographic isolation explain this unique trait[J]. Behavioral ecology and sociobiology, 2003, 54(4): 396-405.

[25]NEWMAN M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical review E, 2006, 74(3): 036104.

[26]GUIMERà R, DANON L, DíAZ-GUILERA A, et al. Self-similar community structure in a network of human interactions[J]. Physical review E, 2003, 68(6): 065103.

[27]NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical review E, 2004, 69(2): 026113.

[28]SHEN Huawei, CHENG Xueqi, CAI Kai, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A: statistical mechanics and its applications, 2009, 388(8): 1706-1712.

鄭文萍，1979年生，女，副教授，中國(guó)計(jì)算機(jī)學(xué)會(huì)會(huì)員，主要研究方向?yàn)閳D論算法、生物信息學(xué)等。主持多項(xiàng)國(guó)家級(jí)項(xiàng)目，發(fā)表學(xué)術(shù)論文多篇。

張浩杰，1991年8月生，男，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘、圖聚類等。

王杰，1988年8月生，男，博士研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘，生物信息學(xué)。

中文引用格式：鄭文萍，張浩杰，王杰.基于稠密子圖的社區(qū)發(fā)現(xiàn)算法[J]. 智能系統(tǒng)學(xué)報(bào)， 2016, 11(3): 426-432.

英文引用格式：ZHENG Wenping， ZHANG Haojie， WANG Jie. Community detection algorithm based on dense subgraphs[J]. CAAI transactions on intelligent systems, 2016,11(3): 426-432.

Community detection algorithm based on dense subgraphs

ZHENG Wenping1,2， ZHANG Haojie1， WANG Jie1,2

(1. School of Computer and Information Technology, Shanxi University, Taiyuan 030006, China; 2. Key Laboratory of Computation Intelligence and Chinese Information Processing, Ministry of Education, Shanxi University, Taiyuan 030006, China)

Abstract：The density-based graph clustering algorithm has been widely used in community detection. However, because it identifies a community by searching a partially dense subgraph in the network, many nodes do not constitute a dense subgraph and are therefore difficult to cluster. In this paper, we present a soft clustering algorithm based on dense subgraphs (BDSG) for detecting communities in complex networks. First, we propose a method for detecting the central communities. Next, we define the degree of community attribution of a node, and put forward a core community extended strategy. Finally, we obtain the clustering results of a network. Compared with the clique percolation method (CPM), k-dense algorithms from Zachary's Karate Club, the dolphin social network, the American college football network, the email network, and the collaboration network, BDSG shows considerably better performance with respect to modularity and time efficiency. In addition, the proposed core community extended strategy may improve the effectiveness of the clustering-methods-based density, such as that in CPM, k-dense algorithms, and others.

Keywords：complex network; community detection; graph clustering; soft clustering; density; core extended strategy; vertex betweenness; modularity

作者簡(jiǎn)介：

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

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

文章編號(hào)：1673-4785(2016)03-0426-07.

通信作者：鄭文萍. E-mail: wpzheng@sxu.edu.cn.

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61572005，61272004)，山西省煤基重點(diǎn)科技攻關(guān)項(xiàng)目(MQ2014-09).

收稿日期：2016-03-19.網(wǎng)絡(luò)出版日期：2016-05-13.

DOI:10.11992.tis.201603045

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160513.0923.022.html