Improving the stability of label propagation algorithm by propagating from low-significance nodes for community detection in social networks

Community detection is regarded as a significant research domain in social network analysis. Thanks to its merits, including linear-time complexity, performance and simplicity, the label propagation algorithm (LPA) has attracted a lot of researchers' interests in recent years. However, regarding the label propagation process, it has some drawbacks such as uncertainty and randomness behavior which may negatively impact the stability and accuracy of community detection. In this paper, a simple and fast method is proposed to overcome the LPA's drawbacks. We have proposed a novel method to improve the certainty and stability of the label propagation algorithm based on node ranking in a social network, called the CSLPR algorithm. After performing a proposed local method for ranking nodes, the label propagation is started from the nodes with lowest rank. In the first and second iterations (t <= 2) of the propagation, if the number of maximum label frequency in neighboring of a node be equal, the Adamic/Adar index is used for selecting the appropriate label. For the other iterations (t > 2), a new criterion, known as label strength, is applied to select the label with the highest strength of a node. In real-world social networks, communities are established around important nodes. Therefore, when a low-significance node joins the networks, it receives the label of a community C-i that has the most connection to this community. The proposed method is evaluated on several real-world and artificial networks. The results reveal that the proposed method can accurately detect communities with higher performance, certainty, and stability in comparison to other methods.