## Sparse Exchangeable Graphs and Their Limits via Graphon Processes

*Christian Borgs, Jennifer T. Chayes, Henry Cohn, Nina Holden*; 18(210):1−71, 2018.

### Abstract

In a recent paper, Caron and Fox suggest a probabilistic model
for sparse graphs which are exchangeable when associating each
vertex with a time parameter in $\mathbb{R}_+$. Here we show that by
generalizing the classical definition of graphons as functions
over probability spaces to functions over $\sigma$-finite
measure spaces, we can model a large family of exchangeable
graphs, including the Caron-Fox graphs and the traditional
exchangeable dense graphs as special cases. Explicitly,
modelling the underlying space of features by a $\sigma$-finite
measure space $(S,\mathcal{S},\mu)$ and the connection probabilities by
an integrable function $W\colon S\times S\to [0,1]$, we
construct a random family $(G_t)_{t\geq 0}$ of growing graphs
such that the vertices of $G_t$ are given by a Poisson point
process on $S$ with intensity $t\mu$, with two points $x,y$ of
the point process connected with probability $W(x,y)$. We call
such a random family a graphon process. We prove that a
graphon process has convergent subgraph frequencies (with
possibly infinite limits) and that, in the natural extension of
the cut metric to our setting, the sequence converges to the
generating graphon. We also show that the underlying graphon is
identifiable only as an equivalence class over graphons with cut
distance zero. More generally, we study metric convergence for
arbitrary (not necessarily random) sequences of graphs, and show
that a sequence of graphs has a convergent subsequence if and
only if it has a subsequence satisfying a property we call
uniform regularity of tails. Finally, we prove that every
graphon is equivalent to a graphon on $\mathbb{R}_+$ equipped with
Lebesgue measure.

[abs][pdf][bib]