Advanced modularity-specialized label propagation algorithm for detecting communities in networks
arXiv:0910.1154 · doi:10.1016/j.physa.2009.12.019
Abstract
A modularity-specialized label propagation algorithm (LPAm) for detecting network communities was recently proposed. This promising algorithm offers some desirable qualities. However, LPAm favors community divisions where all communities are similar in total degree and thus it is prone to get stuck in poor local maxima in the modularity space. To escape local maxima, we employ a multistep greedy agglomerative algorithm (MSG) that can merge multiple pairs of communities at a time. Combining LPAm and MSG, we propose an advanced modularity-specialized label propagation algorithm (LPAm+). Experiments show that LPAm+ successfully detects communities with higher modularity values than ever reported in two commonly used real-world networks. Moreover, LPAm+ offers a fair compromise between accuracy and speed.
9 pages, 2 figures
References in corpus (12)
- Fast unfolding of communities in large networks
- Modularity and community structure in networks
- Cooperative Game Theory Approaches for Network Partitioning
- Near linear time algorithm to detect community structures in large-scale networks
- Community Structure in Jazz
- The performance of modularity maximization in practical contexts
- Detecting network communities by propagating labels under constraints
- Modularity-Maximizing Network Communities via Mathematical Programming
- Size reduction of complex networks preserving modularity
- Towards real-time community detection in large networks
- Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
- Community Structure in Graphs
Cited by in corpus (23)
- A smart local moving algorithm for large-scale modularity-based community detection
- Finding overlapping communities in networks by label propagation
- Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
- Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
- Robust network community detection using balanced propagation
- Community structure of complex software systems: Analysis and applications
- An analysis of the graph processing landscape
- Reinforced Neighborhood Selection Guided Multi-Relational Graph Neural Networks
- Enhancing community detection by local structural information
- Detecting Community Structure in Dynamic Social Networks Using the Concept of Leadership
- Detecting Communities in Tripartite Hypergraphs
- Community detection by label propagation with compression of flow
- Label propagation for clustering
- Distributed Community Detection in Dynamic Graphs
- Unfolding network communities by combining defensive and offensive label propagation
- On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
- Detecting network communities beyond assortativity-related attributes
- Multiscale Evolutionary Perturbation Attack on Community Detection
- Extending modularity by capturing the similarity attraction feature in the null model
- Role-based Label Propagation Algorithm for Community Detection
- Weighted Label Propagation Algorithm based on Local Edge Betweenness
- A framework for community detection in heterogeneous multi-relational networks
- Local Edge Betweenness based Label Propagation for Community Detection in Complex Networks