## Fall 2014: Theory Seminar

Donald Bren Hall, Room 1425, 1:00pm

December 5, 2014:

#
ERGMs are Hard

##
Michael Bannister

We investigate the computational complexity of the exponential random
graph model (ERGM) commonly used in social network analysis. This model
represents a probability distribution on graphs by setting the
log-likelihood of generating a graph to be a weighted sum of feature
counts. These log-likelihoods must be exponentiated and then normalized
to produce probabilities, and the normalizing constant is called the
*partition function*. We show that the problem of computing the
partition function is $\mathsf{\#P}$-hard, and inapproximable in
polynomial time to within an exponential ratio, assuming $\mathsf{P}
\neq \mathsf{NP}$. Furthermore, there is no randomized polynomial time
algorithm for generating random graphs whose distribution is within
total variation distance $1-o(1)$ of a given ERGM. Our proofs use
standard feature types based on the sociological theories of assortative
mixing and triadic closure.

(Joint work with Will
Devanny and David Eppstein.)