LinkLPA: A Link-Based Label Propagation Algorithm for Overlapping Community Detection in Networks

摘要

Community detection is an important methodology for understanding the intrinsic structure and function of complex networks. Because overlapping community is one of the characteristics of real-world networks and should be considered for community detection, in this article, we propose an algorithm, called link-based label propagation algorithm (LinkLPA), to detect overlapping communities. Because the link partition is conceptually natural for the problem of overlapping community detection, LinkLPA first transforms node partition problem into link partition problem and employs a new label propagation algorithm with preference on links instead of nodes to detect communities due to the simplicity and efficiency of label propagation algorithm. Then the proposed LinkLPA performs a postprocessing to refine the detected overlapping communities by avoiding over-overlapping and incorrect partition of weak ties. Experimental results on a large number of real-world and synthetic networks show that the proposed method achieves high accuracy on detecting overlapping communities in networks.