第3期 郑文萍，等：基于稠密子图的社区发现算法 ·431. 好的聚类性能。同时，中心社区扩展算法可以有效 CHEN Kehan,HAN Panpan,WU Jian.User clustering 地提高CPM、k-dense算法的聚类性能，该算法也可 based social network recommendation[]].Chinese journal of 用于其他非结点完全覆盖算法。 computers,.2013,36(2):349-359. [10]FREY B J,DUECK D.Clustering by passing messages be- 5结束语 tween data points[J].Science,2007,315(5814):972- 976. 本文提出一种基于稠密子图的图聚类算法 [11]NEWMAN M E J.Community detection and graph partitio- BDSG,解决了基于密度算法中大量未聚类结点问 ning[]Europhysics letters,2013,103(2):28003. 题。通过搜索网络中的相对稠密子图得到中心社 [12]NEWMAN M E J.Spectral methods for community detec- 区：通过定义结点对社区的归属度来度量结点和社 tion and graph partitioning[J].Physical review E,2013, 区连接倾向性，进而给出一种中心社区扩展策略对 88(4)：042822. 中心社区外结点进行聚类。通过与CPM、k-dense算 [13]LIN Chuncheng,KANG Jiarong,CHEN J Y.An integer 法在5个真实网络数据集上进行分析比较，结果表 programming approach and visual analysis for detecting hi- 明，BDSG算法在未聚类结点个数、模块性及运行时 erarchical community structures in social networks[J].In- 间方面均表现出较好的性能。同时中心社区扩展策 formation sciences,2015,299:296-311. 略与其他算法相结合，对提高CPM、k-dense等算法 [14]REN Jun,WANG Jianxin,LI Min,et al.Identifying pro- tein 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 comple- [1]FORTUNATO S.Community detection in graphs[J].Phys- xes in dense reliable neighborhoods of protein interaction ics reports,2010,486(3/4/5):75-174. networks[C]//Proceedings of the computational systems [2]NEPUSZ T,YU Haiyuan,PACCANARO A.Detecting over- bioinformatics conference.San Diego,USA,2007,6: lapping protein complexes in protein-protein interaction net- 157-168. works[J.Nature methods,2012,9(5):471-472. [16]PALLA G,DEReNYI I,FARKAS I,et al.Uncovering the [3]DEYLAMI H A,ASADPOUR M.Link prediction in social overlapping community structure of complex networks in networks using hierarchical community detectionC//Pro- nature and society J.Nature,2005,435:814-818. ceedings of the 7th conference on information and knowledge [17]SAITO K,YAMADA T,KAZAMA K.Extracting commu- technology.Urmia,Iran,2015:1-5. nities from complex networks by the k-dense method[J]. [4]SCHAEFFER S E.Graph clustering[J].Computer science IEICE transactions on fundamentals of electronics,commu- review,2007,1(1):27-64. nications and computer sciences,2008,E91-A (11 ) [5]杨博，刘大有，U Jiming,等.复杂网络聚类方法[J]. 3304-3311. 软件学报，2009,20(1)：54-66. [18]SUN Penggang,GAO Lin.Fast algorithms for detecting o- YANG Bo,LIU Dayou,LIU Jiming,et al.Complex network verlapping functional modules in protein-protein interaction clustering algorithms [J].Journal of software,2009,20 networks[C]//Proceedings of the IEEE computational in- (1):54-66. telligence in bioinformatics and computational biology. [6]冀俊忠，刘志军，刘红欣，等.蛋白质相互作用网络功 Nashville,TN,USA,2009:247-254. 能模块检测的研究综述[J].自动化学报，2014,40(4)： [19]LIU Guimei,WONG L,CHUA H N.Complex discovery 577.593. from weighted PPI networks[J].Bioinformatics,2009,25 JI Junzhong,LIU Zhijun,LIU Hongxin,et al.An overview (15):1891-1897. of research on functional module detection for protein-protein [20]BADER G D,HOGUE C W V.An automated method for interaction networks J.Acta automatica sinica,2014,40 finding molecular complexes in large protein interaction (4):577-593 networks[.BMC bioinformatics,2003,4(1):2. [7]PALLA G,BARABASI A L,VICSEK T.Quantifying social [21]FREEMAN L C.A set of measures of centrality based on group evolution[J].Nature,2007,446(7136):664-667. betweenness[J].Sociometry,1977,40(1):35-41. [8]SIDIROPOULOS A,PALLIS G,KATSAROS D,et al.Pre- [22 CUI Yaizu,WANG Xingyuan,EUSTACE J.Detecting fetching in content distribution networks via web communi- community structure via the maximal sub-graphs and be- ties identification and outsourcing[J].World wide web, longing degrees in complex networks[J].Physica A:sta- 2008,11(1):39-70. tistical mechanics and its applications,2014,416:198- [9]陈克寒，韩盼盼，吴健.基于用户聚类的异构社交网络 207. 推荐算法[J].计算机学报，2013,36(2)：349-359. [23]ZACHARY WW.An information flow model for conflict好的聚类性能。 同时，中心社区扩展算法可以有效 地提高 ＣＰＭ、ｋ⁃ｄｅｎｓｅ 算法的聚类性能，该算法也可 用于其他非结点完全覆盖算法。 ５ 结束语 本文提出一种基于稠密子图的图聚类算法 ＢＤＳＧ，解决了基于密度算法中大量未聚类结点问 题。 通过搜索网络中的相对稠密子图得到中心社 区；通过定义结点对社区的归属度来度量结点和社 区连接倾向性，进而给出一种中心社区扩展策略对 中心社区外结点进行聚类。 通过与 ＣＰＭ、ｋ⁃ｄｅｎｓｅ 算 法在 ５ 个真实网络数据集上进行分析比较，结果表 明，ＢＤＳＧ 算法在未聚类结点个数、模块性及运行时 间方面均表现出较好的性能。 同时中心社区扩展策 略与其他算法相结合，对提高 ＣＰＭ、ｋ⁃ｄｅｎｓｅ 等算法 的聚类性能具有一定的适用性。 参考文献： ［１］ＦＯＲＴＵＮＡＴＯ Ｓ． Ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ｉｎ ｇｒａｐｈｓ［ Ｊ］． Ｐｈｙｓ⁃ ｉｃｓ ｒｅｐｏｒｔｓ， ２０１０， ４８６（３ ／ ４ ／ ５）： ７５⁃１７４． ［２］ＮＥＰＵＳＺ Ｔ， ＹＵ Ｈａｉｙｕａｎ， ＰＡＣＣＡＮＡＲＯ Ａ． Ｄｅｔｅｃｔｉｎｇ ｏｖｅｒ⁃ ｌａｐｐｉｎｇ ｐｒｏｔｅｉｎ ｃｏｍｐｌｅｘｅｓ ｉｎ ｐｒｏｔｅｉｎ⁃ｐｒｏｔｅｉｎ ｉｎｔｅｒａｃｔｉｏｎ ｎｅｔ⁃ ｗｏｒｋｓ［Ｊ］． Ｎａｔｕｒｅ ｍｅｔｈｏｄｓ， ２０１２， ９（５）： ４７１⁃４７２． ［３］ＤＥＹＬＡＭＩ Ｈ Ａ， ＡＳＡＤＰＯＵＲ Ｍ． Ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ ｉｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ ｕｓｉｎｇ ｈｉｅｒａｒｃｈｉｃａｌ ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ［Ｃ］ ／ ／ Ｐｒｏ⁃ ｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ７ｔｈ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ ｋｎｏｗｌｅｄｇｅ ｔｅｃｈｎｏｌｏｇｙ． Ｕｒｍｉａ， Ｉｒａｎ， ２０１５： １⁃５． ［４］ＳＣＨＡＥＦＦＥＲ Ｓ Ｅ． Ｇｒａｐｈ ｃｌｕｓｔｅｒｉｎｇ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ ｒｅｖｉｅｗ， ２００７， １（１）： ２７⁃６４． ［５］杨博， 刘大有， ＬＩＵ Ｊｉｍｉｎｇ， 等． 复杂网络聚类方法［ Ｊ］． 软件学报， ２００９， ２０（１）： ５４⁃６６． ＹＡＮＧ Ｂｏ， ＬＩＵ Ｄａｙｏｕ， ＬＩＵ Ｊｉｍｉｎｇ， ｅｔ ａｌ． Ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ ｓｏｆｔｗａｒｅ， ２００９， ２０ （１）： ５４⁃６６． ［６］冀俊忠， 刘志军， 刘红欣， 等． 蛋白质相互作用网络功 能模块检测的研究综述［Ｊ］． 自动化学报， ２０１４， ４０（４）： ５７７⁃５９３． ＪＩ Ｊｕｎｚｈｏｎｇ， ＬＩＵ Ｚｈｉｊｕｎ， ＬＩＵ Ｈｏｎｇｘｉｎ， ｅｔ ａｌ． Ａｎ ｏｖｅｒｖｉｅｗ ｏｆ ｒｅｓｅａｒｃｈ ｏｎ ｆｕｎｃｔｉｏｎａｌ ｍｏｄｕｌｅ ｄｅｔｅｃｔｉｏｎ ｆｏｒ ｐｒｏｔｅｉｎ⁃ｐｒｏｔｅｉｎ ｉｎｔｅｒａｃｔｉｏｎ ｎｅｔｗｏｒｋｓ［Ｊ］． Ａｃｔａ ａｕｔｏｍａｔｉｃａ ｓｉｎｉｃａ， ２０１４， ４０ （４）： ５７７⁃５９３． ［７］ＰＡＬＬＡ Ｇ， ＢＡＲＡＢáＳＩ Ａ Ｌ， ＶＩＣＳＥＫ Ｔ． Ｑｕａｎｔｉｆｙｉｎｇ ｓｏｃｉａｌ ｇｒｏｕｐ ｅｖｏｌｕｔｉｏｎ［Ｊ］． Ｎａｔｕｒｅ， ２００７， ４４６（７１３６）： ６６４⁃６６７． ［８］ＳＩＤＩＲＯＰＯＵＬＯＳ Ａ， ＰＡＬＬＩＳ Ｇ， ＫＡＴＳＡＲＯＳ Ｄ， ｅｔ ａｌ． Ｐｒｅ⁃ ｆｅｔｃｈｉｎｇ ｉｎ ｃｏｎｔｅｎｔ ｄｉｓｔｒｉｂｕｔｉｏｎ ｎｅｔｗｏｒｋｓ ｖｉａ ｗｅｂ ｃｏｍｍｕｎｉ⁃ ｔｉｅｓ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ａｎｄ ｏｕｔｓｏｕｒｃｉｎｇ ［ Ｊ］． Ｗｏｒｌｄ ｗｉｄｅ ｗｅｂ， ２００８， １１（１）： ３９⁃７０． ［９］陈克寒， 韩盼盼， 吴健． 基于用户聚类的异构社交网络 推荐算法［Ｊ］． 计算机学报， ２０１３， ３６（２）： ３４９⁃３５９． ＣＨＥＮ Ｋｅｈａｎ， ＨＡＮ Ｐａｎｐａｎ， ＷＵ Ｊｉａｎ． Ｕｓｅｒ ｃｌｕｓｔｅｒｉｎｇ ｂａｓｅｄ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ｒｅｃｏｍｍｅｎｄａｔｉｏｎ［Ｊ］． Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２０１３， ３６（２）： ３４９⁃３５９． ［１０］ＦＲＥＹ Ｂ Ｊ， ＤＵＥＣＫ Ｄ． Ｃｌｕｓｔｅｒｉｎｇ ｂｙ ｐａｓｓｉｎｇ ｍｅｓｓａｇｅｓ ｂｅ⁃ ｔｗｅｅｎ ｄａｔａ ｐｏｉｎｔｓ［ Ｊ］． Ｓｃｉｅｎｃｅ， ２００７， ３１５（ ５８１４）： ９７２⁃ ９７６． ［１１］ＮＥＷＭＡＮ Ｍ Ｅ Ｊ． Ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ａｎｄ ｇｒａｐｈ ｐａｒｔｉｔｉｏ⁃ ｎｉｎｇ［Ｊ］． Ｅｕｒｏｐｈｙｓｉｃｓ ｌｅｔｔｅｒｓ， ２０１３， １０３（２）： ２８００３． ［１２］ＮＥＷＭＡＮ Ｍ Ｅ Ｊ． Ｓｐｅｃｔｒａｌ ｍｅｔｈｏｄｓ ｆｏｒ ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃ⁃ ｔｉｏｎ ａｎｄ ｇｒａｐｈ ｐａｒｔｉｔｉｏｎｉｎｇ［ Ｊ］． Ｐｈｙｓｉｃａｌ ｒｅｖｉｅｗ Ｅ， ２０１３， ８８（４）： ０４２８２２． ［１３］ＬＩＮ Ｃｈｕｎｃｈｅｎｇ， ＫＡＮＧ Ｊｉａｒｏｎｇ， ＣＨＥＮ Ｊ Ｙ． Ａｎ ｉｎｔｅｇｅｒ ｐｒｏｇｒａｍｍｉｎｇ ａｐｐｒｏａｃｈ ａｎｄ ｖｉｓｕａｌ ａｎａｌｙｓｉｓ ｆｏｒ ｄｅｔｅｃｔｉｎｇ ｈｉ⁃ ｅｒａｒｃｈｉｃａｌ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅｓ ｉｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ［ Ｊ］． Ｉｎ⁃ ｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２０１５， ２９９： ２９６⁃３１１． ［１４］ＲＥＮ Ｊｕｎ， ＷＡＮＧ Ｊｉａｎｘｉｎ， ＬＩ Ｍｉｎ， ｅｔ ａｌ． Ｉｄｅｎｔｉｆｙｉｎｇ ｐｒｏ⁃ ｔｅｉｎ ｃｏｍｐｌｅｘｅｓ ｂａｓｅｄ ｏｎ ｄｅｎｓｉｔｙ ａｎｄ ｍｏｄｕｌａｒｉｔｙ ｉｎ ｐｒｏｔｅｉｎ⁃ ｐｒｏｔｅｉｎ ｉｎｔｅｒａｃｔｉｏｎ ｎｅｔｗｏｒｋ ［ Ｊ ］． ＢＭＣ ｓｙｓｔｅｍｓ ｂｉｏｌｏｇｙ， ２０１３， ７（Ｓ４）： Ｓ１２． ［１５］ＬＩ Ｘｉａｏｌｉ， ＦＯＯ Ｃ Ｓ， ＮＧ Ｓ Ｋ． Ｄｉｓｃｏｖｅｒｉｎｇ ｐｒｏｔｅｉｎ ｃｏｍｐｌｅ⁃ ｘｅｓ ｉｎ ｄｅｎｓｅ ｒｅｌｉａｂｌｅ ｎｅｉｇｈｂｏｒｈｏｏｄｓ ｏｆ ｐｒｏｔｅｉｎ ｉｎｔｅｒａｃｔｉｏｎ ｎｅｔｗｏｒｋｓ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎａｌ ｓｙｓｔｅｍｓ ｂｉｏｉｎｆｏｒｍａｔｉｃｓ ｃｏｎｆｅｒｅｎｃｅ． Ｓａｎ Ｄｉｅｇｏ， ＵＳＡ， ２００７， ６： １５７⁃１６８． ［１６］ＰＡＬＬＡ Ｇ， ＤＥＲéＮＹＩ Ｉ， ＦＡＲＫＡＳ Ｉ， ｅｔ ａｌ． Ｕｎｃｏｖｅｒｉｎｇ ｔｈｅ ｏｖｅｒｌａｐｐｉｎｇ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ ｉｎ ｎａｔｕｒｅ ａｎｄ ｓｏｃｉｅｔｙ［Ｊ］． Ｎａｔｕｒｅ， ２００５， ４３５： ８１４⁃８１８． ［１７］ＳＡＩＴＯ Ｋ， ＹＡＭＡＤＡ Ｔ， ＫＡＺＡＭＡ Ｋ． Ｅｘｔｒａｃｔｉｎｇ ｃｏｍｍｕ⁃ ｎｉｔｉｅｓ ｆｒｏｍ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ ｂｙ ｔｈｅ ｋ⁃ｄｅｎｓｅ ｍｅｔｈｏｄ［ Ｊ］． ＩＥＩＣＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｆｕｎｄａｍｅｎｔａｌｓ ｏｆ ｅｌｅｃｔｒｏｎｉｃｓ， ｃｏｍｍｕ⁃ ｎｉｃａｔｉｏｎｓ ａｎｄ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅｓ， ２００８， Ｅ９１⁃Ａ （ １１ ）： ３３０４⁃３３１１． ［１８］ＳＵＮ Ｐｅｎｇｇａｎｇ， ＧＡＯ Ｌｉｎ． Ｆａｓｔ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｄｅｔｅｃｔｉｎｇ ｏ⁃ ｖｅｒｌａｐｐｉｎｇ ｆｕｎｃｔｉｏｎａｌ ｍｏｄｕｌｅｓ ｉｎ ｐｒｏｔｅｉｎ⁃ｐｒｏｔｅｉｎ ｉｎｔｅｒａｃｔｉｏｎ ｎｅｔｗｏｒｋｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ ｃｏｍｐｕｔａｔｉｏｎａｌ ｉｎ⁃ ｔｅｌｌｉｇｅｎｃｅ ｉｎ ｂｉｏｉｎｆｏｒｍａｔｉｃｓ ａｎｄ ｃｏｍｐｕｔａｔｉｏｎａｌ ｂｉｏｌｏｇｙ． Ｎａｓｈｖｉｌｌｅ， ＴＮ， ＵＳＡ， ２００９： ２４７⁃２５４． ［１９］ ＬＩＵ Ｇｕｉｍｅｉ， ＷＯＮＧ Ｌ， ＣＨＵＡ Ｈ Ｎ． Ｃｏｍｐｌｅｘ ｄｉｓｃｏｖｅｒｙ ｆｒｏｍ ｗｅｉｇｈｔｅｄ ＰＰＩ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ， ２００９， ２５ （１５）： １８９１⁃１８９７． ［２０］ＢＡＤＥＲ Ｇ Ｄ， ＨＯＧＵＥ Ｃ Ｗ Ｖ． Ａｎ ａｕｔｏｍａｔｅｄ ｍｅｔｈｏｄ ｆｏｒ ｆｉｎｄｉｎｇ ｍｏｌｅｃｕｌａｒ ｃｏｍｐｌｅｘｅｓ ｉｎ ｌａｒｇｅ ｐｒｏｔｅｉｎ ｉｎｔｅｒａｃｔｉｏｎ ｎｅｔｗｏｒｋｓ［Ｊ］． ＢＭＣ ｂｉｏｉｎｆｏｒｍａｔｉｃｓ， ２００３， ４（１）： ２． ［２１］ＦＲＥＥＭＡＮ Ｌ Ｃ． Ａ ｓｅｔ ｏｆ ｍｅａｓｕｒｅｓ ｏｆ ｃｅｎｔｒａｌｉｔｙ ｂａｓｅｄ ｏｎ ｂｅｔｗｅｅｎｎｅｓｓ［Ｊ］． Ｓｏｃｉｏｍｅｔｒｙ， １９７７， ４０（１）： ３５⁃４１． ［２２］ ＣＵＩ Ｙａｉｚｕ， ＷＡＮＧ Ｘｉｎｇｙｕａｎ， ＥＵＳＴＡＣＥ Ｊ． Ｄｅｔｅｃｔｉｎｇ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｖｉａ ｔｈｅ ｍａｘｉｍａｌ ｓｕｂ⁃ｇｒａｐｈｓ ａｎｄ ｂｅ⁃ ｌｏｎｇｉｎｇ ｄｅｇｒｅｅｓ ｉｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｐｈｙｓｉｃａ Ａ： ｓｔａ⁃ ｔｉｓｔｉｃａｌ ｍｅｃｈａｎｉｃｓ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１４， ４１６： １９８⁃ ２０７． ［２３］ ＺＡＣＨＡＲＹ Ｗ Ｗ． Ａｎ ｉｎｆｏｒｍａｔｉｏｎ ｆｌｏｗ ｍｏｄｅｌ ｆｏｒ ｃｏｎｆｌｉｃｔ 第 ３ 期 郑文萍，等：基于稠密子图的社区发现算法 ·４３１·