In the mathematical field of graph theory,ős–Ré 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.
Definition
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.
The behavior of random graphs are often studied in the case where , the number of vertices, tends to infinity. Although and can be fixed in this case, they can also be functions depending on . For example, the statement that almost every graph in is connected means that, as tends to infinity, the probability that a graph on vertices with edge probability is connected tends to .
Comparison between the two models
The expected number of edges in G(n, p) is , and by the law of large numbers any graph in G(n, p) will almost surely have approximately this many edges (provided the expected number of edges tends to infinity). Therefore, a rough heuristic is that if pn2 → ∞, then G(n,p) should behave similarly to G(n, M) with as n increases.
For many graph properties, this is the case. If P is any graph property which is monotone with respect to the subgraph ordering (meaning that if A is a subgraph of B and B satisfies P, then A will satisfy P as well), then the statements "P holds for almost all graphs in G(n, p)" and "P holds for almost all graphs in " are equivalent (provided pn2 → ∞). For example, this holds if P is the property of being connected, or if P is the property of containing a Hamiltonian cycle. However, this will not necessarily hold for non-monotone properties (e.g. the property of having an even number of edges).
In practice, the G(n, p) model is the one more commonly used today, in part due to the ease of analysis allowed by the independence of the edges.
Properties of G(n, p) With the notation above, a graph in G(n, p) has on average edges. The distribution of the degree of any particular vertex is binomial:
where n is the total number of vertices in the graph. Since
this distribution is Poisson for large n and np = const.
In a 1960 paper, Erdős and Rényi described the behavior of G(n, p) very precisely for various values of p. Their results included that:
If np < 1, then a graph in G(n, p) will almost surely have no connected components of size larger than O(log(n)). If np = 1, then a graph in G(n, p) will almost surely have a largest component whose size is of order n2/3. If np → c > 1, where c is a constant, then a graph in G(n, p) will almost surely have a unique giant component containing a positive fraction of the vertices. No other component will contain more than O(log(n)) vertices. If , then a graph in G(n, p) will almost surely contain isolated vertices, and thus be disconnected. If , then a graph in G(n, p) will almost surely be connected.
Thus is a sharp threshold for the connectedness of G(n, p).