Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Graphon
Summary
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 .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.