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. Replacing each edge value by a probability measure gives a single limit object for all of them while preserving the nonlinear observables that statistical mechanics and large-deviation analysis need. The resulting variational framework is a natural starting point for a theory of weighted, coloured and multiplex exponential random graph models — a direction this work opens rather than develops.
Paper
Pierfrancesco Dionigi and Giulio Zucal, Large deviations for probability graphons, arXiv:2509.14204.