Stochastic blockmodels with growing number of classes

Abstract

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 a collection of Facebook profiles, resulting in block estimates that reveal residual structure.

12 pages, 3 figures; revised version

References in corpus (5)

• Modularity and community structure in networks
• Stochastic blockmodels and community structure in networks
• Spectral clustering and the high-dimensional stochastic blockmodel
• Uncovering latent structure in valued graphs: A variational approach
• Modeling homophily and stochastic equivalence in symmetric relational data

Cited by in corpus (72)

• Spectral clustering and the high-dimensional stochastic blockmodel
• Matrix estimation by Universal Singular Value Thresholding
• Consistency of spectral clustering in stochastic block models
• Fast community detection by SCORE
• Consistency of community detection in networks under degree-corrected stochastic block models
• Parsimonious module inference in large networks
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Network histograms and universality of blockmodel approximation
• Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
• Sparse exchangeable graphs and their limits via graphon processes
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• Consistent estimation of dynamic and multi-layer block models
• Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
• Community detection in multi-relational data with restricted multi-layer stochastic blockmodel
• On the Question of Effective Sample Size in Network Modeling: An Asymptotic Inquiry
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• A Spectral Framework for Anomalous Subgraph Detection
• A Survey on Theoretical Advances of Community Detection in Networks
• Co-clustering separately exchangeable network data
• A Consistent Histogram Estimator for Exchangeable Graph Models
• Private Graphon Estimation for Sparse Graphs
• Detecting Overlapping Communities in Networks Using Spectral Methods
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• Convergence of the groups posterior distribution in latent or stochastic block models
• A nonparametric two-sample hypothesis testing problem for random dot product graphs
• Co-clustering for directed graphs: the Stochastic co-Blockmodel and spectral algorithm Di-Sim
• Social Network Mediation Analysis: a Latent Space Approach
• Determining the Number of Communities in Degree-corrected Stochastic Block Models
• A Graphon Approach to Limiting Spectral Distributions of Wigner-type Matrices
• Recovering communities in the general stochastic block model without knowing the parameters
• Large-scale estimation of random graph models with local dependence
• Consistent structure estimation of exponential-family random graph models with block structure
• Unified ${\ell }_{2\to \infty }$ Eigenspace Perturbation Theory for Symmetric Random Matrices
• A Continuous-time Stochastic Block Model for Basketball Networks
• Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral
• Graphons: A Nonparametric Method to Model, Estimate, and Design Algorithms for Massive Networks
• The blessing of transitivity in sparse and stochastic networks
• A central limit theorem for scaled eigenvectors of random dot product graphs
• Joint Network Topology Inference via a Shared Graphon Model
• Pairwise Covariates-adjusted Block Model for Community Detection
• Consistency and Asymptotic Normality of Stochastic Block Models Estimators from Sampled Data
• Why are Big Data Matrices Approximately Low Rank?
• Universally Consistent Latent Position Estimation and Vertex Classification for Random Dot Product Graphs
• A useful criterion on studying consistent estimation in community detection
• Profile Likelihood Biclustering
• Higher-Order Spectral Clustering under Superimposed Stochastic Block Model
• How Many Communities Are There?
• Spectral clustering via adaptive layer aggregation for multi-layer networks
• Topics in social network analysis and network science
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
• Using Maximum Entry-Wise Deviation to Test the Goodness-of-Fit for Stochastic Block Models
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• Limit theorems for invariant distributions
• A Joint MLE Approach to Large-Scale Structured Latent Attribute Analysis
• Optimal Bayesian Estimation for Random Dot Product Graphs
• Exact recovery and sharp thresholds of Stochastic Ising Block Model
• Identifiability and consistency of network inference using the hub model and variants
• Confidence sets in a sparse stochastic block model with two communities of unknown sizes
• On role extraction for digraphs via neighbourhood pattern similarity
• Combinatorial-Probabilistic Trade-Off: Community Properties Test in the Stochastic Block Models
• Network induced large correlation matrix estimation
• Fast and reliable inference algorithm for hierarchical stochastic block models
• Corrected Bayesian information criterion for stochastic block models
• A Note on New Bernstein-type Inequalities for the Log-likelihood Function of Bernoulli Variables
• Uncertainty quantification and testing in a stochastic block model with two unequal communities
• Clustering on the Edge: Learning Structure in Graphs
• Maximum a Posteriori Inference of Random Dot Product Graphs via Conic Programming
• Logistic Regression Augmented Community Detection for Network Data with Application in Identifying Autism-Related Gene Pathways
• Tractably Modelling Dependence in Networks Beyond Exchangeability
• Community Detection by $L_0$-penalized Graph Laplacian