Detecting community structure via synchronous label propagation

Community detection has become an important methodology to understand the organization and function of various real-world networks. Label propagation algorithm (LPA) is a near linear time algorithm which is effective in finding a good community structure. However, it updates the labels of nodes asynchronously in random order to avoid label oscillations, resulting in poor performance, weak robustness and difficulty in parallelizing the update procedure for large-scale network and distributed dynamic complex networks. We propose a novel strategy named LPA-S to update the labels of nodes synchronously by the probability of each surrounding label, which is easy to be parallelized. We experimentally investigate the effectiveness of the proposed strategy by comparing with asynchronous LPA on both computer-generated networks and real-world networks. The experimental results show our LPA-S does not harm the quality of the partitioning while can be easily parallelized.