Detecting network communities by propagating labels under constraints
Top Cited Papers
- 28 August 2009
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 80 (2), 026129
- https://doi.org/10.1103/physreve.80.026129
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.Keywords
Other Versions
This publication has 21 references indexed in Scilit:
- Towards real-time community detection in large networksPhysical Review E, 2009
- On the equivalence of the label propagation method of community detection and a Potts model approachPhysica A: Statistical Mechanics and its Applications, 2008
- Near linear time algorithm to detect community structures in large-scale networksPhysical Review E, 2007
- Statistical mechanics of community detectionPhysical Review E, 2006
- Comparing community structure identificationJournal of Statistical Mechanics: Theory and Experiment, 2005
- Finding community structure in very large networksPhysical Review E, 2004
- Fast algorithm for detecting community structure in networksPhysical Review E, 2004
- Detecting community structure in networksZeitschrift für Physik B Condensed Matter, 2004
- Finding and evaluating community structure in networksPhysical Review E, 2004
- Application of statistical mechanics to NP-complete problems in combinatorial optimisationJournal of Physics A: General Physics, 1986