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 \emph{ 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.
Categories: cs.DS cs.SI