= Solution
For the \b[<Erdős-Rényi model> $G(n,p)$], choose the number $n$ of <vertices> and an edge <probability> $0\leq p\leq1$. Visit every unordered pair of distinct <vertices> once and include its <edge> independently with <probability> $p$. This construction gives a <simple graph> with expected edge count $p\binom n2$ and mean <vertex degree> $p(n-1)$.
Increasing $p$ at fixed $n$ makes the <graph> denser, increases typical <vertex degree> and local <clustering coefficient>, and tends to shorten <graph distances> and improve connectivity. Increasing $n$ at fixed $p$ also increases the mean <vertex degree>; to retain a sparse comparison one instead decreases $p$ approximately as $1/n$.
Its <degree distribution> is <binomial distribution>, approximately <Poisson distribution> in the sparse large-$n$ regime, so it is \b[not a <scale-free network>]. Connected realizations can have short <average shortest path length>, but their <clustering coefficients> are not elevated above the random baseline they themselves define. Thus they are \b[not <small-world networks> under the high-clustering convention], although “small world” is sometimes used more loosely to mean only short distances.
Back to article page
