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 is generated by independently assigning to each vertex a latent random variable (values along vertical axis) and including each edge independently with probability . For example, edge (green, dotted) is present with probability ; the green boxes in the right square represent the values of and . 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 symmetricmeasurable function , 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.
![{\displaystyle W:[0,1]^{2}\to [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed1d68dec2c8a2552affdd7869423b1185846c34)