Graphon

A realization of an exchangeable random graph defined by a graphon. The graphon is shown as a magenta heatmap (lower right). A random graph of size $n$ is generated by independently assigning to each vertex $k \in \{1,\dotsc,n\}$ a latent random variable $U_{k} \sim \mathrm{U}(0,1)$ (values along vertical axis) and including each edge $(k,l)$ independently with probability $W(U_{k},U_{l})$. For example, edge $(3,5)$ (green, dotted) is present with probability $W(0.72,0.9)$; the green boxes in the right square represent the values of $(u_{3},u_{5})$ and $(u_{5},u_{3})$. The upper left panel shows the graph realization as an adjacency matrix.

In graph theory and statistics, a graphon is a symmetric measurable function $W:[0,1]^2\to[0,1]$, that is important in the study of dense graphs. Graphons arise as the fundamental objects in two areas: as the defining objects of exchangeable random graph models and as a natural notion of limit for sequences of dense graphs. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs.

Graphons are sometimes referred to as “continuous graphs”, but this is bad practice because there are many distinct objects that this label might be applied to. In particular, there are generalizations of graphons to the sparse graph regime that could just as well be called “continuous graphs.”

Definition

A graphon is a symmetric measurable function $W:[0,1]^{2}\to[0,1]$. Usually a graphon is understood as defining an exchangeable random graph model according to the following scheme:

1. Each vertex $j$ of the graph is assigned an independent random value $u_{j}\sim U[0,1]$
2. Edge $(i,j)$ is independently included in the graph with probability $W(u_{i},u_{j})$.

A random graph model is an exchangeable random graph model if and only if it can be defined in terms of a (possibly random) graphon in this way.

It is an immediate consequence of this definition and the law of large numbers that, if $W\neq0$, exchangeable random graph models are dense almost surely.^[1]

Examples

The simplest example of a graphon is $W=p$ for some constant $p\in[0,1]$. In this case the associated exchangeable random graph model is the Erdős–Rényi model that includes each edge independently with probability $p$.

The Erdős–Rényi model can be generalized by:

1. Divide the unit square into $K\times K$ block
2. Let $W$ equal $p_{lm}$ on the $l,m$th block.

Effectively, this gives rise to the random graph model that has $K$ distinct Erdős–Rényi graphs with parameters $p_{ll}$ respectively and bigraphs between them where each possible edge between blocks $l,l$ and $m,m$ is included independently with probability $p_{lm}$. This is simply the $K$ community stochastic block model.

Many other popular random graph models can be understood as exchangeable random graph models defined by some graphon, a detailed survey is included in.^[1]

Jointly exchangeable adjacency matrices

A random graph of size $n$ can be represented as a random $n\times n$ adjacency matrix. In order to impose consistency (in the sense of projectivity) between random graphs of different sizes it is natural to study the sequence of adjacency matrices arising as the upper-left $n\times n$ sub-matrices of some infinite array of random variables; this allows us to generate $G_{n}$ by adding a node to $G_{n-1}$ and sampling the edges $(j,n)$ for $j<n$. With this perspective, random graphs are defined as random infinite symmetric arrays $(X_{ij})$.

Following the fundamental importance of exchangeable sequences in classical probability, it is natural to look for an analogous notion in the random graph setting. One such notion is given by jointly exchangeable matrices; i.e. random matrices satisfying

$(X_{ij}) \ \overset{d}{=} \, (X_{\sigma(i)\sigma(j)})$

for all permutations $\sigma$ of the natural numbers, where $\overset{d}{=}$ means equal in distribution. Intuitively, this condition means that the distribution of the random graph is unchanged by a relabeling of its vertices: that is, the labels of the vertices carry no information.

There is a representation theorem for jointly exchangeable random adjacency matrices, analogous to de Finetti’s representation theorem for exchangeable sequences. This is a special case of the Aldous–Hoover theorem for jointly exchangeable arrays and, in this setting, asserts that the random matrix $(X_{ij})$ is generated by:

1. Sample $u_{j}\sim U[0,1]$ independently
2. $X_{ij}=X_{ji}=1$ independently at random with probability $W(u_i,u_j),$

where $W:[0,1]^2\to[0,1]$ is a (possibly random) graphon. That is, a random graph model has a jointly exchangeable adjacency matrix if and only if it is a jointly exchangeable random graph model defined in terms of some graphon.

Limits of sequences of dense graphs

Consider a sequence of graphs $(G_n)$ where the number of vertices of $G_{n}$ goes to infinity. It is possible to define several notions of convergence of such sequences, each of which may give rise to a distinct limit object. For example, if the sequence $(G_n)$ was a realization of an Erdős–Rényi graphs with parameter $p$ the natural notion of limit would be the edge density of the graphs, which converges to $p$. In this case it would be natural to say that the limit of the sequence is the constant graphon $W=p$. It turns out that for sequences of dense graphs a number of apparently distinct notions of convergence are equivalent and under all of them the natural limit object is a graphon.^[2]

Related notions

Graphons are naturally associated with dense simple graphs. There are straightforward extensions to dense directed weighted graphs. There are also recent extensions to the sparse graph regime, from both the perspective of random graph models ^[3] and graph limit theory.^[4][5]

References

1. Orbanz, P.; Roy, D.M. "Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures". IEEE Transactions on Pattern Analysis and Machine Intelligence 37 (2): 437–461.
2. Lovász, L. Large Networks and Graph Limits. American Mathematical Society.
3. Veitch, V.; Roy, D. M. "The Class of Random Graphs Arising from Exchangeable Random Measures". arXiv:1512.03099.
4. Borgs, C.; Chayes, J. T.; Cohn, H.; Zhao, Y. "An L^p theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions". arXiv:1401.2906.
5. Borgs, C.; Chayes, J. T.; Cohn, H.; Zhao, Y. "An L^p theory of sparse graph convergence II: LD convergence, quotients, and right convergence". arXiv:1408.0744.