Consistent estimation of dynamic and multi-layer block models
arXiv:1410.8597
Abstract
Significant progress has been made recently on theoretical analysis of estimators for the stochastic block model (SBM). In this paper, we consider the multi-graph SBM, which serves as a foundation for many application settings including dynamic and multi-layer networks. We explore the asymptotic properties of two estimators for the multi-graph SBM, namely spectral clustering and the maximum-likelihood estimate (MLE), as the number of layers of the multi-graph increases. We derive sufficient conditions for consistency of both estimators and propose a variational approximation to the MLE that is computationally feasible for large networks. We verify the sufficient conditions via simulation and demonstrate that they are practical. In addition, we apply the model to two real data sets: a dynamic social network and a multi-layer social network with several types of relations.
arXiv commentTo appear at ICML 2015
References in corpus (13)
- Finding and evaluating community structure in networks
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Stochastic blockmodels and community structure in networks
- Multirelational Organization of Large-scale Social Networks in an Online World
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Dynamic stochastic blockmodels for time-evolving social networks
- Stochastic blockmodels with growing number of classes
- Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
- Rate-optimal graphon estimation
- Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
- Adaptive Evolutionary Clustering
- Nonparametric graphon estimation
- Multi-layer graph analysis for dynamic social networks
Cited by in corpus (24)
- Random graph models for dynamic networks
- Community detection in multi-relational data with restricted multi-layer stochastic blockmodel
- Joint Embedding of Graphs
- Inference for multiple heterogeneous networks with a common invariant subspace
- Spectral Clustering for Multiple Sparse Networks: I
- A random effects stochastic block model for joint community detection in multiple networks with applications to neuroimaging
- Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
- General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers
- Null Models and Community Detection in Multi-Layer Networks
- Multilayer Spectral Graph Clustering via Convex Layer Aggregation: Theory and Algorithms
- Bayesian Learning of Dynamic Multilayer Networks
- Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model
- Spectral clustering via adaptive layer aggregation for multi-layer networks
- Spectral clustering in the dynamic stochastic block model
- Multiple Network Embedding for Anomaly Detection in Time Series of Graphs
- A Review of Latent Space Models for Social Networks
- Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
- Simultaneous prediction and community detection for networks with application to neuroimaging
- A Systematic Survey on Multi-relational Community Detection
- Nonparametric regression for multiple heterogeneous networks
- Multi-view Banded Spectral Clustering with Application to ICD9 Clustering
- Hyperbolic Multiplex Network Embedding with Maps of Random Walk
- Clustering multilayer graphs with missing nodes
- A Class of Temporal Hierarchical Exponential Random Graph Models for Longitudinal Network Data