In graph theory and statistics, a graphon (also known as a graph limit) is a symmetric measurable function W : [ 0 , 1 ] 2 → [ 0 , 1 ] {\displaystyle 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.
Statistical formulation A graphon is a symmetric measurable function W : [ 0 , 1 ] 2 → [ 0 , 1 ] {\displaystyle W:[0,1]^{2}\to [0,1]} . Usually a graphon is understood as defining an exchangeable random graph model according to the following scheme:
Each vertex j {\displaystyle j} of the graph is assigned an independent random value u j ∼ U [ 0 , 1 ] {\displaystyle u_{j}\sim U[0,1]}
Edge ( i , j ) {\displaystyle (i,j)} is independently included in the graph with probability W ( u i , u j ) {\displaystyle 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. The model based on a fixed graphon W {\displaystyle W} is sometimes denoted G ( n , W ) {\displaystyle \mathbb {G} (n,W)} , by analogy with the Erdős–Rényi model of random graphs. A graph generated from a graphon W {\displaystyle W} in this way is called a W {\displaystyle W} -random graph. It follows from this definition and the law of large numbers that, if W ≠ 0 {\displaystyle W\neq 0} , exchangeable random graph models are dense almost surely.
Examples The simplest example of a graphon is W ( x , y ) ≡ p {\displaystyle W(x,y)\equiv p} for some constant p ∈ [ 0 , 1 ] {\displaystyle p\in [0,1]} . In this case the associated exchangeable random graph model is the Erdős–Rényi model G ( n , p ) {\displaystyle G(n,p)} that includes each edge independently with probability p {\displaystyle p} . If we instead start with a graphon that is piecewise constant by:
dividing the unit square into k × k {\displaystyle k\times k} blocks, and setting W {\displaystyle W} equal to p l m {\displaystyle p_{lm}} on the ( ℓ , m ) th {\displaystyle (\ell ,m)^{\text{th}}} block, the resulting exchangeable random graph model is the k {\displaystyle k} community stochastic block model, a generalization of the Erdős–Rényi model. We can interpret this as a random graph model consisting of k {\displaystyle k} distinct Erdős–Rényi graphs with parameters p ℓ ℓ {\displaystyle p_{\ell \ell }} respectively, with bigraphs between them where each possible edge between blocks ( ℓ , ℓ ) {\displaystyle (\ell ,\ell )} and ( m , m ) {\displaystyle (m,m)} is included independently with probability p ℓ m {\displaystyle p_{\ell m}} . 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.
… excerpt ends here. Continue reading the full article.
