  We develop approximate estimation methods for exponential random graph models
(ERGMs), whose likelihood is proportional to an intractable normalizing
constant. The usual approach approximates this constant with Monte Carlo
simulations, however convergence may be exponentially slow. We propose a
deterministic method, based on a variational mean-field approximation of the
ERGM's normalizing constant. We compute lower and upper bounds for the
approximation error for any network size, adapting nonlinear large deviations
results. This translates into bounds on the distance between true likelihood
and mean-field likelihood. Monte Carlo simulations suggest that in practice our
deterministic method performs better than our conservative theoretical
approximation bounds imply, for a large class of models.
