Exponential random graph models with soft clique constraints

Abstract

Let $r\ge 3$ be fixed, and let ${\mathbf{G}}_n$ be the set of all simple graphs with vertex set $[n]=\{1,\dots ,n\}$. We consider an exponential random graph model which gives higher probability to $G\in {\mathbf{G}}_n$ than to $H\in {\mathbf{G}}_n$ if $G$ has fewer $r$-cliques than $H$. But all graphs in ${\mathbf{G}}_n$ have positive probability. The degree to which graphs with fewer $r$-cliques are given higher probability is determined by a positive weight $w$. We prove that, asymptotically almost surely as $n\to \infty$, a random graph from ${\mathbf{G}}_n$ has a vertex partition into $r-1$ parts of roughly equal size, the density of edges between the parts is close to $1/2$, and for every $\epsilon >0$ the density of edges within any part is less than $\epsilon$. The asymptotic structural properties are independent of the weight $w$ as long as it is positive. We also extend the result to the context of several clique sizes, each one with its own weight.

58 pages, 1 figure