Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
This provides a computationally efficient solution for non-parametric network analysis, addressing a key inference challenge in exchangeable graph models.
The paper tackles the problem of estimating a graphon from observed network data by proposing a stochastic blockmodel approximation method, showing that the estimation error vanishes as graph size increases.
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.