Graphon

In graph theory and statistics, a graphon (also known as a graph limit) is a symmetric measurable 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. A graphon is a symmetric measurable function . Usually a graphon is understood as defining an exchangeable random graph model according to the following scheme: Each vertex of the graph is assigned an independent random value Edge is independently included in the graph with probability . 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. The model based on a fixed graphon is sometimes denoted , by analogy with the Erdős–Rényi model of random graphs. A graph generated from a graphon in this way is called a -random graph. It follows from this definition and the law of large numbers that, if , exchangeable random graph models are dense almost surely. The simplest example of a graphon is for some constant . In this case the associated exchangeable random graph model is the Erdős–Rényi model that includes each edge independently with probability . If we instead start with a graphon that is piecewise constant by: dividing the unit square into blocks, and setting equal to on the block, the resulting exchangeable random graph model is the community stochastic block model, a generalization of the Erdős–Rényi model. We can interpret this as a random graph model consisting of distinct Erdős–Rényi graphs with parameters respectively, with bigraphs between them where each possible edge between blocks and is included independently with probability .