一种基于最大度节点扩展的社区发现算法

摘要

针对星状社会网络,提出一种基于最大度节点扩展的社区发现算法.首先,计算网络中所有节点的度,选取节点的度大于等于阚值p的k个节点,以这k个节点为中心,与其各自的邻居节点形成k个分散的初始社区,删除重叠度高于给定阈值q的小社区.然后,对出现在这些初始社区中的重叠节点,提出一种近邻方法,通过计算这些节点到所在社区的距离,将其划分到距离最近的社区.对于k个初始社区外的节点,采用同样方法,将其划入到相应距离最近的社区.在真实网络数据集上进行了实验,实验结果表明,该方法能有效地处理初始社区内外边缘部分的不确定节点的划分问题,揭示出网络中存在的社区结构.相比经典的GN算法,该算法能得到更准确的划分结果,也具有更高的性能.