Detecting network communities by propagating labels under constraints

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.

Figure 1

(Color online) An attempted optimization of the label-propagation algorithm produces dubious gains for the Southern women network. The modified LPAr frequently produces the trivial solution, with all vertices assigned to the same community. In the network considered, we expect at least two communities based on the ethnographic study from which the data are drawn.

Figure 2

Modularity $Q$ of community solutions from random networks with known community structures. Each point shows the average $Q$ over 1000 instances of the random networks in relation to the average number $z_{\text{out}}$ of intercommunity links for each vertex. The hybrid algorithm consists of allowing the standard LPA to run its course and find a solution, followed by application of LPAm to the LPA solution in order to ensure that a local maximum of $Q$ is reached. Error bars are smaller than the points.

Figure 3

Accuracy of community solutions from random networks with known community structures. Accuracy is quantified by the normalized mutual information $I_{\text{norm}}$ between the found and actual community solutions. Each point shows the normalized mutual information $I_{\text{norm}}$ over 1000 instances of the random networks in relation to the average number $z_{\text{out}}$ of intercommunity links for each vertex. The hybrid algorithm consists of allowing the standard LPA to run its course and find a solution, followed by application of LPAm to the LPA solution in order to ensure that a local maximum of $Q$ is reached. Error bars are smaller than the points.