Distributed Community Detection on Overlapping Stochastic Block Model

Community detection, referred as the clustering procedure for similar nodes in the network, is an important research topic in the area of big data network. Distributed community detection algorithm, with its simplicity and high-efficiency, has drawn extensive attention recently. The existing distributed algorithm can only be applied on networks with non-overlapping communities, however, overlapping communities widely exist in real networks, which cannot be detected by the distributed algorithm. We carefully study the overlapping community structure and introduce the overlapping stochastic block model, in which each node may belong to multiple communities. Based on the existing distributed algorithm, we further propose an improved algorithm with an extra stage to discover nodes belonging to the overlapping community, which can be applied on the overlapping stochastic block model. Through theoretical analysis, we show that the proposed algorithm achieves effective detection results on both overlapping and non-overlapping communities. We also conduct various simulations on the overlapping stochastic block model, showing that the proposed algorithm outperforms the existing distributed algorithm and maintains effectiveness in a wide range of system parameters.