DPNLP: distance based peripheral nodes label propagation algorithm for community detection in social networks

Label propagation-based methods are the most popular methods for community detection, which have a linear time complexity, thanks to the use of local features for updating node labels. However, they suffer from major concerns including instability, low accuracy, and discovering monster communities. To solve these problems, this paper proposes a novel distance based peripheral nodes label propagation algorithm for fast community detection, called DPNLP. First, core nodes are detected and their labels are distributed to the neighbors to form the initial communities. Then, labels of the peripheral nodes are identified using combinations of local features. Finally, the structures of communities are extracted after assigning a label to the nodes with degree one and two at the last stage of the method. The proposed method achieves significant speed up because of optimizing the number of required updates. In addition, DPNLP is remarkably stable and it does not have monster-community problem. According to the conducted evaluations over artificial and real-world networks, the proposed methods achieve improved results in terms of NMI, F-measure, modularity, and runtime metrics. Experiments have also been performed to confirm the stability of the algorithm and the lack of monster community’s formation.