Detecting network communities by propagating labels under constraints

Abstract

We investigate the recently proposed label-propagation algorithm (LPA) for identifying network communities. We reformulate the LPA as an equivalent optimization problem, giving an objective function whose maxima correspond to community solutions. By considering properties of the objective function, we identify conceptual and practical drawbacks of the label propagation approach, most importantly the disparity between increasing the value of the objective function and improving the quality of communities found. To address the drawbacks, we modify the objective function in the optimization problem, producing a variety of algorithms that propagate labels subject to constraints; of particular interest is a variant that maximizes the modularity measure of community quality. Performance properties and implementation details of the proposed algorithms are discussed. Bipartite as well as unipartite networks are considered.

16 pages, 3 figures, 6 tables; significant expansion of discussion of results

References in corpus (15)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in 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
• Statistical Mechanics of Community Detection
• Community Structure in Jazz
• Modularity and community detection in bipartite networks
• Towards real-time community detection in large networks
• Note on the equivalence of the label propagation method of community detection and a Potts model approach

Cited by in corpus (42)

• Community detection in graphs
• 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
• Advanced modularity-specialized label propagation algorithm for detecting communities in networks
• Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
• Robust network community detection using balanced propagation
• Local resolution-limit-free Potts model for community detection
• Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
• Large network community detection by fast label propagation
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• Online detection of temporal communities in evolving networks by estrangement confinement
• Multi-resolution community detection based on generalized self-loop rescaling strategy
• Universality of the stochastic block model
• Enhancing community detection by local structural information
• Identifying multi-scale communities in networks by asymptotic surprise
• Community detection by label propagation with compression of flow
• Detecting Communities in Tripartite Hypergraphs
• Label propagation for clustering
• Community detection based on significance optimization in complex networks
• The stability to instability transition in the structure of large scale networks
• Global disorder transition in the community structure of large-q Potts systems
• Distributed Community Detection in Dynamic Graphs
• Unfolding network communities by combining defensive and offensive label propagation
• Community detection for networks with unipartite and bipartite structure
• 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
• Local multiresolution order in community detection
• Role-based Label Propagation Algorithm for Community Detection
• The Atlas for the Aspiring Network Scientist
• Dissecting graph measure performance for node clustering in LFR parameter space
• Partitioning Graphs for the Cloud using Reinforcement Learning
• Detecting hierarchical and overlapping network communities using locally optimal modularity changes
• Weighted Label Propagation Algorithm based on Local Edge Betweenness
• Quantitative Function and Algorithm for Community Detection in Bipartite Networks
• Controlled Label Propagation: Preventing Over-Propagation through Gradual Expansion
• Optimisation dans la détection de communautés recouvrantes et équilibre de Nash
• Overlapping Community Detection Optimization and Nash Equilibrium
• Spiking label propagation for community detection
• A fast clustering algorithm for mining social network data
• A framework for community detection in heterogeneous multi-relational networks