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,\ell )$ independently with probability $f(U_{k},U_{\ell })$. For example, edge $(3,5)$ (green, dotted) is present with probability $f(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 (also known as a graph limit) is a symmetric measurable function $W:[0,1]^{2}\to [0,1]$, that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. 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.