Detecting network communities by propagating labels under constraints

Michael J. Barber; John W. Clark

Source-linked AI summary

Detecting network communities by propagating labels under constraints

Michael J. Barber, John W. Clark

arXiv:0903.3138v2Mar 18, 2009physics.data-anphysics.soc-ph

TL;DR

The paper asks whether LPA's optimization objective corresponds to meaningful network communities. It reformulates LPA mathematically, identifies the resulting conceptual and practical drawbacks, and develops constrained variants, including one that maximizes modularity. The variants produce good community results, but no variant is clearly superior across the considered networks.

Problem
LPA's objective can increase without producing better communities, and its globally optimal all-one-label solution is uninformative.
Method
The paper reformulates LPA as optimization of same-label edges, then adds penalty terms to propagate labels subject to constraints, including a modularity-based variant.
Results
The main label-propagation variants give good community results across the considered networks, but no variant is clearly superior.
Takeaways & Limitations
Label propagation is a promising basis for specialized community-detection methods when its strengths and drawbacks are understood.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper reframes label propagation as an optimization problem, exposing a mismatch between its objective and meaningful community quality. It then proposes constrained label-propagation algorithms, including a modularity-maximizing variant.

Label propagation assigns each vertex a unique label, repeatedly replaces labels with the most frequent neighboring label, and identifies communities by shared labels.The procedure is conceptually simple, easy to implement, and practically efficient.
The reformulation defines an objective function based on edges joining identically labeled vertices and shows that LPA finds its local optima.
Increasing the objective function need not improve communities according to the intended concept of community structure.Escaping local maxima can therefore make practical improvement of standard LPA difficult.
Adding penalty terms produces constrained label-propagation algorithms, including a variant that strictly maximizes modularity while retaining standard LPA's favorable computational complexity.The algorithms are evaluated on a model network and real-world networks.
The paper compares several variants for both unipartite and bipartite networks, with implementation and performance discussed across the paper.

II. THE LABEL PROPAGATION ALGORITHM

Community detection requires both a workable definition of community and methods that can operate on networks of relevant size. The paper contrasts modularity-based partitioning with LPA, emphasizing LPA's simplicity, efficiency, and varied empirical context.

Community identification must address both the imprecise definition of a community and the practical realizability of solutions for networks of different sizes.Network size can be characterized by the number of vertices n or edges m.
Modularity evaluates a vertex partition by comparing within-community edges with those expected under a degree-based null model.Finding the global maximum is generally infeasible for all but the smallest networks, so heuristics are used.
LPA defines communities procedurally by propagating the most frequent neighboring labels from initially unique vertex labels.
Each LPA relabeling iteration is linear in the number of graph edges, and over 95% of vertices receive final labels within five iterations in cited studies.
Prior work reported that LPA extensions could analyze networks with tens of millions of edges in a few minutes on a desktop PC.Other work also raised concerns about potentially meaningless communities and many distinct solutions.

III. AN OBJECTIVE FUNCTION FOR LABEL PROPAGATION

The paper gives LPA an equivalent optimization formulation in which labels maximize an objective tied to same-label edges. This reveals that the trivial all-one-label assignment is globally optimal, while ordinary runs reach local optima or limit cycles.

The mathematical reformulation treats LPA as an optimization procedure whose objective function characterizes the community solutions it finds.
For a vertex, the update chooses the label maximizing the sum of adjacency weights to neighboring vertices carrying that label, with specified tie handling.The formulation applies equally to weighted networks because it does not rely on binary adjacency values.
The objective H counts edges connecting vertices with identical labels, equivalently corresponding to a ferromagnetic Potts-model Hamiltonian.
Because the update maximizes the label-dependent term while other terms remain fixed, H never decreases and the process reaches a local maximum or limit cycle.
The globally optimal solution is the uninformative assignment in which every vertex has the same label; other solutions are local maxima of H.Local-search dynamics avoid this trivial solution through becoming trapped away from the global optimum.

IV. DRAWBACKS OF LABEL PROPAGATION

The paper shows that optimizing the LPA objective H can diverge from producing meaningful communities, with attempts to improve search sometimes yielding trivial solutions. The resulting quality must be judged using considerations beyond H.

Attempts to escape local maxima of H can be counterproductive because high-H solutions may be practically useless.The authors describe the LPA’s practical success as arising partly from remaining in frustrated local equilibria rather than reaching the global maximum.
The LPA objective H corresponds poorly to the conceptual quality of communities, so increasing H need not improve the partition.
For the Southern women network, LPA optimization is difficult to assess because H provides no mechanism for testing community quality.Quality instead requires auxiliary considerations such as the number of communities or modularity Q.
A tie-breaking optimization in LPAr frequently assigns every vertex to one community, despite the Southern women network being expected to contain at least two communities.

V. CONSTRAINED LABEL PROPAGATION

The paper modifies the LPA objective by adding penalty terms that constrain undesirable solutions. These constraints produce variants for unipartite and bipartite networks, including algorithms that locally maximize modularity.

The modified objective H′ combines the original objective H with a penalty term G weighted by parameter λ.The paper examines several possible choices for G to eliminate undesirable solutions.
G1 penalizes the trivial all-same-label solution by favoring groups of similar size.Its value is smallest when every vertex has a unique label and largest when all vertices share one label.
G2 instead encourages groups with similar total degree and also works to avoid the trivial all-same-label optimum.The total degree K_l is defined for vertices carrying label l.
LPAm uses the G2-based construction so label propagation can locally maximize the standard modularity Q while retaining the standard LPA’s favorable computational complexity.
LPAb adapts constrained label propagation to bipartite modularity by treating the two vertex parts separately in the null model and modularity calculation.The two parts have no within-part edges, and the corresponding sums are restricted to opposite-colored vertices or encoded with separate degree measures.

A. Unipartite networks

The unipartite-network experiments compare label-propagation variants using modularity and normalized mutual information on model and real networks. Modularity falls as inter-community connectivity increases, while real-network results show no variant is clearly superior.

Evaluation setup: The study compares LPA, LPAm, LPAr, and a hybrid LPA-plus-LPAm algorithm using modularity Q as the principal quality measure.The hybrid first runs LPA, then applies LPAm to reach a local maximum of Q.
Random networks: Q drops as the average number zout of inter-community links per vertex increases in 1000 random-network instances.The model networks contain four communities of 32 vertices with controlled within- and between-community connection probabilities.
Random networks: Normalized mutual information Inorm decreases from 1 to 0 as zout increases, measuring agreement between found and known communities.Inorm = 1 indicates matching partitions, whereas Inorm = 0 indicates independence.
Random networks: The modularity and accuracy figures use averages over 1000 random-network instances and compare results against known community structures.Figure 2 reports Q, while Figure 3 reports Inorm for the same community solutions.
Real networks: Across the tested real networks, no label-propagation variant is clearly superior, although LPAr performs best on the two large co-authorship networks.The variants produce modularity values similar to those obtained with the GAH approach.

B. Bipartite networks

For bipartite networks, label-propagation variants were evaluated with bipartite modularity QB across four real-world networks. LPAb reduces trivial all-vertex solutions in the Southern women network but is less successful elsewhere, while LPAr performs best on larger networks.

B. Bipartite networks: Four real-world bipartite networks were evaluated using LPA, LPAb, LPAr, and an LPA–LPAb hybrid.Each algorithm was applied one hundred times, with maximum and mean QB values reported.
B. Bipartite networks: LPAb improves average QB on the Southern women network by reducing frequent trivial solutions that assign every vertex to one community.The effect is attributed to inclusion of constraint G3.
B. Bipartite networks: LPAr is clearly worst on the Southern women network, consistent with its tendency to assign all vertices the same label.This behavior is also reported in connection with Fig. 1.
B. Bipartite networks: LPAb performs similarly to LPA on Scotland’s corporate-interlocks network but is outperformed by other variants on the remaining networks.LPAr provides the best results for the larger networks, contrasting with its poor Southern women result.
B. Bipartite networks: Label-propagation variants generally produce lower QB values than communities found by a greedy agglomerative hierarchical approach.The comparison concerns reported community-quality values rather than identical optimization procedures.

VII. DISCUSSION

The discussion interprets LPA as optimization and identifies a mismatch between its objective and meaningful community quality. Constrained variants address this mismatch, but performance varies and modularity-based approaches have important scope limitations.

VII. DISCUSSION: LPA’s objective counts same-label edges, yet increasing it need not improve community quality; its global optimum places all vertices in one community.Useful solutions therefore depend on reaching local maxima rather than the uninformative global maximum.
VII. DISCUSSION: Constrained variants avoid the all-vertex solution, with LPAm targeting local maxima of modularity Q and LPAb targeting local maxima of bipartite modularity QB.These variants modify the objective function through constraints.
VII. DISCUSSION: Modularity-based constraints favor communities of similar total degree, creating difficulties when actual community sizes are diverse.The same concern extends to QB, where relevant size is the geometric mean of total degrees across the two network parts.
VII. DISCUSSION: All main variants give good community results, but no variant is clearly superior without prior information about community number, size, or nature.Performance differences suggest that the variants explore different portions of the community-solution space.
VII. DISCUSSION: Compared with greedy agglomerative hierarchical methods, label propagation offers no modularity advantage and may be disadvantageous for bipartite networks.The authors caution that modularity is neither the only quality measure nor free of drawbacks, and call for broader performance characterization.
VII. DISCUSSION: LPAm is not clearly best in Q despite directly maximizing Q, because the variants use modularity in fundamentally different roles.Other variants achieve higher Q on some tested networks.
VII. DISCUSSION: The authors regard label propagation as promising and suitable as a basis for specialized community-detection methods and other network applications.They emphasize understanding both its strengths and drawbacks before further applications.

APPENDIX A: A LABEL-PROPAGATION ALGORITHM FOR MAXIMIZING MODULARITY

Appendix A derives LPAm by expressing modularity maximization as constrained label propagation while preserving the standard algorithm’s linear-in-edges implementation complexity.

APPENDIX A: A LABEL-PROPAGATION ALGORITHM FOR MAXIMIZING MODULARITY: Each standard label-relabeling iteration costs O(m), or O(n) when network vertices scale with edges.Here m is the number of edges and n the number of vertices.
APPENDIX A: A LABEL-PROPAGATION ALGORITHM FOR MAXIMIZING MODULARITY: LPAm is implemented by imposing constraint G2 so the label-propagation objective reproduces modularity Q.The appendix identifies G2 as the constraint used for the modularity-maximizing variant.
APPENDIX A: A LABEL-PROPAGATION ALGORITHM FOR MAXIMIZING MODULARITY: The derivation removes constant diagonal self-interaction terms by shifting the objective function without changing the locations of its maxima.An arbitrary constant is added before eliminating diagonal elements.
APPENDIX A: A LABEL-PROPAGATION ALGORITHM FOR MAXIMIZING MODULARITY: Setting B_uv = A_uv − λk_uk_v yields the matrix form associated with LPAm.The first term retains neighbor-label counting, while the degree-based terms are tracked through label volumes K_l.
APPENDIX A: A LABEL-PROPAGATION ALGORITHM FOR MAXIMIZING MODULARITY: The modified label-propagation rule can be implemented in O(m) worst-case time per pass through the vertices.Neighbor-label counts, label-volume updates, and unused-label access are organized to maintain this complexity.

APPENDIX B: A LABEL-PROPAGATION ALGORITHM FOR MAXIMIZING BIPARTITE MODULARITY

Appendix B adapts constrained label propagation to bipartite modularity by symmetrizing the objective before deriving LPAb. Efficient updates preserve O(m) worst-case time per iteration.

APPENDIX B: A LABEL-PROPAGATION ALGORITHM FOR MAXIMIZING BIPARTITE MODULARITY: The bipartite modularity objective QB is rewritten using symmetry and index exchange so it can be represented by a symmetric matrix.Averaging the transformed expressions produces a form suitable for the standard label-propagation update rule.
APPENDIX B: A LABEL-PROPAGATION ALGORITHM FOR MAXIMIZING BIPARTITE MODULARITY: Because A_uv − λk_ud_v is generally asymmetric, the direct update rule cannot be applied without first defining a rule for the transformed objective.The symmetrized formulation resolves this compatibility issue.
APPENDIX B: A LABEL-PROPAGATION ALGORITHM FOR MAXIMIZING BIPARTITE MODULARITY: The symmetrized objective is converted into the LPAb update rule for bipartite modularity.The conversion parallels the derivation used for the unipartite modularity-maximizing variant.
APPENDIX B: A LABEL-PROPAGATION ALGORITHM FOR MAXIMIZING BIPARTITE MODULARITY: Updating K_l and D_l when labels change allows each LPAb iteration to retain O(m) worst-case time complexity.The implementation details are stated to be similar to those in Appendix A.