Random graphs

These notes are intended to supplement the very brief mention of random graphs in the slides for Session 12.

Erdős–Rényi model

The Erdős–Rényi model (1959) of random undirected graph generation is that \(G_{n,p} = (V,E)\) where \(n\) is the number of vertices \(|V|\) and the probability of forming an edge \((u,v) \in E\) (where \(u \neq v\)) is given by \(p\). (A variant is to generate all possible graphs with the given number of vertices and edges and select between them with uniform probability, but this variant is not now used much.)

Watts-Strogatz model

The Watts-Strogatz model (1998) describes a graph \(G_{n,k,p} = (V,E)\) where \(n\) is \(|V|\), \(k\) is the initial degree of a node (an even integer) and \(p\) is a rewiring probability. It starts with a ring of nodes, with each node connected to its \(k\) nearest neighbours with undirected edges (a ring lattice). Each of the starting edges \((u,v)\) is visited in turn (\(u<v\), starting with a circuit of the edges to the nearest neighbours, then to the next nearest and so on) and replaced with a new edge \((u,v')\) with probability \(p\). \(v'\) is chosen randomly, duplicate edges are forbidden, but original edges may end up being reinstated. If \(p\) is \(0\), there is no rewiring, if \(p\) is 1, every edge is rewired randomly (although slightly differently from Erdős–Rényi).

Watts and Strogatz (1998) make the additional stipulation that \(n \gg k \gg ln(n) \gg 1\) where \(k \gg ln(n)\) guarantees that the graph will be connected.

Note that Easley and Kleinberg's informal description is unlike Watts-Strogatz in not starting from a ring lattice and in not removing edges. Easley and Kleinberg discuss a variant of Watts-Strogatz (due to Kleinberg, 2000) where the random links are generated with probability proportional to the inverse square of the distance between two nodes. There are many other additional models.

The Erdős–Rényi paper is here:

http://www.renyi.hu/~p_erdos/1959-11.pdf

The Watts-Strogatz paper is here:

http://www.nature.com/nature/journal/v393/n6684/full/393440a0.html