基于聚类粒化的社团发现算法

作     者：赵姝 柯望 陈洁 张燕平 ZHAO Shu;KE Wang;CHEN Jie;ZHANG Yanping

作者机构：安徽大学计算机科学与技术学院合肥230601 智能计算与信号处理教育部重点实验室(安徽大学)合肥230601 

出 版 物：《计算机应用》 (journal of Computer Applications)

年 卷 期：2014年第34卷第10期

页      面：2812-2815,2830页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金资助项目(61175046) 安徽省高等学校省级自然科学研究项目(KJ2013A016) 

主　　题：复杂网络 社团发现 粒化系数 聚类粒化 

摘      要：为了实现复杂网络社团发现算法的复杂度和精确度间的均衡,提出一种基于聚类粒化的社团发现算法(CGCDA),将网络粒化获得的粒子视为一个社团,粒化结果即为对网络的社团划分。首先,将网络中的每个节点视为基本粒,通过初始粒化操作实现对网络的粒化;然后,针对获得的粒化集合中满足粒化系数的粒子进行聚类粒化操作,分层粒化直到不存在满足要求的粒子对;最后,将粒子对中的重叠节点视为孤立点,用邻居节点投票法把孤立节点归并到相应的粒子中,实现对复杂网络的社团划分。实验实现了Newman快速算法(NFA)、标号传播算法(LPA)和CGCDA。实验结果表明,CGCDA在四个基准数据集上可获得平均高于LPA 7.6%的模块度和低于NFA 96%的时间。CGCDA时间复杂度较低,获取的社团模块度较高,实现了社团发现时间和精确度的均衡,相比NFA、LPA总体性能更优。