基于流式分析的大规模网络重叠社区发现算法

作者：李辉; 张建朋^*; 陈福才

来源：电子学报, 2022, 50(08): 1951-1958.

• 社区发现
• 重叠社区
• 大规模网络
• 流式分析
• 节点贡献度

为了提高在大规模网络中发现社区的效率,提出一种基于流式分析的大规模网络重叠社区发现算法(Streaming-based Overlapping Community Detection algorithm,SOCD).算法对网络中的边进行流式处理,每次只处理一条边且每条边仅被处理一次.根据节点的度、节点对社区的贡献度以及节点移动前后社区间连边数量的变化等信息对节点进行划分.在人工合成网络和真实大规模网络上的一系列实验表明,SOCD算法在时间消耗和内存占用上具有较大的优势,比传统方法快10倍以上,且具有较强的鲁棒性,能够在线性时间和空间复杂度下高效、准确地挖掘网络中的重叠社区结构.

• 单位
  信息工程大学