Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
arXiv:1311.1731
Abstract
Non-parametric approaches for analyzing network data based on exchangeable graph models (ExGM) have recently gained interest. The key object that defines an ExGM is often referred to as a graphon. This non-parametric perspective on network modeling poses challenging questions on how to make inference on the graphon underlying observed network data. In this paper, we propose a computationally efficient procedure to estimate a graphon from a set of observed networks generated from it. This procedure is based on a stochastic blockmodel approximation (SBA) of the graphon. We show that, by approximating the graphon with a stochastic block model, the graphon can be consistently estimated, that is, the estimation error vanishes as the size of the graph approaches infinity.
20 pages, 4 figures, 2 algorithms. Neural Information Processing Systems (NIPS), 2013
References in corpus (2)
Cited by in corpus (31)
- Rate-optimal graphon estimation
- Sparse graphs using exchangeable random measures
- Network histograms and universality of blockmodel approximation
- Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spaces
- Graphon Signal Processing
- Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- On Robustness of Principal Component Regression
- Estimating network edge probabilities by neighborhood smoothing
- Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral
- Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
- Motif Estimation via Subgraph Sampling: The Fourth Moment Phenomenon
- Subspace Decomposition for Graphon LQR: Applications to VLSNs of Harmonic Oscillators
- Joint Network Topology Inference via a Shared Graphon Model
- Learning modular structures from network data and node variables
- Size-Invariant Graph Representations for Graph Classification Extrapolations
- EM-Based Smooth Graphon Estimation Using Bayesian and Spline-Based Approaches
- Goodness of fit of logistic models for random graphs
- Why are Big Data Matrices Approximately Low Rank?
- From which world is your graph?
- On the Consistency of the Likelihood Maximization Vertex Nomination Scheme: Bridging the Gap Between Maximum Likelihood Estimation and Graph Matching
- Consistent polynomial-time unseeded graph matching for Lipschitz graphons
- Classification on Large Networks: A Quantitative Bound via Motifs and Graphons
- Automatic Dimension Selection for a Non-negative Factorization Approach to Clustering Multiple Random Graphs
- Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels
- Strength of Connections in a Random Graph: Definition, Characterization, and Estimation
- Mixture Models and Networks -- Overview of Stochastic Blockmodelling
- Distributed Cartesian Power Graph Segmentation for Graphon Estimation
- Unified Statistical Theory of Spectral Graph Analysis
- Network estimation via graphon with node features
- Hawkes Processes on Graphons