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

网络的社团结构(Community Structure)作为复杂网络的一个重要特征,发现网络的社团结构是一项非常基础且重要的工作。实际中社团的重叠性(Overlapping)和社团的层次性(Hierarchical Structure)交织在一起,二者的关系十分紧密,单纯忽略其中的任何一方来研究另一方,其结果都不能准确的描述网络中的社团结构。社团发现算法的研究已经得到了学术界的广泛关注,但是对重叠社团发现算法,尤其是利用边社团进行重叠社团发现算法的研究还是比较新的研究领域,具有很广阔的研究前景和重要的现实意义。本文通过对谱分析方法的研究,首次将该方法应用在边社团发现算法上,实现了利用谱分析进行边社团发现。一方面将谱分析方法改进为能够发现重叠社团的算法,另一方面,谱分析方法提供了一种新颖的定量边与边相似度的方式。在基于一维非平凡特征向量的重叠社团发现中,本文分别进行了基于线图标准化拉普拉斯矩阵和基于线图归一化拉普拉斯矩阵一维非平凡特征向量的社团发现；在基于二维非平凡特征向量的重叠社团发现中,本文利用基于线图标准化拉普拉斯矩阵的二维非平凡特征向量空间,进行了兼顾社团层次性和重叠性的复杂网络重叠社团发现算法的研究。在空手道俱乐部网络(Zachary Karate Club)和海豚社交网络(Dolphin social network)与Ahn在2010年提出的算法进行了比较分析。实验结果表明,本文算法能实现复杂网络重叠社区发现,与Ahn的算法相比具有更好的性能。