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
Erdős–Rényi model
Summary
In the mathematical field of graph theory, the Erdős–Rényi model refers to one of two closely related models for generating random graphs or the evolution of a random network. These models are named after Hungarian mathematicians Paul Erdős and Alfréd Rényi, who introduced one of the models in 1959. Edgar Gilbert introduced the other model contemporaneously with and independently of Erdős and Rényi. In the model of Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely. In the model introduced by Gilbert, also called the Erdős–Rényi–Gilbert model, each edge has a fixed probability of being present or absent, independently of the other edges. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.
There are two closely related variants of the Erdős–Rényi random graph model.
In the model, a graph is chosen uniformly at random from the collection of all graphs which have nodes and edges. The nodes are considered to be labeled, meaning that graphs obtained from each other by permuting the vertices are considered to be distinct. For example, in the model, there are three two-edge graphs on three labeled vertices (one for each choice of the middle vertex in a two-edge path), and each of these three graphs is included with probability .
In the model, a graph is constructed by connecting labeled nodes randomly. Each edge is included in the graph with probability , independently from every other edge. Equivalently, the probability for generating each graph that has nodes and edges is The parameter in this model can be thought of as a weighting function; as increases from to , the model becomes more and more likely to include graphs with more edges and less and less likely to include graphs with fewer edges. In particular, the case corresponds to the case where all graphs on vertices are chosen with equal 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.