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 is a symmetric measurable function , that is important in the study of dense graphs. Graphons arise as the fundamental objects in two areas: as the defining objects of exchangeable random graph models and as a natural notion of limit for sequences of dense graphs. 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.

Graphons are sometimes referred to as “continuous graphs”, but this is bad practice because there are many distinct objects that this label might be applied to. In particular, there are generalizations of graphons to the sparse graph regime that could just as well be called “continuous graphs.”

Definition

edit

A graphon is a measurable function  . Usually a graphon is understood as defining an exchangeable random graph model according to the following scheme:

  1. Each vertex   of the graph is assigned an independent random value  
  2. 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.

It is an immediate consequence of this definition and the law of large numbers that, if  , exchangeable random graph models are dense almost surely.[1]

Examples

edit

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  .

The Erdős–Rényi model can be generalized by:

  1. Divide the unit square into   block
  2. Let   equal   on the  th block.

Effectively, this gives rise to the random graph model that has   distinct Erdős–Rényi graphs with parameters   respectively and bigraphs between them where each possible edge between blocks   and   is included independently with probability  . This is simply the   community stochastic block model.

Many other popular random graph models can be understood as exchangeable random graph models defined by some graphon, a detailed survey is included in [1].

Jointly exchangeable adjacency matrices

edit

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:

  1. Sample   independently
  2.   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.

Limits of sequences of dense graphs

edit

Consider a sequence of graphs   where the number of vertices of   goes to infinity. It is possible to define several notions of convergence of such sequences, each of which may give rise to a distinct limit object. For example, if the sequence   was a realization of an Erdős–Rényi graphs with parameter   the natural notion of limit would be the edge density of the graphs, which converges to  . In this case it would be natural to say that the limit of the sequence is the constant graphon  . It turns out that for sequences of dense graphs a number of apparently distinct notions of convergence are equivalent and under all of them the natural limit object is a graphon. [2]

Related notions

edit

Graphons are naturally associated with dense simple graphs. There are straightforward extensions to dense directed weighted graphs. There are also recent extensions to the sparse graph regime, from both the perspective of random graph models [3] and graph limit theory [4] [5].

References

edit
  1. ^ a b Orbanz, P.; Roy, D.M. "Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures". Pattern Analysis and Machine Intelligence, IEEE Transactions on. 37 (2): 437–461.
  2. ^ Lovász, L. Large Networks and Graph Limits. American Mathematical Society.
  3. ^ Veitch, V.; Roy, D. M. "The Class of Random Graphs Arising from Exchangeable Random Measures". ArXiv e-prints.
  4. ^ Borgs, C.; Chayes, J. T.; Cohn, H.; Zhao, Y. "An $L^p$ theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions". ArXiv e-prints.
  5. ^ Borgs, C.; Chayes, J. T.; Cohn, H.; Zhao, Y. "An $L^p$ theory of sparse graph convergence II: LD convergence, quotients, and right convergence". ArXiv e-prints.