第11卷第3期 智能系统学报 Vol.11 No.3 2016年6月 CAAI Transactions on Intelligent Systems Jun.2016 D0I:10.11992.tis.201603045 网络出版地址：http://www.enki..net/kcms/detail/23.1538.TP.20160513.0923.022.html 基于稠密子图的社区发现算法 郑文萍12，张浩杰，王杰12 (1.山西大学计算机与信息技术学院，山西太原030006；2.山西大学计算智能与中文信息处理教育部重点实验室， 山西太原030006) 摘要：基于密度的图聚类算法在社区发现中得到了广泛应用，然而由于其通过搜索网络中局部稠密子图来识别社 区，使得大量结点因不能构成稠密子图而未被聚类。针对此问题，给出了一种基于稠密子图的软聚类算法(comu- nity detection based dense subgraphs,BDSG)。首先给出一种中心社区发现方法；进而定义了一种结点的社区归属度， 并给出中心社区扩展策略；最终得到聚类结果。通过与CPM(clique percolation method),k-dense算法在空手道俱乐 部，海豚社交网络、大学生足球网络、电子邮件网络和合作网络等数据进行比较，表明BDSG算法在模块性指标与时 间效率方面体现了良好性能，同时中心社区扩展策略能在一定程度上提高CPM、k-dense等基于密度算法的聚类有 效性。 关键词：复杂网络：社区发现；图聚类；软聚类：密度：中心扩展策略；点介数：模块性 中图分类号：TP18文献标志码：A文章编号：1673-4785(2016)03-0426-07. 中文引用格式：郑文萍，张浩杰，王杰.基于稠密子图的社区发现算法[J].智能系统学报，2016,11(3)：426432. 英文引用格式：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 Wenping'2,ZHANG Haojie',WANG Jie2 (1.School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China;2.Key Laboratory of Computation In- telligence 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 consti- tute 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 extend- ed 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 strat- egy;vertex betweenness;modularity 收稿日期：2016-03-19.网络出版日期：2016-05-13. 近年来，对各种复杂网络的研究是许多领域的 基金项目：国家自然科学基金项目(61572005,61272004)，山西省煤基 研究热点之一[d),如生物网络、社交网络、电子邮 重点科技攻关项目(M02014-09). 通信作者：郑文萍.E-mail:wpzheng(@sxu.edu.cm 件网络、引文网络等已成为众多学者的主要研究对第 １１ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．３ ２０１６ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１６ ＤＯＩ：１０．１１９９２．ｔｉｓ．２０１６０３０４５ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０５１３．０９２３．０２２．ｈｔｍｌ 基于稠密子图的社区发现算法 郑文萍１，２ ，张浩杰１ ，王杰１，２ （１．山西大学 计算机与信息技术学院，山西 太原 ０３０００６； ２．山西大学 计算智能与中文信息处理教育部重点实验室， 山西 太原 ０３０００６） 摘 要：基于密度的图聚类算法在社区发现中得到了广泛应用，然而由于其通过搜索网络中局部稠密子图来识别社 区，使得大量结点因不能构成稠密子图而未被聚类。 针对此问题，给出了一种基于稠密子图的软聚类算法（ ｃｏｍｍｕ⁃ ｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ｂａｓｅｄ ｄｅｎｓｅ ｓｕｂｇｒａｐｈｓ，ＢＤＳＧ）。 首先给出一种中心社区发现方法；进而定义了一种结点的社区归属度， 并给出中心社区扩展策略；最终得到聚类结果。 通过与 ＣＰＭ（ ｃｌｉｑｕｅ ｐｅｒｃｏｌａｔｉｏｎ ｍｅｔｈｏｄ）、ｋ⁃ｄｅｎｓｅ 算法在空手道俱乐 部、海豚社交网络、大学生足球网络、电子邮件网络和合作网络等数据进行比较，表明 ＢＤＳＧ 算法在模块性指标与时 间效率方面体现了良好性能， 同时中心社区扩展策略能在一定程度上提高 ＣＰＭ、ｋ⁃ｄｅｎｓｅ 等基于密度算法的聚类有 效性。 关键词：复杂网络；社区发现；图聚类；软聚类；密度；中心扩展策略；点介数；模块性 中图分类号：ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０３⁃０４２６⁃０７． 中文引用格式：郑文萍，张浩杰，王杰．基于稠密子图的社区发现算法［Ｊ］． 智能系统学报， ２０１６， １１（３）： ４２６⁃４３２． 英文引用格式：ＺＨＥＮＧ Ｗｅｎｐｉｎｇ， ＺＨＡＮＧ Ｈａｏｊｉｅ， ＷＡＮＧ Ｊｉｅ． Ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｄｅｎｓｅ ｓｕｂｇｒａｐｈｓ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６，１１（３）： ４２６⁃４３２． Ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｄｅｎｓｅ ｓｕｂｇｒａｐｈｓ ＺＨＥＮＧ Ｗｅｎｐｉｎｇ １，２ ， ＺＨＡＮＧ Ｈａｏｊｉｅ １ ， ＷＡＮＧ Ｊｉｅ １，２ （１． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ， Ｓｈａｎｘｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｔａｉｙｕａｎ ０３０００６， Ｃｈｉｎａ； ２． Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎ Ｉｎ⁃ ｔｅｌｌｉｇｅｎｃｅ ａｎｄ Ｃｈｉｎｅｓｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ， Ｍｉｎｉｓｔｒｙ ｏｆ Ｅｄｕｃａｔｉｏｎ， Ｓｈａｎｘｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｔａｉｙｕａｎ ０３０００６， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｄｅｎｓｉｔｙ－ｂａｓｅｄ ｇｒａｐｈ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｈａｓ ｂｅｅｎ ｗｉｄｅｌｙ ｕｓｅｄ ｉｎ ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ． Ｈｏｗｅｖｅｒ， ｂｅｃａｕｓｅ ｉｔ ｉｄｅｎｔｉｆｉｅｓ ａ ｃｏｍｍｕｎｉｔｙ ｂｙ ｓｅａｒｃｈｉｎｇ ａ ｐａｒｔｉａｌｌｙ ｄｅｎｓｅ ｓｕｂｇｒａｐｈ ｉｎ ｔｈｅ ｎｅｔｗｏｒｋ， ｍａｎｙ ｎｏｄｅｓ ｄｏ ｎｏｔ ｃｏｎｓｔｉ⁃ ｔｕｔｅ ａ ｄｅｎｓｅ ｓｕｂｇｒａｐｈ ａｎｄ ａｒｅ ｔｈｅｒｅｆｏｒｅ ｄｉｆｆｉｃｕｌｔ ｔｏ ｃｌｕｓｔｅｒ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｗｅ ｐｒｅｓｅｎｔ ａ ｓｏｆｔ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｄｅｎｓｅ ｓｕｂｇｒａｐｈｓ （ＢＤＳＧ） ｆｏｒ ｄｅｔｅｃｔｉｎｇ ｃｏｍｍｕｎｉｔｉｅｓ ｉｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ． Ｆｉｒｓｔ， ｗｅ ｐｒｏｐｏｓｅ ａ ｍｅｔｈｏｄ ｆｏｒ ｄｅｔｅｃｔｉｎｇ ｔｈｅ ｃｅｎｔｒａｌ ｃｏｍｍｕｎｉｔｉｅｓ． Ｎｅｘｔ， ｗｅ ｄｅｆｉｎｅ ｔｈｅ ｄｅｇｒｅｅ ｏｆ ｃｏｍｍｕｎｉｔｙ ａｔｔｒｉｂｕｔｉｏｎ ｏｆ ａ ｎｏｄｅ， ａｎｄ ｐｕｔ ｆｏｒｗａｒｄ ａ ｃｏｒｅ ｃｏｍｍｕｎｉｔｙ ｅｘｔｅｎｄｅｄ ｓｔｒａｔｅｇｙ． Ｆｉｎａｌｌｙ， ｗｅ ｏｂｔａｉｎ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｏｆ ａ ｎｅｔｗｏｒｋ． Ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ｃｌｉｑｕｅ ｐｅｒｃｏｌａｔｉｏｎ ｍｅｔｈｏｄ （ＣＰＭ）， ｋ－ｄｅｎｓｅ ａｌｇｏｒｉｔｈｍｓ ｆｒｏｍ Ｚａｃｈａｒｙ＇ｓ Ｋａｒａｔｅ Ｃｌｕｂ， ｔｈｅ ｄｏｌｐｈｉｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ， ｔｈｅ Ａｍｅｒｉｃａｎ ｃｏｌｌｅｇｅ ｆｏｏｔｂａｌｌ ｎｅｔｗｏｒｋ， ｔｈｅ ｅｍａｉｌ ｎｅｔｗｏｒｋ， ａｎｄ ｔｈｅ ｃｏｌｌａｂｏｒａｔｉｏｎ ｎｅｔｗｏｒｋ， ＢＤＳＧ ｓｈｏｗｓ ｃｏｎｓｉｄｅｒａｂｌｙ ｂｅｔｔｅｒ ｐｅｒｆｏｒｍａｎｃｅ ｗｉｔｈ ｒｅｓｐｅｃｔ ｔｏ ｍｏｄｕｌａｒｉｔｙ ａｎｄ ｔｉｍｅ ｅｆｆｉｃｉｅｎｃｙ． Ｉｎ ａｄｄｉｔｉｏｎ， ｔｈｅ ｐｒｏｐｏｓｅｄ ｃｏｒｅ ｃｏｍｍｕｎｉｔｙ ｅｘｔｅｎｄ⁃ ｅｄ ｓｔｒａｔｅｇｙ ｍａｙ ｉｍｐｒｏｖｅ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ－ｍｅｔｈｏｄｓ－ｂａｓｅｄ ｄｅｎｓｉｔｙ， ｓｕｃｈ ａｓ ｔｈａｔ ｉｎ ＣＰＭ， ｋ－ｄｅｎｓｅ ａｌｇｏｒｉｔｈｍｓ， ａｎｄ ｏｔｈｅｒｓ． Ｋｅｙｗｏｒｄｓ：ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋ； ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ； ｇｒａｐｈ ｃｌｕｓｔｅｒｉｎｇ； ｓｏｆｔ ｃｌｕｓｔｅｒｉｎｇ； ｄｅｎｓｉｔｙ； ｃｏｒｅ ｅｘｔｅｎｄｅｄ ｓｔｒａｔ⁃ ｅｇｙ； ｖｅｒｔｅｘ ｂｅｔｗｅｅｎｎｅｓｓ； ｍｏｄｕｌａｒｉｔｙ 收稿日期：２０１６⁃０３⁃１９． 网络出版日期：２０１６⁃０５⁃１３． 基金项目：国家自然科学基金项目（ ６１５７２００５，６１２７２００４），山西省煤基 重点科技攻关项目（ＭＱ２０１４⁃０９）． 通信作者：郑文萍． Ｅ⁃ｍａｉｌ： ｗｐｚｈｅｎｇ＠ ｓｘｕ．ｅｄｕ．ｃｎ． 近年来，对各种复杂网络的研究是许多领域的 研究热点之一［１⁃３］ ，如生物网络、社交网络、电子邮 件网络、引文网络等已成为众多学者的主要研究对