Exponential random network models

June 17 to June 21, 2013

at the

American Institute of Mathematics, San Jose, California

organized by

Sourav Chatterjee, Persi Diaconis, Susan Holmes, and Martina Morris

Original Announcement

This workshop will bring practicing social scientists and statisticians who study exponential random graph models and use these models into contact with an emerging group of mathematicians who use a variety of new tools, including graph limit theory and tools from statistical mechanics such as spin glasses. The hope is to get mathematicians to work on problems of immediate interest, tell practitioners what tools are available, and tell each group the 'standard lore' of the other. To facilitate this, we focus on particular examples such as the alternating star model. This is an interesting case of an exponential random graph model.

The standard exponential random graph model gives a distribution on graphs of the form $$ P(G) = Z(b) exp{ b(1)t(1,G) + ... + b(k)t(k,G) }. $$ This is a probability measure over the set of simple,labeled,undirected graphs on n vertices. The $t(i,G)$ are features, e.g. $t(1,G)=\#edges$, $t(2,G)=\#$ triangles, etc. the $b(i)$ are parameters in the model and Z(b) is a (usually unknowable) normalizing constant. There are similar models for directed graphs and models that incorporate features on the vertices and edges. It is well known that estimating the parameters in the exponential model based on a single observed graph, is very difficult if $n$ is at all large. Applied workers have been able to introduce a class of models with $t(i,G)$ the number of $i$-stars in G and $b(i) = (-1/A)^(i-1)$ with $A$ a positive constant. They have observed that they behave stably and allow estimation of additional parameters if used as a base. Because of the alternating signs, these models are similar to spin-glass models. We would like to address the evidence that the alternating stars model behaves well. What are the strengths and weaknesses of this model. Can any of this be proved or understood?

Material from the workshop

A list of participants.

The workshop schedule.

A report on the workshop activities.

Papers arising from the workshop:

Asymptotic quantization of exponential random graphs
by  Mei Yin, Alessandro Rinaldo and Sukhada Fadnavis,  Ann. Appl. Probab. 26 (2016), no. 6, 3251-3285  MR3582803
Bayesian Model Averaging of Stochastic Block Models to Estimate the Graphon Function and Motif Frequencies in a W-graph Model
by  P. Latouche and S. Robin
On the asymptotics of constrained exponential random graphs
by  Richard Kenyon and Mei Yin,  J. Appl. Probab. 54 (2017), no. 1, 165–180  MR3632612
Asymptotic quantization of exponential random graphs
by  Mei Yin, Alessandro Rinaldo and Sukhada Fadnavis