基于稠密子图的社区发现算法
2016-06-02郑文萍张浩杰王杰
郑文萍,张浩杰,王杰
(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]等方面均有广泛的应用前景,因此具有十分重要的理论意义和应用价值。……
