一种基于网络剪枝和局部社区扩展的边社区发现算法

摘要

一种基于图剪枝和局部社区扩展的边社区发现算法是一种重叠社区发现算法。首先，计算图中的边吸引力，将图中边吸引力低于阈值的边删除，得到剪枝后的图。之后，将剪枝图转化为线图，使用PageRank算法，计算线图上的节点的得分矩阵，选取一个种子节点，扩展社区，重复该过程，直至网络中无候选种子节点为止。合并重复线图上的节点社区，并将其转换回原图上节点的重叠社区结构。本发明为重叠社区发现提供了一种基于图剪枝和局部社区扩展的边社区发现算法，与现有方法比较，本发明具有如下主要优点：（1）提出边吸引力概念，利用边吸引力进行图剪枝，降低线图节点的规模。（2）使用局部社区发现算法对线图上节点进行社区发现，能达到更优的评估度量值。