Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity

Pan Zhang; Cristopher Moore

Source-linked AI summary

Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity

Pan Zhang, Cristopher Moore

arXiv:1403.5787v3Mar 23, 2014physics.soc-phcond-mat.stat-mechcs.SIstat.ML

TL;DR

Modularity maximization can overfit random structure and yield unstable, competing partitions. The paper instead treats modularity as a finite-temperature Hamiltonian and uses Belief Propagation to find consensus among high-modularity partitions. The method reaches the stochastic block model's detectability transition, performs well on real networks, and supports recursive hierarchical detection.

Problem
Modularity maximization can produce illusory communities in random graphs and poorly correlated, non-robust partitions in real networks.
Method
The method uses a finite-temperature Gibbs distribution for modularity and a scalable Belief Propagation algorithm to identify consensus among many high-modularity partitions.
Results
The algorithm succeeds down to the stochastic block model's detectability transition, finds significant communities in real networks, and recursively detects hierarchical structure.
Takeaways & Limitations
A retrieval state distinguishes statistically significant community structure from random fluctuations and supports choosing group numbers and decomposing networks hierarchically.

Abstract

from arXiv · show

Modularity is a popular measure of community structure. However, maximizing the modularity can lead to many competing partitions, with almost the same modularity, that are poorly correlated with each other. It can also produce illusory "communities" in random graphs where none exist. We address this problem by using the modularity as a Hamiltonian at finite temperature, and using an efficient Belief Propagation algorithm to obtain the consensus of many partitions with high modularity, rather than looking for a single partition that maximizes it. We show analytically and numerically that the proposed algorithm works all the way down to the detectability transition in networks generated by the stochastic block model. It also performs well on real-world networks, revealing large communities in some networks where previous work has claimed no communities exist. Finally we show that by applying our algorithm recursively, subdividing communities until no statistically-significant subcommunities can be found, we can detect hierarchical structure in real-world networks more efficiently than previous methods.

A. Results on the Stochastic Block Model

On stochastic block model networks, BP exhibits a retrieval phase between the paramagnetic and spin glass phases, finding statistically significant structure down to the detectability transition. The phase boundary agrees with theory, and the method achieves nearly the same partition overlap as an EM-based algorithm without its parameter-learning loop.

Comparison with ER graphs: In an ER graph, BP has only paramagnetic and spin glass phases, whereas the SBM additionally exhibits retrieval.For the ER example, the transition is at β∗ = 1.317; convergence time diverges at the phase transitions.
Phase behavior: In the example with ϵ = 0.2, retrieval begins at βR = 1.072 and reaches modularity 0.393 before the spin glass transition at βSG = 2.27.The planted partition has modularity Mhidden(ϵ) = 0.33 in this comparison.
Phase behavior: The SBM has paramagnetic, retrieval, and spin glass phases, with the retrieval phase representing statistically significant community structure.For q = 2 and c = 3, the retrieval phase appears between the other two phases when community structure is sufficiently strong.
Phase behavior: For ϵ < ϵ∗≈0.267, BP finds a retrieval state between βR and βSG.The detectability threshold is ϵ∗, and the retrieval-state interval is βR < β < βSG.
Theory and accuracy: The measured boundary βR is in excellent agreement with the theoretical expression, while the spin glass instability occurs above β∗(2, 3).The phase diagram estimates βR experimentally and compares it with the analytic prediction.
Theory and accuracy: At β = β∗, the algorithm succeeds throughout the easily detectable regime even when SBM parameters are unknown.Its retrieval partition has nearly the same overlap as an EM-based method without the additional EM loop.

B. Results on real-world networks and choosing the number of groups

On real-world networks, the method finds retrieval states with high ground-truth overlap, identifies statistically significant large-scale communities, and provides a principled way to select the number of groups.

The algorithm uses β = β∗(q∗, c) in real-world networks, although this temperature is not optimal and varying β may improve performance.The setting nevertheless appears to work well in practice.
The retrieval modularity stops growing when q exceeds the correct number of groups, providing a principled model-selection procedure.For networks with known q∗, the procedure agrees perfectly with the ground truth.
The method finds retrieval states with high retrieval modularity and high overlap with ground truth across the evaluated real-world networks.For Gnutella, Epinions, and web-Google, it identifies significant large-scale communities despite the absence of known ground truth.
For the disassortative David Copperfield network, the method finds a retrieval state with negative modularity and high ground-truth overlap using β = −β∗(q∗, c).Nouns are more likely to be adjacent to adjectives than to other nouns, producing disassortative structure.
Table I reports retrieval modularity, ground-truth overlap, selected q∗, β∗, and convergence time for several real-world networks.The table includes networks without known ground truth, for which the authors claim significant large-scale communities.

C. Results on hierarchical clustering

Recursive application of the algorithm detects hierarchical structure by subdividing communities until no retrieval state remains. In the political blog network, it finds a five-level hierarchy with 14 subgroups.

The algorithm recursively determines q∗, divides the network into subgraphs, and stops when no retrieval state indicates significant internal structure.This procedure is intended to detect communities and subcommunities at multiple scales.
For SBM subgraphs and some small real-world networks, no retrieval state is found after the first division, whereas larger networks can yield repeated retrieval states and deep hierarchies.Zachary’s karate club is an example that stops after one level.
The political blog network reaches a hierarchy 5 levels deep with 14 subgroups after initially identifying liberal and conservative communities.The first division agrees with ground-truth labels on 95% of nodes; modularity decreases from 0.426 at level 2 to 0.282 at level 5.
Compared with a nested SBM analysis reporting 17 subgroups, this method reports 14, while the first three subdivision levels are similar.The comparison concerns the same political blog network.

D. Comparison with other algorithms

Compared with Louvain and OSLOM, the BP method better matches planted structure near the detectability transition, avoids overfitting random graphs, and recovers larger communities with similar modularity.

The comparison section evaluates BP against Louvain and OSLOM, with OSLOM specifically designed to focus on statistically significant communities.The subsequent results assess accuracy and inferred group counts.
On Gnutella and Epinions, BP finds q∗ = 7 and q∗ = 4 groups with modularities 0.517 and 0.429, while Louvain finds 66 and 949 groups with modularities 0.499 and 0.430.The similar modularities accompany substantially larger-scale communities under BP.
Figure 4 compares recursive political-blog partitioning with its adjacency matrix after nodes are ordered by the final hierarchy.Leaves encode nodes, sizes encode degree, and colors encode final groups.
Louvain and OSLOM lose NMI well below the SBM detectability transition, while BP retains accurate recovery in that regime.Figure 5 evaluates SBM networks with n = 10^4, c = 6, and q = 6, with the transition at ϵ = 0.195.
On ER graphs with c = 4, BP correctly infers q∗ = 1, whereas the other algorithms overfit by finding increasingly many small communities as n grows.Each point in Figure 5 averages 20 instances.

II. DISCUSSION

The discussion frames BP as a scalable consensus method for statistically significant community detection, using retrieval states to select group counts and expose hierarchy. It also identifies extensions and remaining performance trade-offs.

The method uses modularity without explicitly fitting a generative or graphical model.It avoids direct modularity maximization, which is computationally difficult and prone to overfitting.
BP estimates Gibbs-distribution marginals and assigns each node to its most-likely community, thereby seeking consensus among many high-modularity partitions.The retrieval partition is based on these marginal probabilities.
A retrieval state distinguishes statistically significant structure from random fluctuations and supports selecting the number of groups and recursively decomposing networks.The contrasting spin-glass state fluctuates among unrelated local optima.
For fixed β, modularity is linearly related to the DCSBM log-likelihood, but the method does not need EM parameter learning or model selection between SBM variants.β remains a tunable parameter.
The hierarchical algorithm provides evidence of overcoming the resolution limit on a ring of cliques by recovering the cliques at the second level.The resolution limit makes communities of size O(√n) or less difficult to find.
The non-backtracking-matrix method can infer more groups on some networks, possibly because it detects deeper hierarchical subcommunities, but a detailed comparison remains open.The political blog network is given as an example.
The method could be extended to weighted or γ-generalized modularity and to other objectives such as normalized cut or conductance.These are proposed directions rather than evaluated extensions in the supplied discussion.
Decimation or reinforcement might improve performance, but would add running time or remains future work.Decimation repeatedly fixes the most biased labels and reruns BP; reinforcement adds external fields toward likely configurations.

A. Defining statistical significance

The paper defines statistical significance through a retrieval phase in which many high-modularity partitions are correlated with one another and with the ground truth. This contrasts with random graphs, where high-modularity partitions are numerous but mutually uncorrelated.

A. Defining statistical significance: In random graphs, many high-modularity partitions are nearly uncorrelated, so selecting one optimum can overfit noise.The partition landscape is described as glassy, with alternatives far apart in Hamming distance.
A. Defining statistical significance: In networks with community structure, correlated high-modularity partitions form a smooth valley around the ground truth.At a suitable temperature, this retrieval phase combines low energy, high modularity, and high entropy.
A. Defining statistical significance: The retrieval phase serves as a physics-based definition of statistically significant community structure.The maximum-marginal retrieval partition is presented as an optimal prediction of node groups when this phase exists.
A. Defining statistical significance: Unlike stochastic-block-model approaches, the method avoids an explicit generative model and focuses directly on modularity.The comparison concerns both the model specification and the energy used to define the Gibbs distribution.

B. The cavity method and belief propagation

The paper uses Belief Propagation, or the cavity method, to estimate Gibbs marginals and Bethe free energy on sparse networks. Its message updates are scalable, with fixed-group iterations linear in the number of edges.

B. The cavity method and belief propagation: MCMC is considered prohibitively slow because estimating marginals requires many independent samples and free energy requires sampling across temperatures.This motivates replacing sampling with message passing.
B. The cavity method and belief propagation: Belief Propagation uses a tree-based conditional-independence approximation to estimate marginals and Bethe free energy on sparse networks.The approximation is exact only on trees but is reported as accurate in the detectable SBM regime and typical real-world graphs.
B. The cavity method and belief propagation: BP messages estimate a node’s group marginal from its interactions with neighboring nodes while excluding the recipient node.The messages are passed from node i to node k and condition on i’s other interactions.
B. The cavity method and belief propagation: The BP equations include an external field for each group, updated after every iteration.The neighborhood notation and external-field update are part of the sparse-network formulation.
B. The cavity method and belief propagation: For q groups and m edges, each iteration takes O(qm), becoming linear in edges when q is fixed.The updates are also easily parallelized, and convergence iterations depend weakly on network size empirically.

C. The factorized solution and local stability

The analysis distinguishes a factorized paramagnetic solution from a retrieval state and a spin glass state using BP stability. On stochastic block model networks, the retrieval state persists down to the Kesten–Stigum detectability transition.

C. The factorized solution and local stability: The factorized solution assigns every node equally to every group and yields zero retrieval modularity.This solution is called the paramagnetic state.
C. The factorized solution and local stability: The retrieval partition assigns each node to its most-likely community, representing the consensus of correlated high-modularity partitions.Its retrieval modularity measures statistically significant community structure.
C. The factorized solution and local stability: When BP fails to converge, its current retrieval modularity fluctuates and does not represent a stable consensus.The failure reflects an unstable landscape with exponentially many partition clusters and replica-symmetry breaking.
C. The factorized solution and local stability: cλ2 > 1 is the local-stability condition under which the factorized fixed point becomes unstable to random noise on locally tree-like Poisson graphs.Here c is the average degree, or average excess degree for other degree distributions.
C. The factorized solution and local stability: The BP stability calculation assumes a network random conditional on its degree distribution.For real-world networks, the heuristic β = β∗ can fail if β∗ lies outside the retrieval phase, requiring a nearby temperature scan.
C. The factorized solution and local stability: The retrieval state exists down to the Kesten–Stigum transition, where µ = √c and the retrieval phase disappears.At this boundary, the relevant eigenvalue enters the bulk of the non-backtracking matrix spectrum.

D. Defining the spin glass phase

The paper identifies the spin glass phase with unstable BP behavior and rapidly changing partitions, while contrasting it with the retrieval phase. Numerical phase diagrams show retrieval transitions and distinguish structured networks from Erdős–Rényi graphs.

D. Defining the spin glass phase: The spin glass phase is associated with divergent susceptibility and broken replica symmetry, but the true phase diagram may be more complicated.The identification is reliable when the phase appears continuously, but not necessarily when it appears discontinuously.
D. Defining the spin glass phase: In the hard-but-detectable phase, BP can miss a lower-free-energy retrieval state because its basin of attraction is exponentially small.The paper states that one-step replica-symmetry-breaking equations would be needed to detect this phase.
D. Defining the spin glass phase: The BP update uses messages representing cavity estimates of node-group marginals, with normalization factors for one- and two-point marginals.BP fixed points are stationary points of the Bethe free energy.
D. Defining the spin glass phase: Sparse-network updates replace non-neighbor effects with an external field, reducing the iteration cost to qm.For fixed q, this is linear in the number of edges.
D. Defining the spin glass phase: In SBM experiments, the retrieval transition is marked by lower Bethe free energy, nonzero retrieval modularity, and diverging convergence time.For Erdős–Rényi graphs, apparent modularity instead enters the spin glass phase, where BP fails to converge and the modularity fluctuates.

Appendix B: Relation with the degree-corrected stochastic block model

The appendix relates the finite-temperature modularity approach to the degree-corrected stochastic block model and shows how retrieval modularity supports model selection and hierarchical subdivision. It also documents performance across degree distributions and a limitation of free-energy-based selection on real-world networks.

Relation to the DCSBM: The modularity Gibbs distribution is exactly equivalent to a degree-corrected stochastic block model for suitable parameters, sharing its free energy and ground state.This establishes a formal connection while retaining modularity as the direct definition of community structure.
Relation to the DCSBM: The approach uses one temperature parameter β instead of fitting DCSBM parameters with expectation-maximization.Communities can usually be detected at β = β∗, or by scanning a small region around it.
Choosing the number of groups: On real-world networks, retrieval modularity indicates the appropriate group count q∗, whereas DCSBM free energy can continue decreasing as q exceeds q∗.For the SBM, retrieval modularity stops growing at the known q∗ and remains nearly independent of β in the retrieval phase.
Empirical behavior: The method performs similarly on Poisson-degree SBM networks and heavy-tailed networks such as LFR and political blogs, without selecting between SBM and DCSBM.The appendix contrasts this with approaches requiring explicit model selection.
Limitations: Free-energy model selection works well on synthetic graphs but continues decreasing with q on real-world networks, so its reliability outside SBM-generated data is unclear.This motivates using retrieval modularity as a guide for the number of groups on real-world networks.
Hierarchical structure: Recursively splitting communities and stopping when q∗ = 1 yields hierarchical structure, correctly recovering individual cliques after an intermediate multi-clique split.In a power-law network without community structure, BP selects q∗ = 1 while competing methods overfit with increasingly many groups.