Stochastic blockmodels, graphons and K-means clustering

22 Jan 2015

Speaker: Prof. David Choi

Abstract: Stochastic blockmodels and graphons are models for network data that are studied in both statistics and mathematics. A stochastic blockmodel is like a mixture model for networks, while a graphon is a fully nonparametric model. In this talk, I'll show a connection between stochastic blockmodels and K-means clustering. Using this connection, I'll apply existing bounds for K-means clustering to show an oracle inequality, stating that the excess clustering risk for stochastic blockmodeling decays as O(1/sqrt(n)) if the data is generated from a graphon.

We thank Microsoft Research for their gracious support