Parallel Algorithm for Overlapping Community Detection in Complex Networks

With the increasing size of complex networks, traditional detection methods are difficult to scale to larger networks. This paper proposes a parallel hierarchical link（PHLink） algorithm to discover overlapping communities. By studying the power-law degree distribution of complex networks, we distinguish the motivations of why two nodes intend to establish a connection so that the complexity for community detection can be reduced. PHLink is implemented using distributed computing for large-scale networks via graph segmentation and redundant storage. Experiments validate that PHLink can accurately discover network communities and the overlaps between them. For scale-free networks, removing 0.1% of the hub nodes reduces the computation time by 94%. Meanwhile, PHLink demonstrates good speed-up and scale-up on Hadoop, which can scale to very large complex networks with millions of edges.