Stochastic blockmodels with growing number of classes

We present asymptotic and finite-sample results on the use of stochastic blockmodels for the analysis of network data. We show that the fraction of misclassified network nodes converges in probability to zero under maximum likelihood fitting when the number of classes is allowed to grow as the root of the network size and the average network degree grows at least poly-logarithmically in this size. We also establish finite-sample confidence bounds on maximum-likelihood blockmodel parameter estimates from data comprising independent Bernoulli random variates; these results hold uniformly over class assignment. We provide simulations verifying the conditions sufficient for our results, and conclude by fitting a logit parameterization of a stochastic blockmodel with covariates to a network data example comprising self-reported school friendships, resulting in block estimates that reveal residual structure.

• Publication year

  2010

• Venue

  Biometrika

• Publication date

  2010-11-20

• Fields of study

  Mathematics, Computer Science, Medicine

• Identifiers
  DOI 10.1093/biomet/asr053arXiv 1011.4644PMID 23843660PMCID PMC3635708
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Spectral clustering and the high-dimensional stochastic blockmodel

  2010cited by this paper
• Stochastic blockmodels and community structure in networks

  2010cited by this paper
• Uncovering latent structure in valued graphs: A variational approach

  2010cited by this paper
• A nonparametric view of network models and Newman–Girvan and other modularities

  2009influential reference
• A Survey of Statistical Network Models

  2009cited by this paper
• Concentration of Measure for the Analysis of Randomized Algorithms

  2009cited by this paper
• Identifying Community Structures from Network Data via Maximum Likelihood Methods

  2009cited by this paper
• Birds of a feather, or friend of a friend? using exponential random graph models to investigate adolescent social networks*

  2009cited by this paper
• Comparing Community Structure to Characteristics in Online Collegiate Social Networks

  2008cited by this paper
• Modeling homophily and stochastic equivalence in symmetric relational data

  2007cited by this paper
• Model‐based clustering for social networks

  2007cited by this paper
• Mixed Membership Stochastic Blockmodels

  2007cited by this paper
• Modularity and community structure in networks.

  2006cited by this paper
• Complex Graphs and Networks

  2006cited by this paper
• Generalized blockmodeling

  2005cited by this paper
• A latent mixed membership model for relational data

  2005cited by this paper
• Probabilistic Symmetries and Invariance Principles

  2005cited by this paper
• Community structure in social and biological networks

  2001cited by this paper
• Estimation and Prediction for Stochastic Blockstructures

  2001cited by this paper
• Estimation and Prediction for Stochastic Blockmodels for Graphs with Latent Block Structure

  1997cited by this paper
• Stochastic Blockmodels for Directed Graphs

  1987cited by this paper
• Statistical Analysis of Multiple Sociometric Relations.

  1985cited by this paper
• Stochastic blockmodels: First steps

  1983cited by this paper

• Identification and Estimation of Network Models with Nonparametric Unobserved Heterogeneity

  2026cites this paper
• Information Limits of Joint Community Detection and Finite Group Synchronization

  2026cites this paper
• A Goodness-of-Fit Test for Sparse Networks

  2025cites this paper
• Non-asymptotic goodness-of-fit tests and model selection in valued stochastic blockmodels

  2025cites this paper
• Simultaneous estimation of connectivity and dimensionality in samples of networks

  2025cites this paper
• Stochastic Block Models for Complex Network Analysis: A Survey

  2025cites this paper
• Detecting small clusters in the stochastic block model

  2025cites this paper
• Model-free algorithms for fast node clustering in SBM type graphs and application to social role inference in animals

  2025cites this paper
• Multiple Hypothesis Testing To Estimate The Number Of Communities in Stochastic Block Models

  2025cites this paper
• Variational Estimators for Node Popularity Models

  2025cites this paper
• Comparative Evaluation of Assumption Lean Community Detection Methods for Human Connectome Networks

  2025cites this paper
• High-dimensional Factor Analysis for Network-linked data

  2024cites this paper
• Quantifying Multivariate Graph Dependencies: Theory and Estimation for Multiplex Graphs

  2024cites this paper
• A Note on the Identifiability of the Degree‐Corrected Stochastic Block Model

  2024cites this paper
• Profile Least Squares Estimation in Networks With Covariates

  2024influential citation
• An Eigengap Ratio Test for Determining the Number of Communities in Network Data

  2024cites this paper
• Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models

  2023cites this paper
• Optimal distribution-free concentration for the log-likelihood function of Bernoulli variables

  2023cites this paper
• Community detection and clustering characteristics analysis of the stock market

  2023cites this paper
• Spectral clustering in the Gaussian mixture block model

  2023cites this paper
• Restricted Tweedie Stochastic Block Models

  2023cites this paper
• Combinatorial-Probabilistic Trade-Off: P-Values of Community Property Test in the Stochastic Block Models

  2023cites this paper
• Entropy of Exchangeable Random Graphs

  2023cites this paper
• Network Inference Using the Hub Model and Variants

  2023cites this paper
• Measuring the Complexity of an Exchangeable Graph

  2023cites this paper
• Semiparametric Modeling and Analysis for Longitudinal Network Data

  2023cites this paper
• Graph Neural Networks for Community Detection on Sparse Graphs

  2022cites this paper
• Modeling and Estimating Mixed Memberships in Weightednetworks

  2022cites this paper
• Spectral Estimation of Large Stochastic Blockmodels with Discrete Nodal Covariates

  2022cites this paper
• Joint Network Topology Inference Via a Shared Graphon Model

  2022cites this paper
• Dynamic network sampling for community detection

  2022cites this paper
• Distributed Community Detection in Large Networks

  2022cites this paper
• Stochastic Block Smooth Graphon Model

  2022cites this paper
• Community detection in overlapping weighted networks

  2022cites this paper
• A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphs

  2022cites this paper
• Two-sample test for stochastic block models via the largest singular value

  2022cites this paper
• Limit theorems for distributions invariant under groups of transformations

  2022cites this paper
• Perfect Spectral Clustering with Discrete Covariates

  2022cites this paper
• of the Bernoulli Society for Mathematical Statistics and Probability Volume Twenty Eight Number Two May 2022

  2022cites this paper
• Differentially Private Community Detection for Stochastic Block Models

  2022influential citation
• Multiple Hypothesis Testing To Estimate The Number of Communities in Sparse Stochastic Block Models

  2022cites this paper
• An alternative class of models to position social network groups in latent spaces

  2022cites this paper
• Two-sample test for stochastic block models via maximum entry-wise deviation

  2022cites this paper
• Confidence sets in a sparse stochastic block model with two communities of unknown sizes

  2021cites this paper
• A Useful Criterion on Studying Consistent Estimation in Community Detection

  2021cites this paper
• Mixture models and networks: The stochastic blockmodel

  2021cites this paper
• Weighted stochastic block model

  2021cites this paper
• Penalized homophily latent space models for directed scale-free networks

  2021cites this paper
• Mixed membership distribution-free model

  2021cites this paper
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons

  2021cites this paper
• A sparse stochastic block model with two unequal communities

  2021cites this paper
• Bayesian Inference of Random Dot Product Graphs via Conic Programming

  2021cites this paper
• Degree-corrected distribution-free model for community detection in weighted networks

  2021cites this paper
• On role extraction for digraphs via neighbourhood pattern similarity

  2021cites this paper
• Distribution-Free Models for Community Detection

  2021cites this paper
• Maximum A Posteriori Inference of Random Dot Product Graphs via Conic Programming

  2021cites this paper
• A fast algorithm for integrative community detection of multi‐layer networks

  2021cites this paper
• Uncertainty quantification and testing in a stochastic block model with two unequal communities

  2021cites this paper
• On identifying unobserved heterogeneity in stochastic blockmodel graphs with vertex covariates

  2020cites this paper
• Profile likelihood biclustering

  2020cites this paper
• On Optimal Uniform Concentration Inequalities for Discrete Entropies in the High-dimensional Setting

  2020cites this paper
• Econometric analysis of bipartite networks

  2020cites this paper
• Multi‐subject stochastic blockmodels with mixed effects for adaptive analysis of individual differences in human brain network cluster structure

  2020cites this paper
• Large-scale estimation of random graph models with local dependence

  2020cites this paper
• Detecting Latent Communities in Network Formation Models

  2020cites this paper
• Tractably modelling dependence in networks beyond exchangeability

  2020cites this paper
• Identifiability and consistency of network inference using the hub model and variants: a restricted class of Bernoulli mixture models

  2020influential citation
• Smoothing graphons for modelling exchangeable relational data

  2020cites this paper
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models

  2020cites this paper
• Nonreconstruction of high-dimensional stochastic block model with bounded degree

  2020cites this paper
• Learning Sparse Graphons and the Generalized Kesten-Stigum Threshold

  2020cites this paper
• Exact Recovery and Sharp Thresholds of Stochastic Ising Block Model

  2020cites this paper
• An optimal uniform concentration inequality for discrete entropies on finite alphabets in the high-dimensional setting

  2020cites this paper
• On Spectral Algorithms for Community Detection in Stochastic Blockmodel Graphs With Vertex Covariates

  2020cites this paper
• Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks

  2020cites this paper
• Best Subset, Forward Stepwise or Lasso? Analysis and Recommendations Based on Extensive Comparisons

  2020cites this paper
• Combinatorial-Probabilistic Trade-Off: Community Properties Test in the Stochastic Block Models

  2020cites this paper
• Extracting Brain Disease-Related Connectome Subgraphs by Adaptive Dense Subgraph Discovery

  2020cites this paper
• A network model that combines latent factors and sparse graphs

  2020cites this paper
• Bayesian Testing for Exogenous Partition Structures in Stochastic Block Models

  2020cites this paper
• Community Detection in Social Networks: Multilayer Networks and Pairwise Covariates

  2020cites this paper
• Edgeworth expansions for network moments

  2020cites this paper
• A Joint MLE Approach to Large-Scale Structured Latent Attribute Analysis

  2020cites this paper
• Consistency and asymptotic normality of stochastic block models estimators from sampled data

  2019cites this paper
• Limit theorems beyond sums of I.I.D observations

  2019cites this paper
• Multi-Subject Stochastic Blockmodels for Adaptive Analysis of Individual Differences in Human Brain Network Cluster Structure

  2019cites this paper
• The Evolution of the Spatial Association Effect of Carbon Emissions in Transportation: A Social Network Perspective

  2019cites this paper
• Multi‐scale network regression for brain‐phenotype associations

  2019cites this paper
• Fusing data depth with complex networks: Community detection with prior information

  2019cites this paper
• Optimal Bayesian estimation for random dot product graphs

  2019cites this paper
• Limits of Model Selection, Link Prediction, and Community Detection

  2019cites this paper
• Learning with Clusters

  2019cites this paper
• Consistent community detection in multi-layer network data

  2019cites this paper
• A Popularity Scaled Latent Space Model for Large-Scale Directed Social Network

  2019cites this paper
• Linking Functional Brain Networks to Psychopathology and Beyond

  2019cites this paper
• Node Features Adjusted Stochastic Block Model

  2019cites this paper
• A Stochastic Block Model for Multilevel Networks: Application to the Sociology of Organisations

  2019cites this paper
• A Note on New Bernstein-type Inequalities for the Log-likelihood Function of Bernoulli Variables

  2019cites this paper
• Spectral Inference for Large Stochastic Blockmodels With Nodal Covariates

  2019cites this paper
• Unified $\ell_{2\rightarrow\infty}$ Eigenspace Perturbation Theory for Symmetric Random Matrices

  2019cites this paper