ErdsRényi

The Erdős–Rényi model is a family of random graphs introduced by Paul Erdős and Alfréd Rényi in 1959 and 1960. It comes in two standard formulations, G(n, p) and G(n, m). In G(n, p) each potential edge between the n vertices is included independently with probability p. In G(n, m) exactly m edges are chosen uniformly at random from the set of all possible edges.

In G(n, p), as n grows, several threshold phenomena occur. If p = c/n with constant c, there is a phase transition at c = 1: for c < 1 all components are small, while for c > 1 a giant component containing a positive fraction of the vertices appears. If p is enlarged to around (log n)/n, the graph becomes connected with high probability.

Degree distribution in G(n, p) is Binomial(n−1, p); in the sparse regime p = c/n this converges to a Poisson distribution with mean c. In particular, when p = c/n, the degrees are approximately Poisson.

Properties include that the model has low clustering in the sparse regime and that component sizes, connectivity, and the emergence of a giant component can be studied with rigorous threshold results. Distances are typically logarithmic in n in the sparse regime and shrink in denser regimes.

Applications include theoretical studies of random graphs, phase transitions, network reliability, and benchmarking for network algorithms. Limitations are its lack of clustering and realistic degree distributions for many real-world networks. Variants and extensions include inhomogeneous random graphs, geometric variants, and models with preferential attachment.