Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
Published in
Neural Information Processing Systems(2013)External Links:
TL
TL;DR
This paper proposes a computationally efficient procedure to estimate a graphon from a set of observed networks generated from it based on a stochastic blockmodel approximation (SBA) of the graphon, and shows that the estimation error vanishes as the size of thegraph approaches infinity.
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.
References36 items
1
Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures
2
Variational Bayes model averaging for graphon functions and motif frequencies inference in W-graph models
3
Nonparametric graphon estimation
4
Co-clustering separately exchangeable network data
5