# Exponential random network models

June 17 to June 21, 2013

at the

American Institute of Mathematics, Palo Alto, California

organized by

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

This workshop, sponsored by AIM and the NSF, 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?

The workshop will differ from typical conferences in some regards. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.

The deadline to apply for support to participate in this workshop has passed.