Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm

Abstract

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.

IEEE NSW 2011

References in corpus (15)

• Fast unfolding of communities in large networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Detecting network communities by propagating labels under constraints
• Towards real-time community detection in large networks
• Finding Community Structure in Mega-scale Social Networks
• Limited resolution in complex network community detection with Potts model approach
• Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
• Note on the equivalence of the label propagation method of community detection and a Potts model approach
• Random field Ising model and community structure in complex networks
• Hub-Based Community Finding

Cited by in corpus (21)

• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• SLPA: Uncovering Overlapping Communities in Social Networks via A Speaker-listener Interaction Dynamic Process
• A New Metric for Quality of Network Community Structure
• Large network community detection by fast label propagation
• GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities
• Community detection using boundary nodes in complex networks
• OLCPM: An Online Framework for Detecting Overlapping Communities in Dynamic Social Networks
• LabelRank: A Stabilized Label Propagation Algorithm for Community Detection in Networks
• LabelRankT: Incremental Community Detection in Dynamic Networks via Label Propagation
• Community Detection in Dynamic Networks via Adaptive Label Propagation
• Predicting complex user behavior from CDR based social networks
• Community detection by label propagation with compression of flow
• Label propagation for clustering
• Complex Networks, Communities and Clustering: A survey
• Incremental Learning with Accuracy Prediction of Social and Individual Properties from Mobile-Phone Data
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• Understanding Information Flow in Cascades Using Network Motifs
• Understanding Vulnerability of Communities in Complex Networks
• Testing Alignment of Node Attributes with Network Structure Through Label Propagation
• Identifying Community Structures in Dynamic Networks