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.
Statistical formulation
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.
Examples
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 .
Many other popular random graph models can be understood as exchangeable random graph models defined by some graphon, a detailed survey is included in Orbanz and Roy.
Jointly exchangeable adjacency matrices
A random graph of size can be represented as a random 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 sub-matrices of some infinite array of random variables; this allows us to generate by adding a node to and sampling the edges for . With this perspective, random graphs are defined as random infinite symmetric arrays .
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
for all permutations of the natural numbers, where 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 is generated by:
Sample independently
independently at random with probability
where 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.
Graphon estimation
Due to identifiability issues, it is impossible to estimate either the graphon function or the node latent positions and there are two main directions of graphon estimation. One direction aims at estimating up to an equivalence class, or estimate the probability matrix induced by .
Analytic formulation
Any graph on vertices can be identified with its adjacency matrix . This matrix corresponds to a stepfunction , defined by partitioning into intervals such that has interior
and for each , setting equal to the
entry of . This function is the associated graphon of the graph .