Joint work with Giulio Zucal · Preprint
Classical graphons describe limits of dense simple graphs through symmetric measurable functions from the unit square into $[0,1]$. For weighted or coloured networks a single number at each pair of latent positions is often too restrictive. A probability graphon instead assigns to each pair $(x,y)$ an entire probability measure
$$ W:[0,1]^2 \longrightarrow \mathcal{P}(\mathsf{Z}), $$on a Polish space $\mathsf{Z}$ of possible edge values, generalising graphons from $[0,1]$-valued to measure-valued entries. The symmetric case corresponds to undirected graphs; the non-symmetric case covers directed ones. The large-deviation results below are proved under the standing assumption that $\mathsf{Z}$ is compact.
The large-deviation problem
Consider a dense random weighted graph on $n$ vertices whose edge weights are sampled independently from a common reference measure $\nu$ on $\mathsf{Z}$ — the exact weighted analogue of the Erdős–Rényi model. Its empirical network can be represented as a probability graphon. We establish a large-deviation principle on the space of unlabelled probability graphons, that is modulo weak isomorphism, equipped with the unlabelled cut metric.
The rate function has the integrated relative-entropy form
$$ I_\nu(W) \;=\; \int_{[0,1]^2} \mathcal{H}\!\left(W(x,y)\,\middle|\,\nu\right)\, \mathrm{d}x\, \mathrm{d}y, $$where $\mathcal{H}(\,\cdot\mid\nu)$ is the Kullback–Leibler divergence with respect to the reference edge law. The principle holds at speed $n^2/2$, so informally
$$ \mathbb{P}\bigl(W_{G_n}\approx W\bigr) \;\asymp\; \exp\!\left[-\frac{n^2}{2}\, I_\nu(W)\right]. $$Atypical macroscopic weighted-network structures therefore carry an exponential cost determined by the local information needed to deform the reference edge distribution.
Main contributions
- A large-deviation principle for probability graphons induced by dense random weighted graphs, with a good rate function given by the integrated relative entropy above.
- A Sanov-type theorem in the graphon setting, where the role of the empirical measure is played by the measure-valued limit of the edge weights. The averaging is local — via integrals over subsets of $[0,1]^2$ — rather than the global $1/n$ averaging of the classical statement.
- A generalisation of the Chatterjee–Varadhan large-deviation theory beyond its binary setting: their rate function is recovered in the special case $\mathsf{Z}=\{0,1\}$, and the result extends to arbitrary edge-weight distributions on a compact Polish space.
- A companion concentration result: conditioned on a closed rare event, the set of minimisers of $I_\nu$ is non-empty and compact, and the model concentrates on it in cut distance.
Why this matters
Many networks are naturally weighted or categorical rather than binary. Probability graphons provide a common language for their large-scale structure, while large deviations quantify the entropy cost of departing from independent edge sampling. This also supplies a foundation for models with interactions: rewarding selected network patterns leads to a variational competition between energy and entropy.
From large deviations to coloured ERGMs
In our subsequent preprint Colorful Exponential Random Graph Models, joint with Bhaswar B. Bhattacharya, Ankan Ganguly and Giulio Zucal, we develop this connection for networks with finitely many edge colours.
The large-deviation principle, combined with Varadhan’s lemma, gives a variational expression for the limiting free energy. Its maximisers describe the typical large-network structures. We identify families with constant maximisers (replica symmetry), derive a high-temperature uniqueness criterion, and study how structured phases emerge through symmetry breaking and zero-temperature selection.
The induced-wedge and rainbow-triangle models illustrate how local pattern preferences can produce macroscopic organisation. These results develop the coloured-network application of the large-deviation framework; the original paper below establishes the underlying theory for general compact edge-value spaces.
Coloured ERGMs: results and examples →
Paper
Pierfrancesco Dionigi and Giulio Zucal, Large deviations for probability graphons, arXiv:2509.14204.