Spectral Inference for Large Stochastic Blockmodels With Nodal Covariates

In many applications of network analysis, it is important to distinguish between observed and unobserved factors affecting network structure. To this end, we develop spectral estimators for both unobserved blocks and the effect of covariates in stochastic blockmodels. Our main strategy is to reformulate the stochastic blockmodel estimation problem as recovery of latent positions in a generalized random dot product graph. On the theoretical side, we establish asymptotic normality of our estimators for the subsequent purpose of performing inference. On the applied side, we show that computing our estimator is much faster than standard variational expectation--maximization algorithms and scales well for large networks. The results in this paper provide a foundation to estimate the effect of observed covariates as well as unobserved latent community structure on the probability of link formation in networks.

• Publication year

  2019

• Venue

  Social Science Research Network

• Publication date

  2019-08-18

• Fields of study

  Mathematics, Computer Science, Economics

• Identifiers
  DOI 10.2139/ssrn.3438987arXiv 1908.06438
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On Estimation and Inference in Latent Structure Random Graphs

  2018cited by this paper
• Community detection and stochastic block models: recent developments

  2017cited by this paper
• Statistical Inference on Random Dot Product Graphs: a Survey

  2017influential reference
• Job Mobility Networks and Endogenous Labor Markets

  2017cited by this paper
• Estimation of Peer Effects in Endogenous Social Networks: Control Function Approach

  2017cited by this paper
• Semi-External Memory Sparse Matrix Multiplication for Billion-Node Graphs

  2016cited by this paper
• The Oxford handbook of the economics of networks

  2016cited by this paper
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs

  2016influential reference
• An SSD-based eigensolver for spectral analysis on billion-node graphs

  2016cited by this paper
• Model-Based Clustering

  2016cited by this paper
• Likelihood Inference for Large Scale Stochastic Blockmodels With Covariates Based on a Divide-and-Conquer Parallelizable Algorithm With Communication

  2016influential reference
• Estimating Causal Peer Influence in Homophilous Social Networks by Inferring Latent Locations

  2016cited by this paper
• Incorporating Covariates Into Stochastic Blockmodels

  2015cited by this paper
• Some Challenges in the Empirics of the Effects of Networks

  2015cited by this paper
• FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs

  2014cited by this paper
• Social Networks and the Identification of Peer Effects

  2013cited by this paper
• Model-Based Clustering of Large Networks

  2012cited by this paper
• Asymptotic Normality of Maximum Likelihood and its Variational Approximation for Stochastic Blockmodels

  2012influential reference
• Universally consistent vertex classification for latent positions graphs

  2012cited by this paper
• Social Structure of Facebook Networks

  2011cited by this paper
• Stochastic blockmodels with growing number of classes

  2010cited by this paper
• Variational Bayesian inference and complexity control for stochastic block models

  2009cited by this paper
• Graphical Models, Exponential Families, and Variational Inference

  2008cited by this paper
• A mixture model for random graphs

  2008cited by this paper
• Automatic dimensionality selection from the scree plot via the use of profile likelihood

  2006influential reference
• Estimation and Prediction for Stochastic Blockstructures

  2001cited by this paper
• MCLUST: Software for Model-Based Cluster Analysis

  1999cited by this paper

• Identification and Estimation of Network Models with Nonparametric Unobserved Heterogeneity

  2026cites this paper
• The co-varying ties between networks and item responses via latent variables.

  2024cites this paper
• Using network analysis to study and manage human-mediated dispersal of exotic species

  2023cites this paper
• Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Model

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

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

  2022cites this paper
• Perfect Spectral Clustering with Discrete Covariates

  2022influential citation
• AN (cid:96) p THEORY OF PCA AND SPECTRAL CLUSTERING

  2022cites this paper
• Dynamic network sampling for community detection

  2022cites this paper
• An 𝓁p theory of PCA and spectral clustering

  2022cites this paper
• Exploiting node metadata to predict interactions in bipartite networks using graph embedding and neural networks

  2022influential citation
• An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees

  2021cites this paper
• Recent Integrations of Latent Variable Network Modeling With Psychometric Models

  2021cites this paper
• Exploiting node metadata to predict interactions in large networks using graph embedding and neural networks

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

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

  2020cites this paper
• An $\ell_p$ theory of PCA and spectral clustering.

  2020cites this paper
• Joint Latent Space Model for Social Networks with Multivariate Attributes

  2019cites this paper
• Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure

  2019cites this paper