Mixing Time of Conditional Two Star Exponential Random Graphs

Source abstract

Two star exponential random graph models (ERGMs) are an interesting special case of both general ERGMs and mean-field Ising models. In this paper, we study two star ERGMs conditioning on the edge density $p$. We begin with an analytic characterization of the replica symmetric region, where the conditional model is close in cut distance to the Erdős--Rényi random graph $G(n,p)$. We prove that this region is twice as large as the corresponding region for the unconditional model. To study refined properties of the conditional model, we then analyze the global Kawasaki algorithm for sampling from it. Within the replica symmetric region, and under the additional condition that $4βp(1-p)<0.5$ when $|p-1/2|\lesssim 0.4632$, where $β$ is the model parameter, we prove metastable fast mixing of the Kawasaki algorithm. As corollaries, we obtain a weak Poincaré inequality and use it to deduce concentration inequalities of optimal order for conditional subgraph counts. The additional condition $4βp(1-p)<1/2$ if $|p-1/2|\lesssim 0.4632$ comes from our proof technique of contractive coupling. This bottleneck did not appear in previous studies applying the contractive coupling technique to unconditional ERGMs.