一种基于聚类的社团划分算法

摘要：

社团划分是社会网络的一个研究热点。为了快速准确地发现社会网络的社团结构,文中从节点的重要度出发,利用节点之间的相似性,提出了一种基于聚类的社团划分算法—CCDA。其基本思想是每次以节点集合中聚集系数最大的点作为聚类中心,基于最短路径和欧几里得距离计算节点相似度,选择与聚类中心的相似度大于给定阈值的点进行聚类,不断迭代,直至节点集合为空,所产生的各个簇即为不同的社团。对被重复划分的节点,以模块度函数为标准,将节点归属到最合适的社团中。由于该算法每次从重要节点出发,再次选取聚类中心时不需考虑已经被聚类的节点,所以时间复杂度低于GN算法和Newman算法。将该算法应用于经典的社会网络Zachary,结果表明了CCDA算法对社团划分的有效性。

关键词：社会网络、社团划分、聚集系数、相似性、聚类

分类号：TP311(计算技术、计算机技术)

资助基金：国家“973”重点基础研究发展计划项目2011CB302903

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

页数：共4页

页码：119-122