Large Deviations Principle on the Mixing Times of Exponential Random Graph Models

Abstract

In this paper we introduce the concepts of large deviations principle to estimate the probabilities of rare events, and apply it to estimating the mixing time of exponential random graph models (ERGMs). We build upon results of large deviations principle applied to the simpler Er˝os-R´enyi random graph model from Chatterjee, Varadhan and Diaconis in order to better understand the convergence of exponential random graph models to a set of graphons. When the parameters β2, . . . , βk of the ERGM are nonnegative, the ERGM converges to a set of constant graphons. We theoretically examine specific cases of the edge-triangle model of the ERGM where their Markov chain representations take both long and short amounts of time to mix to the stationary distribution. We then empirically test several cases on a MCMC simulation that we built in Python.