2022/08/12 by Nicholas A. Cook, Cook, Nicholas A., Amir Dembo +1 · 1 citation
Physics and Astronomy · #05C80 #60C05 #60F10 #82B26 #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2208.06397
openalex publication_date 2022/08/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider general Exponential Random Graph Models (ERGMs) where the sufficient statistics are functions of homomorphism counts for a fixed collection of simple graphs Fk. Whereas previous work has shown a degeneracy phenomenon in dense ERGMs, we show this can be cured by raising the sufficient statistics to a fractional power. We rigorously establish the naïve mean-field approximation for the partition function of the corresponding Gibbs measures, and in case of "ferromagnetic" models with vanishing edge density show that typical samples resemble a typical Erdős--Rényi graph with a planted clique and/or a planted complete bipartite graph of appropriate sizes. We establish such behavior also for the conditional structure of the Erdős--Rényi graph in the large deviations regime for excess Fk-homomorphism counts. These structural results are obtained by combining quantitative large deviation principles, established in previous works, with a novel stability form of a result of [5] on the asymptotic solution for the associated entropic variational problem. A technical ingredient of independent interest is a stability form of Finner's generalized Hölder inequality.