基于稠密子图的社区发现算法

摘要：

基于密度的图聚类算法在社区发现中得到了广泛应用，然而由于其通过搜索网络中局部稠密子图来识别社区，使得大量结点因不能构成稠密子图而未被聚类。针对此问题，给出了一种基于稠密子图的软聚类算法（ commu?nity detection based dense subgraphs，BDSG）。首先给出一种中心社区发现方法；进而定义了一种结点的社区归属度，并给出中心社区扩展策略；最终得到聚类结果。通过与CPM（ clique percolation method）、k?dense算法在空手道俱乐部、海豚社交网络、大学生足球网络、电子邮件网络和合作网络等数据进行比较，表明BDSG算法在模块性指标与时间效率方面体现了良好性能，同时中心社区扩展策略能在一定程度上提高CPM、k?dense等基于密度算法的聚类有效性。

关键词：复杂网络、社区发现、图聚类、软聚类、密度、中心扩展策略、点介数、模块性

所属期刊栏目：11

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金项目61572005，61272004;山西省煤基重点科技攻关项目 MQ2014-09．

在线出版日期：2016-06-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：426-432