基于稠密子圖的社區發現算法

鄭文萍，張浩杰，王杰

(1.山西大學 計算機與信息技術學院，山西 太原 030006； 2.山西大學 計算智能與中文信息處理教育部重點實驗室，山西 太原 030006)

?

基于稠密子圖的社區發現算法

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

(1.山西大學 計算機與信息技術學院，山西 太原 030006； 2.山西大學 計算智能與中文信息處理教育部重點實驗室，山西 太原 030006)

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

關鍵詞：復雜網絡；社區發現；圖聚類；軟聚類；密度；中心擴展策略；點介數；模塊性

近年來，對各種復雜網絡的研究是許多領域的研究熱點之一[1-3]，如生物網絡、社交網絡、電子郵件網絡、引文網絡等已成為眾多學者的主要研究對象。大量研究表明，復雜網絡中存在著一種普遍特征——社區結構[4]。復雜網絡中社區發現[5]不僅有助于深入研究整個網絡的拓撲結構、功能模塊以及動力學特性，同時在生物蛋白質的性能與互作用的分析[6]、社會組織結構的網絡分析[7]、搜索引擎[8]及推薦系統[9]等方面均有廣泛的應用前景，因此具有十分重要的理論意義和應用價值。

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

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

1背景知識

(1)

通常一個結點的點介數越大，則該結點對網絡結構的影響越大。點介數是網絡中結點重要性度量指標之一。

2結點對社區的歸屬度定義

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

圖1　空手道俱樂部中未聚類結點分析Fig.1　The analysis of subordinate vertices in zachary’s karate club

因此，度量未聚類結點和已有社區的歸屬度，需要綜合考慮該結點與一個社區關聯邊數以及社區內該結點的相鄰結點的重要性。為了更準確地表示未聚類結點和社區的關系，首先給出結點v對社區C的歸屬度定義：

(2)

表1不同α值時聚類結果的比較

Table 1The comparison of the clustering results among differentα

數據集未聚類節點Qα=0.8α=1α=0.8α=1空手道俱樂部130.82050.7179海豚社交網絡010.77350.7610大學生足球網絡000.63900.6150電子郵件網絡34410.72240.7151合作網絡6576610.78280.6473

3基于稠密子圖的社區發現算法

基于稠密子圖的社區發現算法(BDSG)主要由2部分構成：首先通過搜索網絡中大于指定密度閾值d的稠密子圖得到網絡中心社區，確定聚類個數k，不屬于任何一個中心社區的結點為未聚類結點；根據式(2)計算未聚類結點與已有社區的歸屬度，將一些未聚類結點劃分到歸屬度大于指定閾值的社區中，對當前中心社區進行擴展；更新剩余未聚類結點的歸屬度，若網絡中所有未聚類結點對任意社區的歸屬度都小于設定閾值，則算法結束。

3.1確定聚類個數

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

進行稠密子圖合并操作后可得到2個初始中心社區：C1=[U1∪U2]G，C2=[U3∪U4]G，聚類個數k=2。

算法確定了聚類個數和初始中心社區數之后，不屬于任何中心社區的結點就是未聚類結點。由于初始中心社區尋找過程中關注于網絡中相對稠密的子圖，網絡中存在大量未聚類結點，需要設計合理的中心社區擴展策略，對未聚類結點進一步處理。

3.2中心社區擴展策略

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

圖3給出了BDSG算法在空手道俱樂部數據集上的聚類結果，共得到2個社區，空白結點表示未聚類結點。

4實驗與結果分析

為了分析研究BDSG算法在真實網絡中社區發現的有效性，將BDSG算法分別應用于空手道俱樂部(Karate)[23]、海豚社交網絡(Dolphin)[24]、大學生足球網絡(Football)[25]、電子郵件網絡(Email)[26]和合作網絡(NetScience)[27]等5個數據集。實驗所用計算機配置為Inter Core i5 CPU 2.5 GHz，6 GB內存，Windows 7操作系統。程序采用java編程語言并在Eclipse環境下運行。依經驗選擇密度閾值d=0.9，調節參數α=0.8。

圖3～5分別給出了本文BDSG算法在空手道俱樂部、海豚社交網絡和大學生足球網絡的聚類結果。表2給出了BDSG算法與CPM、k-dense算法分別在聚類個數、未聚類結點數、社區模塊性(Q)[28]以及運行時間等方面的比較結果。

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

圖4　BDSG算法在海豚社交網絡上得到的聚類結果Fig.4　Clustering results on dolphins social network obtained by BDSG

圖5　BDSG算法在大學生足球網絡上得到的聚類結果Fig.5　Clustering results on college football network obtained by BDSG

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

實驗結果表明BDSG算法在這些網絡數據上均具有較好的性能表現。BDSG算法在空手道俱樂部和大學生足球網絡上所得到社區個數與網絡實際的社區個數相同，而電子郵件網絡和合作網絡缺乏原始社區個數信息，無法進行比較；海豚社交網絡和大學生足球網絡中，BDSG算法所用時間明顯少于CPM與k-dense算法；在電子郵件網絡和合作網絡中，BDSG運行時間比k-dense算法慢，但最終未聚類結點數少于k-dense算法；在這些實驗數據集上，本算法所產生的未聚類結點個數明顯較少、社區模塊性較高。

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

綜上所述，BDSG算法在空手道俱樂部、海豚社交網絡、大學生足球網絡、電子郵件網絡和合作網絡等數據集上，與CPM、k-dense算法相比運行時間較短、未聚類結點個數較少、社區模塊性較高，具有良好的聚類性能。同時，中心社區擴展算法可以有效地提高CPM、k-dense算法的聚類性能，該算法也可用于其他非結點完全覆蓋算法。

5結束語

本文提出一種基于稠密子圖的圖聚類算法BDSG，解決了基于密度算法中大量未聚類結點問題。通過搜索網絡中的相對稠密子圖得到中心社區；通過定義結點對社區的歸屬度來度量結點和社區連接傾向性，進而給出一種中心社區擴展策略對中心社區外結點進行聚類。通過與CPM、k-dense算法在5個真實網絡數據集上進行分析比較，結果表明，BDSG算法在未聚類結點個數、模塊性及運行時間方面均表現出較好的性能。同時中心社區擴展策略與其他算法相結合，對提高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, 等. 復雜網絡聚類方法[J]. 軟件學報, 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]冀俊忠, 劉志軍, 劉紅欣, 等. 蛋白質相互作用網絡功能模塊檢測的研究綜述[J]. 自動化學報, 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]陳克寒, 韓盼盼, 吳健. 基于用戶聚類的異構社交網絡推薦算法[J]. 計算機學報, 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年生，女，副教授，中國計算機學會會員，主要研究方向為圖論算法、生物信息學等。主持多項國家級項目，發表學術論文多篇。

張浩杰，1991年8月生，男，碩士研究生，主要研究方向為數據挖掘、圖聚類等。

王杰，1988年8月生，男，博士研究生，主要研究方向為數據挖掘，生物信息學。

中文引用格式：鄭文萍，張浩杰，王杰.基于稠密子圖的社區發現算法[J]. 智能系統學報， 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

文獻標志碼：A

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

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

基金項目：國家自然科學基金項目(61572005，61272004)，山西省煤基重點科技攻關項目(MQ2014-09).

收稿日期：2016-03-19.網絡出版日期：2016-05-13.

DOI:10.11992.tis.201603045

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160513.0923.022.html