A Novel Algorithm for Finding Overlapping Communities in Networks Based on Label Propagation

摘要

Community discovery in Social network is one of the hot spots. In real networks, some nodes belong to several different communities. Overlapping community discovery has been more and more popular. Label propagation algorithm has been proven to be an effective method for complex network community discovery, this algorithm has the characteristics of simple and fast. For the poor stability problem of Label propagation algorithm, this article proposes a stable overlapping communities discovery method based on the label propagation algorithm: SALPA. At the beginning of the method, introduce the influence of nodes, which is used to measure the influence of nodes, select the most influential nodes as the core nodes, in the propagating stage, when there are more than one label with the same degree of membership, select the connectivity lager than the threshold. The method has been carried out in three real networks and two big synthetic networks. Compared with the classical algorithm, experiment results demonstrate the effectiveness, stability and computational speed of the method have been improved.