鄭文萍,張浩杰,王杰
(1.山西大學(xué) 計算機與信息技術(shù)學(xué)院,山西 太原 030006; 2.山西大學(xué) 計算智能與中文信息處理教育部重點實驗室,山西 太原 030006)
?
基于稠密子圖的社區(qū)發(fā)現(xiàn)算法
鄭文萍1,2,張浩杰1,王杰1,2
(1.山西大學(xué) 計算機與信息技術(shù)學(xué)院,山西 太原 030006; 2.山西大學(xué) 計算智能與中文信息處理教育部重點實驗室,山西 太原 030006)
摘要:基于密度的圖聚類算法在社區(qū)發(fā)現(xiàn)中得到了廣泛應(yīng)用,然而由于其通過搜索網(wǎng)絡(luò)中局部稠密子圖來識別社區(qū),使得大量結(jié)點因不能構(gòu)成稠密子圖而未被聚類。針對此問題,給出了一種基于稠密子圖的軟聚類算法(community detection based dense subgraphs,BDSG)。首先給出一種中心社區(qū)發(fā)現(xiàn)方法;進而定義了一種結(jié)點的社區(qū)歸屬度,并給出中心社區(qū)擴展策略;最終得到聚類結(jié)果。通過與CPM(clique percolation method)、k-dense算法在空手道俱樂部、海豚社交網(wǎng)絡(luò)、大學(xué)生足球網(wǎng)絡(luò)、電子郵件網(wǎng)絡(luò)和合作網(wǎng)絡(luò)等數(shù)據(jù)進行比較,表明BDSG算法在模塊性指標(biāo)與時間效率方面體現(xiàn)了良好性能, 同時中心社區(qū)擴展策略能在一定程度上提高CPM、k-dense等基于密度算法的聚類有效性。
關(guān)鍵詞:復(fù)雜網(wǎng)絡(luò);社區(qū)發(fā)現(xiàn);圖聚類;軟聚類;密度;中心擴展策略;點介數(shù);模塊性
近年來,對各種復(fù)雜網(wǎng)絡(luò)的研究是許多領(lǐng)域的研究熱點之一[1-3],如生物網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、電子郵件網(wǎng)絡(luò)、引文網(wǎng)絡(luò)等已成為眾多學(xué)者的主要研究對象。大量研究表明,復(fù)雜網(wǎng)絡(luò)中存在著一種普遍特征——社區(qū)結(jié)構(gòu)[4]。復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)[5]不僅有助于深入研究整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、功能模塊以及動力學(xué)特性,同時在生物蛋白質(zhì)的性能與互作用的分析[6]、社會組織結(jié)構(gòu)的網(wǎng)絡(luò)分析[7]、搜索引擎[8]及推薦系統(tǒng)[9]等方面均有廣泛的應(yīng)用前景,因此具有十分重要的理論意義和應(yīng)用價值。
目前,社區(qū)發(fā)現(xiàn)算法的研究主要分為基于圖劃分的聚類算法[10-11]、基于譜分析的聚類算法[12]、基于層次的聚類算法[13]和基于密度的聚類算法[14]等。其中基于密度的聚類算法通過搜索網(wǎng)絡(luò)中稠密子圖[15]能較好地發(fā)現(xiàn)網(wǎng)絡(luò)中的功能模塊,因此在社區(qū)發(fā)現(xiàn)中得到了廣泛應(yīng)用。2005年,Palla等[16]提出派系過濾算法(clique percolation method,CPM),首先挖掘網(wǎng)絡(luò)中結(jié)點數(shù)大于k的所有派系(完全圖),然后將重疊結(jié)點大于k-1的派系合并得到k派系社區(qū)。2006年,Saito等[17]提出k-dense子圖結(jié)構(gòu),通過尋找網(wǎng)絡(luò)中的k-dense結(jié)構(gòu)進行社區(qū)檢測。2009年,Sun等[18]以CPM為基礎(chǔ),通過改進尋找派系的方法提高算法效率,提出迭代派系過濾算法(iterative-clique percolation method,ICPM)。2010年,Liu等[19]提出基于極大團的聚類算法(clustering-based on maximal cliques,CMC),通過搜索網(wǎng)絡(luò)中的所有極大團,并依據(jù)相互連接度合并重疊率較高的極大團得到網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。由于這些算法要搜索網(wǎng)絡(luò)中的相對稠密子圖來進行聚類,當(dāng)網(wǎng)絡(luò)中存在包含大量結(jié)點的稀疏子圖時,這些結(jié)點可能最終成為未聚類結(jié)點,造成了聚類結(jié)果的不完全覆蓋。這些未聚類結(jié)點構(gòu)成的稀疏子圖可能具有某種功能,或者與某些稠密子圖共同行使功能,因此需要對網(wǎng)絡(luò)中的部分未聚類結(jié)點進行進一步分析,判斷其是否屬于某一社區(qū)或形成新的社區(qū)。
針對基于密度算法中大量未聚類結(jié)點問題,提出一種基于稠密子圖的社區(qū)發(fā)現(xiàn)算法(community detection based on dense subgraphs,BDSG)。首先通過搜索網(wǎng)絡(luò)中的相對稠密子圖得到中心社區(qū);對于未聚類結(jié)點,定義了結(jié)點v對社區(qū)C的歸屬度b(v,C)來度量結(jié)點和社區(qū)的連接傾向程度;基于歸屬度,給出一種中心社區(qū)擴展策略(core community extended strategy, CE),對未聚類結(jié)點進一步處理。BDSG算法中,一個結(jié)點可能屬于多個社區(qū),是一種軟聚類方法。通過在空手道俱樂部、海豚社交網(wǎng)絡(luò)、大學(xué)生足球網(wǎng)絡(luò)、電子郵件網(wǎng)絡(luò)和合作網(wǎng)絡(luò)5個真實網(wǎng)絡(luò)上與CPM、k-dense算法進行比較,評估和分析BDSG算法在未聚類結(jié)點分配和社區(qū)模塊性等方面的性能表現(xiàn)?;跉w屬度的中心社區(qū)擴展策略也將應(yīng)用在CPM、k-dense等基于密度的圖聚類算法中,對未聚類結(jié)點進一步處理,以提高聚類有效性。
1背景知識
(1)
通常一個結(jié)點的點介數(shù)越大,則該結(jié)點對網(wǎng)絡(luò)結(jié)構(gòu)的影響越大。點介數(shù)是網(wǎng)絡(luò)中結(jié)點重要性度量指標(biāo)之一。
2結(jié)點對社區(qū)的歸屬度定義
基于密度的圖聚類算法中可能存在大量不屬于任何已有社區(qū)的未聚類結(jié)點,為了將這些結(jié)點聚類到合適的社區(qū),需要定義未聚類結(jié)點和社區(qū)的關(guān)聯(lián)強度,稱為結(jié)點v對于社區(qū)C的歸屬度b(v,C)。歸屬度的定義對聚類結(jié)果的影響至關(guān)重要,結(jié)點v對于社區(qū)C的歸屬度越大,則結(jié)點v屬于社區(qū)C的可能性越大。
圖1 空手道俱樂部中未聚類結(jié)點分析Fig.1 The analysis of subordinate vertices in zachary’s karate club
因此,度量未聚類結(jié)點和已有社區(qū)的歸屬度,需要綜合考慮該結(jié)點與一個社區(qū)關(guān)聯(lián)邊數(shù)以及社區(qū)內(nèi)該結(jié)點的相鄰結(jié)點的重要性。為了更準(zhǔn)確地表示未聚類結(jié)點和社區(qū)的關(guān)系,首先給出結(jié)點v對社區(qū)C的歸屬度定義:
(2)
表1不同α值時聚類結(jié)果的比較
Table 1The comparison of the clustering results among differentα
數(shù)據(jù)集未聚類節(jié)點Qα=0.8α=1α=0.8α=1空手道俱樂部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)成:首先通過搜索網(wǎng)絡(luò)中大于指定密度閾值d的稠密子圖得到網(wǎng)絡(luò)中心社區(qū),確定聚類個數(shù)k,不屬于任何一個中心社區(qū)的結(jié)點為未聚類結(jié)點;根據(jù)式(2)計算未聚類結(jié)點與已有社區(qū)的歸屬度,將一些未聚類結(jié)點劃分到歸屬度大于指定閾值的社區(qū)中,對當(dāng)前中心社區(qū)進行擴展;更新剩余未聚類結(jié)點的歸屬度,若網(wǎng)絡(luò)中所有未聚類結(jié)點對任意社區(qū)的歸屬度都小于設(shè)定閾值,則算法結(jié)束。
3.1確定聚類個數(shù)
首先,尋找網(wǎng)絡(luò)中的子圖密度大于指定閾值d的所有稠密子圖。圖2給出了d=0.9時,算法得到的4個稠密子圖,分別記為U1、U2、U3和U4。
進行稠密子圖合并操作后可得到2個初始中心社區(qū):C1=[U1∪U2]G,C2=[U3∪U4]G,聚類個數(shù)k=2。
算法確定了聚類個數(shù)和初始中心社區(qū)數(shù)之后,不屬于任何中心社區(qū)的結(jié)點就是未聚類結(jié)點。由于初始中心社區(qū)尋找過程中關(guān)注于網(wǎng)絡(luò)中相對稠密的子圖,網(wǎng)絡(luò)中存在大量未聚類結(jié)點,需要設(shè)計合理的中心社區(qū)擴展策略,對未聚類結(jié)點進一步處理。
3.2中心社區(qū)擴展策略
算法1中心社區(qū)擴展算法 (core community extended strategy,CE)
圖3給出了BDSG算法在空手道俱樂部數(shù)據(jù)集上的聚類結(jié)果,共得到2個社區(qū),空白結(jié)點表示未聚類結(jié)點。
4實驗與結(jié)果分析
為了分析研究BDSG算法在真實網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)的有效性,將BDSG算法分別應(yīng)用于空手道俱樂部(Karate)[23]、海豚社交網(wǎng)絡(luò)(Dolphin)[24]、大學(xué)生足球網(wǎng)絡(luò)(Football)[25]、電子郵件網(wǎng)絡(luò)(Email)[26]和合作網(wǎng)絡(luò)(NetScience)[27]等5個數(shù)據(jù)集。實驗所用計算機配置為Inter Core i5 CPU 2.5 GHz,6 GB內(nèi)存,Windows 7操作系統(tǒng)。程序采用java編程語言并在Eclipse環(huán)境下運行。依經(jīng)驗選擇密度閾值d=0.9,調(diào)節(jié)參數(shù)α=0.8。
圖3~5分別給出了本文BDSG算法在空手道俱樂部、海豚社交網(wǎng)絡(luò)和大學(xué)生足球網(wǎng)絡(luò)的聚類結(jié)果。表2給出了BDSG算法與CPM、k-dense算法分別在聚類個數(shù)、未聚類結(jié)點數(shù)、社區(qū)模塊性(Q)[28]以及運行時間等方面的比較結(jié)果。
圖3 BDSG算法在空手道俱樂部得到的聚類結(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ù)集頂點數(shù)邊數(shù)原始社區(qū)個數(shù)算法聚類個數(shù)未聚類節(jié)點數(shù)Q運行時間/ms空手道俱樂部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
實驗結(jié)果表明BDSG算法在這些網(wǎng)絡(luò)數(shù)據(jù)上均具有較好的性能表現(xiàn)。BDSG算法在空手道俱樂部和大學(xué)生足球網(wǎng)絡(luò)上所得到社區(qū)個數(shù)與網(wǎng)絡(luò)實際的社區(qū)個數(shù)相同,而電子郵件網(wǎng)絡(luò)和合作網(wǎng)絡(luò)缺乏原始社區(qū)個數(shù)信息,無法進行比較;海豚社交網(wǎng)絡(luò)和大學(xué)生足球網(wǎng)絡(luò)中,BDSG算法所用時間明顯少于CPM與k-dense算法;在電子郵件網(wǎng)絡(luò)和合作網(wǎng)絡(luò)中,BDSG運行時間比k-dense算法慢,但最終未聚類結(jié)點數(shù)少于k-dense算法;在這些實驗數(shù)據(jù)集上,本算法所產(chǎn)生的未聚類結(jié)點個數(shù)明顯較少、社區(qū)模塊性較高。
此外,本文給出的中心社區(qū)擴展算法也可應(yīng)用于CPM、k-dense等算法以處理未聚類節(jié)點,提高聚類性能。實驗結(jié)果(見表2)表明CPM與k-dense算法的聚類有效性均顯著提高。在空手道俱樂部、海豚社交網(wǎng)絡(luò)、電子郵件網(wǎng)絡(luò)和合作網(wǎng)絡(luò)中,在CPM與k-dense算法運行時間略有增大的情況下,CE算法的加入使得其未聚類結(jié)點個數(shù)降幅較大,社區(qū)模塊性具有較為明顯的提高。同時CPM與k-dense算法在加入擴展策略CE之后與BDSG算法相比, BDSG算法在未聚類結(jié)點數(shù)以及社區(qū)模塊性方面優(yōu)勢依然較為明顯。
綜上所述,BDSG算法在空手道俱樂部、海豚社交網(wǎng)絡(luò)、大學(xué)生足球網(wǎng)絡(luò)、電子郵件網(wǎng)絡(luò)和合作網(wǎng)絡(luò)等數(shù)據(jù)集上,與CPM、k-dense算法相比運行時間較短、未聚類結(jié)點個數(shù)較少、社區(qū)模塊性較高,具有良好的聚類性能。同時,中心社區(qū)擴展算法可以有效地提高CPM、k-dense算法的聚類性能,該算法也可用于其他非結(jié)點完全覆蓋算法。
5結(jié)束語
本文提出一種基于稠密子圖的圖聚類算法BDSG,解決了基于密度算法中大量未聚類結(jié)點問題。通過搜索網(wǎng)絡(luò)中的相對稠密子圖得到中心社區(qū);通過定義結(jié)點對社區(qū)的歸屬度來度量結(jié)點和社區(qū)連接傾向性,進而給出一種中心社區(qū)擴展策略對中心社區(qū)外結(jié)點進行聚類。通過與CPM、k-dense算法在5個真實網(wǎng)絡(luò)數(shù)據(jù)集上進行分析比較,結(jié)果表明,BDSG算法在未聚類結(jié)點個數(shù)、模塊性及運行時間方面均表現(xiàn)出較好的性能。同時中心社區(qū)擴展策略與其他算法相結(jié)合,對提高CPM、k-dense等算法的聚類性能具有一定的適用性。
參考文獻:
[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é)報, 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ò)功能模塊檢測的研究綜述[J]. 自動化學(xué)報, 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]. 計算機學(xué)報, 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年生,女,副教授,中國計算機學(xué)會會員,主要研究方向為圖論算法、生物信息學(xué)等。主持多項國家級項目,發(fā)表學(xué)術(shù)論文多篇。
張浩杰,1991年8月生,男,碩士研究生,主要研究方向為數(shù)據(jù)挖掘、圖聚類等。
王杰,1988年8月生,男,博士研究生,主要研究方向為數(shù)據(jù)挖掘,生物信息學(xué)。
中文引用格式:鄭文萍,張浩杰,王杰.基于稠密子圖的社區(qū)發(fā)現(xiàn)算法[J]. 智能系統(tǒng)學(xué)報, 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
作者簡介:
中圖分類號:TP18
文獻標(biāo)志碼:A
文章編號:1673-4785(2016)03-0426-07.
通信作者:鄭文萍. E-mail: wpzheng@sxu.edu.cn.
基金項目:國家自然科學(xué)基金項目(61572005,61272004),山西省煤基重點科技攻關(guān)項目(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