Source-linked AI summary
Stochastic blockmodels and community structure in networks
Brian Karrer, M. E. J. Newman
TL;DR
Stochastic blockmodels often ignore heterogeneous vertex degrees, limiting their fit to real-world networks and potentially distorting community detection. The paper develops a degree-corrected blockmodel with closed-form solutions and compares it with the uncorrected model on real and synthetic networks. The corrected model performs quantitatively better, while retaining tractability and supporting benchmark generation, though it has important modeling limitations.
Problem
Standard blockmodels ignore heterogeneous vertex degrees, which can make them unsuitable for real-world networks and cause degree-driven structure to be mistaken for group membership.
Method
The paper develops a degree-corrected stochastic blockmodel with closed-form parameter solutions and uses it for inference and synthetic benchmark generation.
Results
The degree-corrected model performs quantitatively better than the uncorrected model on synthetic and real-world networks.
Takeaways & Limitations
Degree correction can prevent splits based solely on degree and increase sensitivity to underlying network structure while retaining blockmodel generality and tractability.
Takeaways & Limitations
The model can produce unrealistic zero-degree vertices, cannot represent some forbidden degree sequences, and may miss higher-order structure such as motifs or degree correlations.
Abstract
from arXiv · showhide
Stochastic blockmodels have been proposed as a tool for detecting community structure in networks as well as for generating synthetic networks for use as benchmarks. Most blockmodels, however, ignore variation in vertex degree, making them unsuitable for applications to real-world networks, which typically display broad degree distributions that can significantly distort the results. Here we demonstrate how the generalization of blockmodels to incorporate this missing element leads to an improved objective function for community detection in complex networks. We also propose a heuristic algorithm for community detection using this objective function or its non-degree-corrected counterpart and show that the degree-corrected version dramatically outperforms the uncorrected one in both real-world and synthetic networks.
I. INTRODUCTION
The paper extends stochastic blockmodels to account for heterogeneous vertex degrees, addressing poor fits and misleading structure detection in real-world networks. It develops a degree-corrected model with closed-form parameter solutions and evaluates it against the original model on empirical and synthetic networks.
- Model background: Stochastic blockmodels generate network edges from probabilities determined by vertices’ group memberships.They can represent community, core-periphery, hierarchical, and multipartite structures.
- Empirical inference: A posteriori blockmodeling fits these models to empirical networks to infer group structure and can recover planted blocks under certain conditions.The approach is broader than traditional community detection because it can detect structures beyond dense communities.
- Problem: The ordinary blockmodel often fits real-world networks poorly because it cannot represent their degree heterogeneity.Its limited flexibility can cause important network features to be missed.
- Contribution: The paper introduces a degree-corrected blockmodel as a simple extension of the classic model and derives closed-form parameter solutions.This facilitates direct comparison between corrected and traditional models while preserving analytic tractability.
- Evaluation: The degree-corrected model is evaluated for community detection on actual networks and new synthetic benchmarks against the uncorrected model.The paper reports that it performs better in both settings while adding only slight complexity.
II. STANDARD STOCHASTIC BLOCKMODEL
The standard stochastic blockmodel derives a likelihood-based objective for assigning vertices to groups, but its uniform null model ignores heterogeneous degrees. This can mistake degree-driven divisions for community structure, motivating a degree-aware alternative.
- Likelihood objective: The ordinary blockmodel maximizes the graph likelihood over block parameters and vertex group assignments.After optimizing parameters, the resulting objective function ranks group assignments by their likelihood.
- Information-theoretic interpretation: Its objective has an information-theoretic interpretation as the divergence between the group-end distribution and a distribution without group structure.The most likely assignments require the most information to describe relative to the group-free model.
- Null model: The blockmodel’s null model assumes constant expected edge probability, whereas degree-preserving alternatives use Pij = kikj/2m.The uniform null model produces Poisson degree distributions, unlike the broad degree distributions common in real networks.
- Degree correction: Accounting for degree makes high-degree connections less surprising and yields better results than the uniform model.This reflects that high-degree vertices are more likely to connect simply because they have more edges.
- Failure mode: Using the uniform degree-independent distribution can cause the model to interpret structure generated by the degree sequence as group membership.The proposed remedy is a stochastic blockmodel that directly incorporates heterogeneous degree distributions.
III. DEGREE-CORRECTED STOCHASTIC BLOCKMODEL
The degree-corrected blockmodel extends the stochastic blockmodel with vertex-specific degree parameters, preserving both group-level edge counts and the network’s expected degree sequence. Its likelihood differs from the uncorrected objective mainly by replacing group vertex counts with group stub counts, while supporting efficient local optimization and information-theoretic interpretation.
- Model definition: The degree-corrected model introduces vertex parameters θ_i that control the expected degrees of individual vertices.Expected adjacency entries are modeled as θ_iθ_jω_gi gj.
- Parameter estimation: Maximum-likelihood estimates preserve the expected number of edges between groups and the expected degree sequence.The parameters are normalized so the fitted ensemble matches these observed network summaries.
- Objective function: The corrected log-likelihood replaces each group’s vertex count n_r with its stub count κ_r, producing a substantial change despite the minor algebraic modification.The corrected and uncorrected objectives otherwise have the same basic form.
- Information-theoretic interpretation: The corrected objective can be interpreted as mutual information between the group labels at the ends of a randomly selected edge.It measures group assignments relative to a null model with the given expected degree sequence, unlike the ordinary model’s Erdős–Rényi reference.
- Applications: The objective can also quantify assortative mixing by testing which discrete vertex characteristic is most predictive of network structure.The paper gives nationality, race, and gender in social networks as examples of such characteristics.
- Optimization: Single-vertex group switches can be evaluated efficiently, enabling local Monte Carlo and Kernighan–Lin-style heuristic community detection.The average cost of evaluating a move is O(K + ⟨k⟩), while selecting the best destination group costs O(K(K + ⟨k⟩)).
IV. RESULTS
The paper evaluates corrected and uncorrected blockmodels against known community assignments in real-world and synthetic networks using normalized mutual information. In the karate club example, the figure compares inferred memberships with the observed faction split while encoding vertex degree by size.
- Evaluation: Performance is evaluated on real-world and synthetic networks by comparing inferred communities with known assignments.The comparison metric is normalized mutual information.
- Evaluation: Normalized mutual information equals one for identical assignments and zero for uncorrelated assignments.It is computed from the mutual information and entropies of inferred and true community labels.
- Karate club network: Figure 1 compares uncorrected and corrected blockmodel divisions of the karate club network, with vertex size proportional to degree and color indicating inferred group membership.The dashed line marks the split observed in real life.
A. Empirical networks
Empirical tests show that degree heterogeneity can make the uncorrected blockmodel detect degree-based groups instead of meaningful communities. Degree correction recovers known or independently labeled structure more accurately, while offering little difference when degrees are homogeneous.
- In homogeneous-degree networks, corrected and uncorrected blockmodels perform similarly because their likelihoods differ only by an additive constant.
- The uncorrected model splits the karate-club network by degree rather than recovering its two known factions.
- Degree correction recovers the karate-club factions except for one boundary vertex, which other community-detection algorithms also misidentify.
- Accounting for degree variation prevents the uncorrected model from favoring high-, medium-, and low-degree groups as K increases.
- The corrected model achieves normalized mutual information 0.72 on the political-blog labels, compared with 0.0001 for the uncorrected model.
B. Generation of synthetic networks
The synthetic benchmark networks are generated from degree-corrected blockmodels with freely chosen group assignments and expected degrees. A mixing parameter λ interpolates between planted structure and a degree-conditioned random network, enabling controlled tests across multiple structural forms.
- Synthetic networks use degree-corrected blockmodels so group assignments and expected vertex degrees can be chosen independently.
- The benchmark varies ω_rs to control the level of community structure while preserving the selected expected degrees.
- The construction supports community, approximately bipartite or core-periphery, and hierarchical structures.
- At λ = 1, edges follow the planted communities, whereas at λ = 0 they are placed randomly conditional on the degree sequence.
- Intermediate λ values mix planted and null-model edges, with λ representing the expected fraction drawn from the planted structure.
C. Performance on synthetic networks
Synthetic evaluations compare model objectives and optimization behavior using planted and random initializations across several heterogeneous network structures. The degree-corrected model detects planted structure more effectively, including when initialized randomly and compared against a favorably initialized uncorrected model.
- The evaluation separates objective quality from heuristic performance by testing both random and planted initial conditions.
- Synthetic results average normalized mutual information over 30 networks of size n = 1000 for each data point.
- Two-group, two-degree networks: At λ = 1/2, the uncorrected model finds no planted structure under either initialization, including initialization with the known correct answer.
- Core-periphery and hierarchical networks: Across core-periphery and hierarchical networks, the corrected model performs significantly better than the uncorrected model, including under random initialization.
V. CONCLUSIONS
The paper incorporates heterogeneous vertex degrees into stochastic blockmodels, improving inference while preserving their usefulness as tractable benchmark generators. Degree correction outperforms the uncorrected model on synthetic and real-world networks, although important modeling limitations remain.
- Degree-corrected blockmodels incorporate heterogeneous vertex degrees while retaining the generality and tractability of standard blockmodels.They can also generate benchmark networks with degree sequences closer to those of real networks.
- The degree-corrected model performs quantitatively better than the uncorrected model for group-structure inference on both synthetic and real-world test networks.
- In networks with substantial degree heterogeneity, the uncorrected model may split vertices into high- and low-degree groups instead of recovering true memberships.Degree correction ignores divisions based solely on degree and is therefore more sensitive to underlying structure.
- More sophisticated overlapping and mixed-membership blockmodels may also benefit from incorporating degree sequences, especially in online social networks with heterogeneous degrees.The paper presents this as a likely benefit rather than an established result.
- The degree-corrected model can produce unrealistic zero-degree vertices, cannot represent some forbidden degree values, and may miss higher-order network structure or degree correlations.