Detecting network communities by propagating labels under constraints.

By Michael J. Barber, John W. Clark Jr.. Physical review. E, Statistical, nonlinear, and soft matter physics, 2009

358 citations recorded by the source corpus.

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.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/86f6694e2990a21d38ea3d05801c77e17ac48bba

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks (2010, background): “One of the most interesting is the algorithm developed in [2], where the update rule is modified in such a way that the objective function being optimised becomes the modularity [17] of the resulting clustering.”
Community detection in graphs (2009, background): “In order to eliminate undesired solutions, Barber and Clark introduced some constraints in the optimization process [324].”
A smart local moving algorithm for large-scale modularity-based community detection (2013, methodology): “The local moving heuristic has been quite popular in the literature (Barber & Clark, 2009; Blondel et al., 2008; Liu & Murata, 2010; Mei, He, Shi, Wang, & Li, 2009; Rotta & Noack, 2011; Schuetz & Caflisch, 2008; Ye, Hu, & Yu, 2008), probably in part because it can be implemented in an efficient way…”
A Comprehensive Survey on Community Detection With Deep Learning (2021, background): “A combination with the modularity forms a variation – Modularity-specialized LPA (LPAm) [51].”