An Improved Label Propagation Algorithm Based on Motif and Critical Node for Community Detection

Community detection can reveal the structural properties of real social networks. In community detection, label propagation is an effective typical method which has the advantage of nearly linear time complexity. However, it usually random selects nodes to update the direct neighbor label, which leads to the inaccurate community structure and instability. To solve these issues, we introduce network motif and critical node to assign weights to the edges of the network. Moreover, motif can reveal the basic building blocks of higher-order structures in complex networks. Based on two techniques above, this paper proposes an improved label propagation algorithm called MCN-LPA. MCN-LPA first mines motifs in original network. Then, MCN-LPA uses the mined motifs to find the critical nodes, which play a vital role in the effective information dissemination. Thirdly, a weighted undirected network is constructed based on motif and critical node. Finally, the correlation strength between neighbors on the network and the number of neighbor labels are employed for label propagation. The aim is to overcome the randomness of label selection to achieve the more stable community structure. Extensive experiments are conducted on four real-world complex networks. The results demonstrate that our proposed method outperforms the state-of-the-arts and has the better stability.