Stochastic Blockmodel Approximation of a Graphon: Theory and Consistent Estimation
Abstract
Given a convergent sequence of graphs, there exists a limit object called the graphon from which random graphs are generated. This nonparametric perspective of random graphs opens the door to study graphs beyond the traditional parametric models, but at the same time also poses the challenging question of how to estimate the graphon underlying observed graphs. In this paper, we propose a computationally efficient algorithm to estimate a graphon from a set of observed graphs generated from it. We show that, by approximating the graphon with stochastic block models, the graphon can be consistently estimated, that is, the estimation error vanishes as the size of the graph approaches infinity.
Cite
Text
Airoldi et al. "Stochastic Blockmodel Approximation of a Graphon: Theory and Consistent Estimation." Neural Information Processing Systems, 2013.Markdown
[Airoldi et al. "Stochastic Blockmodel Approximation of a Graphon: Theory and Consistent Estimation." Neural Information Processing Systems, 2013.](https://mlanthology.org/neurips/2013/airoldi2013neurips-stochastic/)BibTeX
@inproceedings{airoldi2013neurips-stochastic,
title = {{Stochastic Blockmodel Approximation of a Graphon: Theory and Consistent Estimation}},
author = {Airoldi, Edoardo M. and Costa, Thiago B and Chan, Stanley H},
booktitle = {Neural Information Processing Systems},
year = {2013},
pages = {692-700},
url = {https://mlanthology.org/neurips/2013/airoldi2013neurips-stochastic/}
}