A modified label propagation algorithm for community detection in attributed networks

Abstract

Community detection is an important problem in network science that discovers highly clustered groups of nodes having similar properties. Label propagation algorithm (LPA) is one of the popular clustering techniques that has attracted much attention due to its efficiency and non-dependence on parameters. Despite its advantages, an important limitation of LPA is the randomness in grouping nodes that leads to instability and the formation of large communities. In this study, we propose four variants based on LPA to overcome the random community allocation problem, henceforth generating better clusters. These variants utilize link strength and node attribute information to enhance the quality of detected communities. Furthermore, the proposed variants require no parameter for categorical attributes and only one parameter (constant for all the networks) for continuous attributes. Finally, the best results are obtained by Variant I having a maximum Normalized Mutual Information score of 0.86, 0.88 on the two synthetic networks.

Keywords

• Community detection
• Complex network
• Social networks
• Attributed graph clustering
• Label propagation
• Link strength