Skip to yearly menu bar Skip to main content


Poster

Stochastic blockmodel approximation of a graphon: Theory and consistent estimation

Edo M Airoldi · Thiago B Costa · Stanley H Chan

Harrah's Special Events Center, 2nd Floor

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.

Live content is unavailable. Log in and register to view live content