Tame sparse exponential random graphs

Peiyan Zhang, Remco van der Hofstad, Frank den HollanderBernoulli 2026 · DOI

TL;DR

This paper introduces a new class of "tame" sparse exponential random graph (ERG) models that can precisely control the fraction of vertices involved in triangles. By developing a second-order analysis of large deviation probabilities in Erdős-Rényi random graphs, the authors establish a framework for constructing ERGs that are both sparse and exhibit a tunable level of transitivity, a crucial feature for modeling real-world networks.

What Problem Does This Paper Address?

Real-world networks often exhibit a phenomenon called "clustering" or "transitivity," where neighbors of a vertex are more likely to be connected to each other, leading to a significant number of triangles. While exponential random graph models (ERGMs) are popular for capturing these properties, existing models struggle to simultaneously achieve sparsity (few edges relative to vertices) and a controlled, non-trivial number of triangles. Previous work showed that ERGs either had very few or almost all vertices in triangles, making them unrealistic. This paper addresses the challenge of creating sparse ERGs with a tunable, intermediate fraction of vertices participating in triangles.

Methods

The core of the paper lies in a novel, second-order non-linear large deviation analysis of the number of vertices in triangles ($V_T(G)$) within sparse Erdős-Rényi random graphs ($G(n, p_n)$ where $p_n = \lambda/n$). This analysis provides a precise estimate of the probability $P(V_T(G) \ge q)$ up to the second order. This detailed probabilistic understanding is then leveraged to:

  1. Construct new ERG models: Based on the number of vertices in triangles, allowing for fine-tuning of the triangle density.
  2. Derive a large deviation principle for the number of edges: This confirms that the proposed ERG models remain sparse.
  3. Develop consistent estimators: For the parameters of these new ERG models, which is crucial for practical applications.

The technical machinery involves detailed combinatorial arguments, probability theory (specifically large deviations), and variational calculus to optimize certain functions.

Datasets

Not discussed in the paper. The paper focuses on theoretical models of random graphs rather than empirical datasets.

Key Insights and Ideas

  • The "Critical Window" for Triangles: The paper identifies a specific regime for the ERG parameter $\beta$ (related to $\log n$) where the number of vertices in triangles transitions from being very low to very high. By precisely analyzing this "critical window," they can control the fraction of vertices in triangles to any desired value between 0 and 1.
  • Second-Order Large Deviations are Crucial: The ability to estimate probabilities up to the second order (beyond just the leading term) is what enables the precise control over triangle density and the proof of sparsity for the proposed ERG models. This is a significant technical advancement.
  • Disjoint Triangles and Sparsity: A key finding is that when a sparse random graph is conditioned to have a significant number of vertices in triangles, most of these triangles are vertex-disjoint. This, combined with the large deviation principle for edge counts, strongly suggests that the resulting graphs are indeed sparse.
  • Tunable Transitivity: The proposed ERG models offer a way to "tune" the transitivity of a network by adjusting a single parameter, making them more realistic for modeling diverse real-world networks.

Key Results

  • Precise Probability Estimate: The paper provides a second-order estimate for the large deviation probability $P(V_T(G_n) \ge q)$ in sparse Erdős-Rényi random graphs.
  • New ERG Models: Introduction of ERG models where the number of vertices in triangles can be controlled to a specific fraction $a \in (0,1)$ with high probability.
  • Sparsity Guarantee: Proof that these new ERG models exhibit a large deviation principle for the number of edges, confirming their sparsity.
  • Consistent Parameter Estimation: Development of methods to consistently estimate the parameters of the proposed ERG models from observed network data.
  • Disjoint Triangles Property: Demonstration that under the conditioning of having many vertices in triangles, most of these triangles are vertex-disjoint.

Limitations and Future Work

  • Generalizability of Estimation: While the paper demonstrates consistent estimation for a specific ERG model (linear tilting), the authors suggest that extending this to more complex ERG models with more parameters is a natural next step.
  • Central Limit Theorem for Edges: The paper's results on the number of edges suggest that a central limit theorem might hold, but proving this is challenging due to the lack of suitable correlation-type inequalities.
  • Local Limit of the Model: The authors conjecture that the local limit of their model is similar to an Erdős-Rényi graph with randomly dropped disjoint triangles, but proving this is difficult.
  • Alternative Graph Properties: The paper focuses on the number of vertices in triangles. Future work could explore models based on the number of edges in triangles or other graph properties, which might present more complex challenges.
  • Model Extension: Investigating the behavior of ERGs with a larger number of parameters and determining the generality of consistent parameter estimation are also suggested future directions.

Summary updated

Abstract

In this paper we obtain a precise estimate of the probability that the sparse binomial random graph contains a large number of vertices in a triangle. We compute the logarithm of this probability up to second order, which enables us to propose an exponential random graph model based on the number of vertices in a triangle. Specifically, by tuning a single parameter, we can with high probability induce any given fraction of vertices in a triangle. Moreover, in the proposed exponential random graph model we derive a large deviation principle for the number of edges. As a byproduct, we propose a consistent estimator of the tuning parameter.
BibTeX
@inproceedings{zhang2026tame,
  author = {Peiyan Zhang and Remco van der Hofstad and Frank den Hollander},
  title = {{Tame sparse exponential random graphs}},
  booktitle = {Bernoulli},
  year = {2026},
  doi = {10.3150/25-bej1926},
}
Figure