  Exponential random graphs are used extensively in the sociology literature.
This model seeks to incorporate in random graphs the notion of reciprocity,
that is, the larger than expected number of triangles and other small
subgraphs. Sampling from these distributions is crucial for parameter
estimation hypothesis testing, and more generally for understanding basic
features of the network model itself. In practice sampling is typically carried
out using Markov chain Monte Carlo, in particular either the Glauber dynamics
or the Metropolis-Hasting procedure.
  In this paper we characterize the high and low temperature regimes of the
exponential random graph model. We establish that in the high temperature
regime the mixing time of the Glauber dynamics is $\Theta(n^2 \log n)$, where
$n$ is the number of vertices in the graph; in contrast, we show that in the
low temperature regime the mixing is exponentially slow for any local Markov
chain. Our results, moreover, give a rigorous basis for criticisms made of such
models. In the high temperature regime, where sampling with MCMC is possible,
we show that any finite collection of edges are asymptotically independent;
thus, the model does not possess the desired reciprocity property, and is not
appreciably different from the Erd\H{o}s-R\'enyi random graph.
