Peter Bickel
UC Berkeley

Inference for unlabelled graphs

In view of the emergence of dense networks such as the Internet, and manifestations such as Facebook, a great deal of attention has recently been given to unlabelled graphs possibly with covariates. A heavily studied problem has been the identification of communities of individuals, corresponding to vertices of an unlabelled graph. A description of these and other problems may be found in the recent monographs of Newman (2010), Kleinberg et al. (2010) and Kolaczyc (2010). There is a well developed inference literature in the social sciences, see Wasserman and Faust (1994) but the network sizes addressed tend to be small. Chen and I recently introduced a nonparametric framework for probabilistic ergodic models of infinite unlabelled graphs (PNAS2009) and made some connections with modularities arising in the physics literature and community models in the social sciences. Our hope is to develop exploratory and confirmatory methods in this framework which have the power of clarifying and testing parametric assumptions in this complex setting that their analogues have in the study of models for samples of independent observations. We will advance and give some results on methods we have developed for both dense and sparse graphs.

(This is joint work with Aiyou Chen, Liza Levina,and Sharmodeep Bhattacharyya)