Improved label propagation algorithms with node attribute and link strength for community detection

Document Type: Research Paper

Authors

Yazd university

Abstract

Community detection has a wide variety of  applications in different fields such as data mining, social network analysis and so on.
Label Propagation Algorithm (LPA) is a simple and fast community detection algorithm, but it has low accuracy. There have been presented   some advanced versions of LPA  in recent years such as CenLP and WILPAS. In this paper, we present  improved versions of CenLP and WILPAS methods called CenLP+ and WILPAS+ respectively.   Experiments and benchmarks demonstrate that while CenLP+ is as fast as CenLP, it outperforms CenLP on both synthetic and  real-world networks.  Moreover, while accuracy of WILPAS+ on synthetic networks  comparable with that of WILPAS, on real-world networks, WILPAS+ excels WILPAS. In addition,  whereas both presented methods CenLP+ and WILPAS+ show high accuracy on synthetic networks, on real-world networks they outperform remarkably all other tested label propagation based algorithms for  community detection. Therefore, since CenLP+ and WILPAS+ are both fast and accurate,  specially on real-world networks, they can efficiently reveal   community structures of mega-scale  social networks.

Keywords