基于GN算法的重叠社区识别方法

Method of identifying overlapping communities based on GN algorithm

针对社会网络中的重叠社区识别问题,提出用从属度描述节点对不同社区的紧密程度,并把模块度扩展到重叠社区的识别.基于Girvan和Newman提出的非重叠社区识别(GN)算法设计了重叠社区的串行识别算法.基于MapReduce模型设计了并行识别算法,以提高识别效率.对模块度与重叠度进行了分析,结果表明:所提出的算法在计算机科学文献网络中能有效识别重叠社区,且运行效率优于已有重叠社区识别算法.

The overlapping community detection in complex networks was studied .The notion of de‐gree of membership was first presented to expresses how strongly a node belongs to a community ,and then the definition of modularity was extended to undirected graphs with overlapping communities . An overlapping community detection algorithm was provided by extending the classical algorithm presented by Girvan and Newman （GN） for identifying disjoint communities ,called GN algorithm .In order to improve the running speed ,a parallel algorithm based on MapReduce was given .The experi‐mental results demonstrate the effectiveness of proposed algorithms on DBLP （digital bibliography and library project） data and show that they outperform other methods on efficiency .