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

来源：计算机技术与发展杂志2015年第10期北京时间：

作者：王伟;李玲娟

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

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