at the
American Institute of Mathematics, San Jose, California
organized by
Sourav Chatterjee, Persi Diaconis, Susan Holmes, and Martina Morris
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 schedule.
A report on the workshop activities.
Papers arising from the workshop: