Exponential random graph models with soft clique constraints
2026-08-31 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors study a random graph model that favors graphs with fewer complete subgraphs (called r-cliques) for some fixed r ≥ 3. They show that as the number of vertices grows large, a typical graph in this model tends to look like a graph split into r-1 nearly equal parts, with most edges running between these parts and very few edges inside each part. This pattern holds regardless of how strongly the model favors fewer r-cliques, as long as that preference is positive. They also generalize their findings to models considering multiple clique sizes with separate weights.
random graphexponential random graph modelr-cliquevertex partitionedge densityasymptotic behaviorcomplete subgraphgraph structureclique numberprobability distribution on graphs
Authors
Yasmin Tousinejad, Vera Koponen
Abstract
Let $r\geq3$ be fixed, and let $\mathbf{G}_n$ be the set of all simple graphs with vertex set $[n]=\{1,\ldots,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 $\varepsilon > 0$ the density of edges within any part is less than $\varepsilon$. 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.