Timezone: »

 
Poster
Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
Edo M Airoldi · Thiago B Costa · Stanley H Chan

Fri Dec 06 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor
in Poster Session »

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.

[ PDF] 

Author Information

Edo M Airoldi (Harvard University)
Thiago B Costa (Harvard University)
Stanley H Chan (Harvard University)

More from the Same Authors