Random graph

Summary

A random graph is a graph chosen at random according to a probability distribution on a set of graphs. The most studied model is the Erdős–Rényi model $G(n, p)$, in which each possible edge on $n$ labelled vertices is present independently with probability $p$. One studies which properties hold with probability tending to $1$ as $n$ grows. There are sharp thresholds, for example for connectivity and for the appearance of a giant component. Random graphs are a main tool of the probabilistic method and a model for large real networks.