MLPA: Detecting overlapping communities by multi-label propagation approach

摘要

The identification of communities is an important step in understanding of the complex network. Comparative studies suggest that the development of accurate and efficient methods to infer the communities is still in its early stages. Label propagation algorithm (LPA) that detects communities by propagating labels among vertices, attracts a great deal of attention recently. However, the communities detected by most LPAs are disjointed. Due to communities are often overlapping in real world networks, we show a multi-label propagation algorithm (MLPA) to detect overlapping communities. The inspiration is that the more people are familiar, the more they trust each other. To simulate the confidence of human communication, propagating intensity (PI) is defined to describe the confidence extent of the label propagated by neighboring vertices. The PI is then used to guide the propagation, with the purpose to make the detection more accurate. The results of extensive experiments both on synthetic and real networks show that the proposed MLPA outperforms many other methods. The effectiveness of MLPA can be attributed to its multi-label propagating strategy.