Erdős–Rényi model

In graph theory, the Erdős–Rényi model is either of two closely related models for generating random graphs. They are named after Paul Erdős and Alfréd Rényi, who first introduced one of the models in 1959; the other model was introduced independently and contemporaneously by Edgar Gilbert. In the model introduced by 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, 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 (ER) random graph model.

The behavior of random graphs are often studied in the case where n, the number of vertices, tends to infinity. Although p and M can be fixed in this case, they can also be functions depending on n. For example, the statement

means

The expected number of edges in G(n, p) is ${\displaystyle {\tbinom {n}{2}}p}$, 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 pn² → ∞, then G(n,p) should behave similarly to G(n, M) with ${\displaystyle M={\tbinom {n}{2}}p}$ as n increases.

...
Wikipedia