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 GraphSearch.
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.