Applications of L^p Theory of Sparse Graph Limits

May 19, 2015
  • Sparse matrices
  • 65F51
When analyzing large networks, statisticians often assume a generative model in which the observed graph is assumed to come from a stochastic block model, i.e., a random graph with inhomogeneous edge probabilities given in terms of a small block matrix. A non-parametric version of these stochastic block models are so-called W-random graphs, given in terms of an integrable, symmetric function W on the unit square. In this talk we discuss the question of how to recover a good approximation to W from just a single sample of a W-random graph, and relate it to the theory of convergence of sparse graphs. We also show how to use this theory to obtain node differentially private versions of the non-parametric stochastic block model, enabling one of the strongest results on node differential privacy. Joint work with Jennifer Chayes, Henry Cohn, Shirshendu Ganguly and Adam Smith.