基于拓扑结构的密度峰值重叠社区发现算法

摘要

现代网络科学的不断发展,为人们的生活提供了极大的便利。对复杂网络的研究是推动现代网络科学发展的重要动力,而社区是研究复杂网络的重要结构。已有的社区发现方法大多是高度复杂的,这不利于有效挖掘复杂网络。为了研究更高效的社区发现算法,文中将近年来被提出的密度峰值聚类算法应用于社区发现中,对密度峰值算法进行改进,提出了一种高效的社区发现算法。将密度峰值算法应用于社区发现存在一些问题,由于复杂网络数据结构具有特殊性,其数据大多以拓扑图或邻接矩阵的形式存储,因此将密度峰值聚类算法应用到社区发现中的核心问题是如何有效地计算网络中各节点间的距离、节点局部密度和选择中心节点。针对该问题,文中通过网络拓扑图中各节点及其邻居节点的度来计算每一个节点的局部密度,通过节点间的相似度来度量节点间的距离,并对距离进行离散化处理,以便选取社区中心节点;定义了核心跳变值来更精确地选取社区中心,防止大社区吞并小社区;基于LFR人工网络和真实网络数据集,将所提算法与已有算法进行比较,并采用扩展的模块度、调整兰德系数以及归一化互信息对实验结果进行评估。真实网络中的实验结果表明了所提算法具有不错的效果,且在一些真实场景中具有明显优势;在人工网络中,所提算法同样具有优势,同时其相比其他算法更加稳定。