2011/05/17 by Jierui Xie, Bolesław K. Szymański, Boleslaw K. Szymanski · 165 citations
Computer Science · Mathematics · Physics and Astronomy · #Affinity propagation #Algorithm #Artificial intelligence #CURE data clustering algorithm #Cluster analysis #Clustering coefficient #Community structure #Complex Network Analysis Techniques #Computer science #Correlation clustering #Data Visualization and Analytics #Data mining #Generalization #Mathematics #Node (physics) #Opinion Dynamics and Social Influence #Quality (philosophy) #Range (aeronautics) #Statistics #Time complexity #cs.SI #physics.soc-ph
paper · pdf · doi:10.1109/nsw.2011.6004645
published as Proc.IEEE Network Science Workshop, NSW'11, West Point, NY, 2011, pp. 188-195 · IEEE NSW 2011
arxiv created 2011/05/17 · openalex publication_date 2011/06/01 · arxiv updated 2016/11/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Studies of community structure and evolution in large social networks require a fast and accurate algorithm for community detection. As the size of analyzed communities grows, complexity of the community detection algorithm needs to be kept close to linear. The Label Propagation Algorithm (LPA) has the benefits of nearly-linear running time and easy implementation, thus it forms a good basis for efficient community detection methods. In this paper, we propose new update rule and label propagation criterion in LPA to improve both its computational efficiency and the quality of communities that it detects. The speed is optimized by avoiding unnecessary updates performed by the original algorithm. This change reduces significantly (by order of magnitude for large networks) the number of iterations that the algorithm executes. We also evaluate our generalization of the LPA update rule that takes into account, with varying strength, connections to the neighborhood of a node considering a new label. Experiments on computer generated networks and a wide range of social networks show that our new rule improves the quality of the detected communities compared to those found by the original LPA. The benefit of considering positive neighborhood strength is pronounced especially on real-world networks containing sufficiently large fraction of nodes with high clustering coefficient.