Stochastic blockmodel approximation of a graphon: Theory and consistent estimation

Non-parametric approaches for analyzing network data base d on exchangeable graph models (ExGM) have recently gained interest. The key o bject 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 bl ockmodel approximation (SBA) of the graphon. W e show that, by approximating t he graphon with a stochastic block model, the graphon can be consistently es timated, that is, the estimation error vanishes as the size of the graph approache s infinity.