基于线图的复杂网络重叠社团发现算法研究

在重叠社团发现算法中,基于线图的重叠社团发现算法是最近几年兴起的比较新的领域,具有广阔的研究前景,线图是将边看作研究对象来发现复杂网络社团结构的一种方法,线图的最大优势就是可以利用非重叠社团发现算法发现重叠社团结构。本文就是基于线图提出了一种重叠社团发现算法。在真实世界中,很多复杂网络的社团个数是未知的,这使得一些依赖于社团个数先验知识的算法无法使用。因此,本文将基于拉普拉斯矩阵的Jordan型图特征分析应用到线图中,来获取线图社团个数的先验知识。然后,将基于拉普拉斯矩阵的谱聚类应用到线图中,通过拉普拉斯矩阵的特征向量将网络中的边映射到欧氏空间,欧氏空间中每个特征向量分量中的元素对应了线图中的节点,并且选择其中的两列构成特征向量空间,同时计算特征向量之间的相似度。最后,有了社团个数先验知识的支撑与铺垫,一方面选择K-means聚类算法对特征向量进行聚类来确定社团的划分结果,既利用了K-means算法简单快速的优点,又符合K-means算法依赖社团个数先验知识的特点,相得益彰;另一方面,使用层次聚类算法对特征向量进行聚类,在得到层次聚类树状图后,依据社团个数的先验知识对层次聚类树状图进行切割,从而确定最终的社团划分结果。实验结果表明,本文算法能够实现对复杂网络重叠社团结构的发现,比相关算法具有更好的性能。