Network models and sparse graphon estimation

Speaker(s): 
Olga Klopp (Université Paris-Quest Nanterre)
Date: 
Wednesday, November 2, 2016 - 10:00am
Location: 
WIAS, Erhard-Schmidt-Saal, Mohrenstraße 39, 10117 Berlin

Inhomogeneous random graph models encompass many network models such as stochastic block models and latent position models. We consider the problem of statistical estimation of the matrix of connection probabilities based on the observations of the adjacency matrix of the network and derive optimal rates of convergence for this problem. Our results cover the important setting of sparse networks. We also establish upper bounds on the mini-max risk for graphon estimation when the probability matrix is sampled according to a graphon model.
The problem of estimation of the matrix of connection probabilities of a network can be viewed as a particular case of a general matrix sequence model. In this model, we observe the noisy entries of a matrix and assume that the signal matrix is ''structured'', that is, it can be factorized using sparse factors. This model includes a number of interesting problems such as the mixture of Gaussian, sparse dictionary learning, stochastic block models and mixture membership models. In the second part of the talk, I will consider the problem of statistical estimation of the signal matrix for this model and derive optimal rates of estimation.