Model Selection for Degree-corrected Block Models

Abstract

The proliferation of models for networks raises challenging problems of model selection: the data are sparse and globally dependent, and models are typically high-dimensional and have large numbers of latent variables. Together, these issues mean that the usual model-selection criteria do not work properly for networks. We illustrate these challenges, and show one way to resolve them, by considering the key network-analysis problem of dividing a graph into communities or blocks of nodes with homogeneous patterns of links to the rest of the network. The standard tool for doing this is the stochastic block model, under which the probability of a link between two nodes is a function solely of the blocks to which they belong. This imposes a homogeneous degree distribution within each block; this can be unrealistic, so degree-corrected block models add a parameter for each node, modulating its over-all degree. The choice between ordinary and degree-corrected block models matters because they make very different inferences about communities. We present the first principled and tractable approach to model selection between standard and degree-corrected block models, based on new large-graph asymptotics for the distribution of log-likelihood ratios under the stochastic block model, finding substantial departures from classical results for sparse graphs. We also develop linear-time approximations for log-likelihoods under both the stochastic block model and the degree-corrected model, using belief propagation. Applications to simulated and real networks show excellent agreement with our approximations. Our results thus both solve the practical problem of deciding on degree correction, and point to a general approach to model selection in network analysis.

References in corpus (7)

• Cooperative Game Theory Approaches for Network Partitioning
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• Missing and spurious interactions and the reconstruction of complex networks
• Phase transition in the detection of modules in sparse networks
• Marginal Likelihood Integrals for Mixtures of Independence Models
• Oriented and Degree-generated Block Models: Generating and Inferring Communities with Inhomogeneous Degree Distributions

Cited by in corpus (45)

• Statistical physics of inference: Thresholds and algorithms
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Fast community detection by SCORE
• A Review of Stochastic Block Models and Extensions for Graph Clustering
• Identification of core-periphery structure in networks
• A General Optimization Technique for High Quality Community Detection in Complex Networks
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Efficiently inferring community structure in bipartite networks
• Modeling sequences and temporal networks with dynamic community structures
• A goodness-of-fit test for stochastic block models
• Bayesian stochastic blockmodeling
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Multilayer stochastic block models reveal the multilayer structure of complex networks
• Reconstruction methods for networks: the case of economic and financial systems
• Consistencies and inconsistencies between model selection and link prediction in networks
• Structural inference for uncertain networks
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Phase transitions in semisupervised clustering of sparse networks
• Community detection in networks with unequal groups
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Cross-validation estimate of the number of clusters in a network
• Demarcating Geographic Regions using Community Detection in Commuting Networks with Significant Self-Loops
• Centrality metrics and localization in core-periphery networks
• Adapting Stochastic Block Models to Power-Law Degree Distributions
• The Infinite Degree Corrected Stochastic Block Model
• A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models
• Network cross-validation by edge sampling
• Model selection and clustering in stochastic block models with the exact integrated complete data likelihood
• Asymptotic resolution bounds of generalized modularity and multi-scale community detection
• Network Cross-Validation for Determining the Number of Communities in Network Data
• Null Models and Community Detection in Multi-Layer Networks
• Generative models for local network community detection
• Adjusted chi-square test for degree-corrected block models
• Hypothesis Testing for Equality of Latent Positions in Random Graphs
• Non-linear Attributed Graph Clustering by Symmetric NMF with PU Learning
• Community Detection Algorithm Combining Stochastic Block Model and Attribute Data Clustering
• Large Deviations of Semi-supervised Learning in the Stochastic Block Model
• Uniqueness of communities in regular stochastic block models
• Loan maturity aggregation in interbank lending networks obscures mesoscale structure and economic functions
• Community Detection in Weighted Multilayer Networks with Ambient Noise
• Spectral goodness-of-fit tests for complete and partial network data
• Quantifying metadata relevance to network block structure using description length
• A Unified Framework for Community Detection and Model Selection in Blockmodels
• Clustering on the Edge: Learning Structure in Graphs