Source-linked AI summary
Consistency of community detection in networks under degree-corrected stochastic block models
Yunpeng Zhao, Elizaveta Levina, Ji Zhu
TL;DR
Community detection needs consistency theory beyond the standard stochastic block model because real networks can contain hubs and substantial degree variation within communities. The paper extends that theory to the degree-corrected model and compares likelihood and modularity criteria, finding broader consistency for degree-corrected methods but practical costs from estimating more parameters.
Problem
The standard stochastic block model assumes within-community stochastic equivalence, limiting its fit to networks with hubs or highly variable node degrees, while consistency results for degree-corrected models were unavailable.
Method
The paper generalizes the consistency framework to the degree-corrected stochastic block model and evaluates four community-detection criteria under standard and degree-corrected models.
Results
Degree-corrected methods are consistent under broader models, while modularity requires parameter constraints for consistency and likelihood-based methods do not.
Takeaways & Limitations
Degree correction is practically worthwhile primarily when node degrees within communities are highly variable, because it requires estimating many more parameters.
Takeaways & Limitations
The analysis assumes K is known, although determining the number of communities is generally difficult and remains an open problem.
Abstract
from arXiv · showhide
Community detection is a fundamental problem in network analysis, with applications in many diverse areas. The stochastic block model is a common tool for model-based community detection, and asymptotic tools for checking consistency of community detection under the block model have been recently developed. However, the block model is limited by its assumption that all nodes within a community are stochastically equivalent, and provides a poor fit to networks with hubs or highly varying node degrees within communities, which are common in practice. The degree-corrected stochastic block model was proposed to address this shortcoming and allows variation in node degrees within a community while preserving the overall block community structure. In this paper we establish general theory for checking consistency of community detection under the degree-corrected stochastic block model and compare several community detection criteria under both the standard and the degree-corrected models. We show which criteria are consistent under which models and constraints, as well as compare their relative performance in practice. We find that methods based on the degree-corrected block model, which includes the standard block model as a special case, are consistent under a wider class of models and that modularity-type methods require parameter constraints for consistency, whereas likelihood-based methods do not. On the other hand, in practice, the degree correction involves estimating many more parameters, and empirically we find it is only worth doing if the node degrees within communities are indeed highly variable. We illustrate the methods on simulated networks and on a network of political blogs.
1. Introduction.
The paper frames community detection as a fundamental network-analysis problem and motivates principled consistency comparisons because standard block models poorly accommodate degree variation and hubs.
- Motivation: Community detection seeks groups of nodes that are more similar to one another than to nodes in other groups.It is a fundamental problem with applications across social networks, gene regulation, recommender systems, and security monitoring.
- Existing methods: Global-criterion methods optimize network partitions using tools such as graph cuts, spectral clustering, and modularity.Model-based methods instead fit probabilistic network models with communities.
- Theoretical gap: Consistency theory provides a principled way to compare detection criteria as the number of nodes grows, but earlier results focused on the stochastic block model.That model treats nodes sharing a community label as stochastically equivalent.
- Theoretical gap: The degree-corrected stochastic block model accommodates hubs, yet consistency results and general method comparisons were unavailable for it.Prior examples indicated that it fits data with hubs better than the standard block model.
- Paper approach: The paper generalizes the consistency framework, evaluates modularity and block-model criteria, and distinguishes assumed models from criteria used to optimize partitions.It argues that model-derived criteria are consistent when their assumed model holds, while implicit parameter assumptions can impose additional constraints.
- Paper organization: The article develops models and criteria, states consistency results, proves a general theorem, compares simulated performance, and analyzes political blogs.The sections proceed from setup and theory to simulations, an application, and discussion.
2. Network models and community detection criteria.
The paper defines network partitions and block-model criteria, including degree correction, then contrasts likelihood-based and modularity-based objectives and their consistency conditions.
- Network setup: A network is represented by a binary symmetric adjacency matrix, and community detection seeks a disjoint partition into K labeled groups.The analysis considers unweighted, undirected networks.
- Block models: The stochastic block model assumes independent Bernoulli edges whose probabilities depend on the labels of their endpoint communities.The community-probability matrix is symmetric, and self-loops are allowed for simpler notation.
- Block models: The degree-corrected model assigns each node a degree parameter θ_i that reflects its individual propensity to form ties.The parameters require an identifiability constraint, and the paper uses a Poisson likelihood to simplify derivations.
- Likelihood criteria: Profile-likelihood criteria optimize fitted block-model objectives over partitions, with degree correction reducing to the regular block model when all θ_i are equal.The paper reports identical practical solutions for Poisson and Bernoulli versions of the likelihood criteria.
- Modularity criteria: Modularity compares observed within-community edges with expected edges under a null model, producing Erdos–Renyi or Newman–Girvan variants depending on that choice.The Erdos–Renyi null uses a constant edge probability, whereas the degree-corrected null uses probabilities proportional to θ_iθ_j and can be estimated from node degrees.
- Criterion comparison: Likelihood criteria use all links and their community endpoints, whereas modularity is unchanged when between-community links are randomly permuted without becoming within-community links.Degree correction substitutes aggregate degree quantities for community-size quantities in both criterion families.
- Consistency results: Under degree-corrected models, Newman–Girvan modularity and degree-corrected block-model criteria are consistent, while Erdos–Renyi modularity and regular block-model criteria are not.Likelihood methods require no parameter restrictions under their assumed model, whereas modularity requires a stronger-within-than-between links condition.
3. Consistency of community detection criteria.
The paper evaluates consistency of community-detection criteria under standard and degree-corrected stochastic block models. Degree-corrected criteria cover broader models, while modularity requires stronger within-community-link conditions and likelihood criteria do not.
- Consistency framework: Consistency is defined asymptotically, with strong consistency requiring no errors and weak consistency requiring the expected degree λ_n to diverge.Label equality is understood up to community-label permutations.
- Model assumptions: The analysis treats community labels and degree parameters as latent random variables, allowing dependence between them and normalizing E[θ_i] = 1.Edges are conditionally independent Bernoulli variables, with self-loops allowed for notational simplicity.
- Modularity criteria: Newman–Girvan modularity is strongly consistent when λ_n/log n →∞ and weakly consistent when λ_n →∞ under degree-corrected models satisfying its parameter constraints.These constraints essentially require within-community links to be more likely than between-community links.
- Modularity criteria: Erdos–Renyi modularity is consistent under the standard block model with λ_n/log n →∞ for strong consistency and λ_n →∞ for weak consistency, but not under the degree-corrected model.In a counterexample, grouping nodes by degree-variable value achieves Q_ERM = 0.0135 versus 0.0125 for the true partition.
- Likelihood criteria: The degree-corrected likelihood criterion is consistent under the degree-corrected model, whereas the standard block-model criterion is consistent under the standard model but not necessarily under degree correction.Both likelihood-based criteria require no parameter constraints and have the same strong and weak degree-growth thresholds under their respective models.
- Practical comparison: Although theory favors likelihood and degree-corrected criteria, practical selection depends on optimization cost and degree heterogeneity within communities.Degree correction estimates many more parameters and may be less useful when within-community degrees do not vary widely.
4. A general theorem on consistency under degree-corrected stochastic block models.
The paper develops a general sufficient-condition framework for consistency under degree-corrected stochastic block models. It represents a broad class of criteria through population-level functions and derives the specific consistency results as corollaries.
- General criterion form: A broad class of community-detection criteria can be expressed as functions of network summary quantities, including graph cuts and all criteria studied earlier.The framework targets consistency of criteria of this form under degree-corrected block models.
- Population criterion: The population version of a criterion replaces sample summaries with conditional expectations represented by H(S) and h(S), yielding F(H(S),h(S)).The generic array S encodes population assignments and is constrained to preserve the appropriate community-mass structure.
- Sufficient condition: Consistency requires the population criterion to be maximized by the true partition, up to a permutation of community labels.The matrix E represents this permutation equivalence, while the identity choice is used for exposition.
- Main theorem: The general theorem establishes strong consistency for any criterion of the specified form when its model, population-maximization, and regularity conditions hold.The theorem generalizes an earlier result from standard stochastic block models and implies all consistency results in Section 3.
5. Numerical evaluation.
Simulations compare four community-detection criteria under regular and degree-corrected block models, varying degree heterogeneity, community balance, network sparsity, and degree distributions. Degree-corrected likelihood and Newman–Girvan modularity generally handle degree variation best, while model mismatch and overfitting affect other criteria.
- 5.1. The degree-corrected stochastic block model.: Under balanced degree-corrected models, degree-corrected likelihood and Newman–Girvan modularity perform best in dense networks, while regular block-model likelihood deteriorates rapidly as degree variation increases.Erdos–Renyi modularity is more robust to degree variation than block-model likelihood, but both can group nodes by similar degrees.
- 5.1. The degree-corrected stochastic block model.: Sparser networks reduce performance for all criteria, with larger effects when degree variance is high because fewer links provide less information for fitting.The sparsity penalty is especially pronounced as m increases.
- 5.2. The standard stochastic block model.: Under the standard block model, all criteria are consistent, but performance generally improves as community sizes become more balanced, with block-model likelihood performing best overall.Degree-corrected methods can overfit this setting by treating ordinary degree variation as signal rather than noise.
- 5.3. Unbalanced community sizes.: With unbalanced communities, modularity performs much worse in sparse networks, while degree-corrected likelihood can overfit in the sparsest case when m = 1.In dense networks, performance at π = 0.3 is similar to the balanced case at π = 0.5.
- 5.4. A different degree distribution.: For a mixture degree distribution with m = 10, degree-corrected likelihood and Newman–Girvan modularity remain effective, indicating that discreteness of the degree parameters is not crucial.Erdos–Renyi modularity improves as α increases, consistent with greater robustness to degree variation.
6. Example: The political blogs network.
The political-blog network compares four community-detection criteria against manually assigned liberal and conservative labels. Newman–Girvan modularity and the degree-corrected model agree most closely with the truth, while degree variation exposes weaknesses in other approaches.
- The network contains US political blogs connected by hyperlinks, with manually assigned liberal or conservative labels used as ground truth.
- 0.819 adjusted Rand index was achieved by both Newman–Girvan modularity and the degree-corrected model, which differed on only four nodes.This was the highest adjusted Rand index among the methods.
- 0.793 adjusted Rand index was achieved by Erdos–Renyi modularity, slightly below the Newman–Girvan and degree-corrected results.
- The block-model likelihood separated nodes by low and high degree rather than matching the political labels as closely.
- 0.092 adjusted Rand index resulted from eigendecomposition of Erdos–Renyi modularity, compared with 0.819 from tabu search.The corresponding Newman–Girvan values were 0.781 and 0.819.
- Node area represents logarithmic degree, while colors represent community labels in the political-blogs visualization.
7. Summary and discussion.
The paper develops a general consistency framework for degree-corrected stochastic block models and applies it across four detection criteria. Its theory agrees with empirical evidence, but theoretical consistency does not always predict the best practical performance.
- The general tool extends consistency analysis from the standard to the more general degree-corrected stochastic block model.The degree-corrected framework includes the regular block model as a special case.
- Four community-detection criteria receive consistency results under the unified framework.
- The analysis separates the model assumed to derive a criterion from the model assumed true when analyzing that criterion.
- Parameter constraints are required when methods implicitly rely on them, with different conditions for the two modularity methods.
- Theoretical consistency agrees with simulation and data analysis, although methods with stronger theoretical properties do not always perform best in practice.
- The analysis assumes K is known, while determining K is generally a difficult open problem.The paper also identifies growing K, approximate eigendecomposition solutions, and sparse networks as further open areas.
APPENDIX
The appendix supplies proof details for the consistency results, using empirical-to-population approximations, concentration arguments, continuity, and uniqueness of population maximizers. It establishes weak and strong consistency through successive bounds.
- The proofs interpret R, V, ˆΠ, f, and f 0 as empirical or population distributions associated with estimated labels, true labels, and degree parameters.
- The proof first approximates 1/µn Okl by ˆTkl(e), then approximates ˆTkl(e) by Tkl(e).
- Bernstein’s inequality provides a concentration lemma used before establishing the general consistency theorem.
- Uniform closeness to the population criterion is combined with continuity and convergence of ˆΠ to control empirical criterion differences.
- Weak consistency follows after bounding the relevant terms, and strong consistency follows from the subsequent convergence argument.
- Uniqueness of the population maximizer is established through diagonal or permuted-diagonal structure under matrix assumptions.The supporting lemma requires symmetry, nonidentical columns, nonzero entries in each column of S, and matching entries where products are positive.
- The proof strategy for Erdos–Renyi modularity cannot be transferred directly to degree-corrected block models.
CORRECTION TO THE PROOF OF CONSISTENCY OF COMMUNITY DETECTION
This correction addresses an error in earlier consistency proofs for both stochastic block models and degree-corrected stochastic block models. It supplies a corrected argument while retaining the broader degree-corrected case as the main formulation.
- The correction addresses errors in consistency proofs for both stochastic block models and degree-corrected stochastic block models.
- The degree-corrected case is used for the correction because it is more general and includes regular stochastic block models as a special case.
- The notation uses arbitrary label assignments e, true labels c, and the criterion maximizer ˆc.
- The criteria are written in a form involving µn = n^2ρn, where ρn tends to zero as the average edge probability.
- The corrected proof adds the constraint |e − c| ≤ δn n to an existing approximation argument.
- The corrected bound completes the proof and preserves the conclusion of the earlier consistency theorem.