Random Graphs

From TechWiki


A random undirected Erdős–Rényi graph consists of n nodes, l links and link probability p with binomial degree distribution

\mathcal{P} (k_i = k) = {n\choose k} p^k (1-p)^{n-k},

where ki is the degree of node i. The first terms gives the number of equivalent choices of such a network. The remaining terms describe the probability of a graph with k links and n nodes existing.

Note that a network of n nodes has maximally the following number of links

l_{max} = \frac{1}{2} n (n-1),

and it holds that

z := \langle k \rangle = \frac{l}{n} = p (n-1).

In the limit of large n the following approximation become exact

\mathcal{P} (k) \approx \frac{z^k  e^{-z}}{k!},
z \approx p n.

This can be seen by noting that

e^{-z} = \lim_{n \to \infty} \left( 1 + \frac{-z}{n} \right),
1 =\lim_{n \to \infty} \left( \frac{n!}{n^k (n-k)!} \right).

Observe that \mathcal{P} (k) now describes a Poisson distribution.


Directed networks are described by a joint probability density \mathcal{P} (k_{in}, k_{out}). Note, however, that generally this function is not factorizable, i.e., \mathcal{P} (k_{in}, k_{out}) \neq \mathcal{P} (k_{in}) \mathcal P( k_{out}).

The realization of the random directed network is based on the undirected case, where the links get assigned a direction with equal probability. This choice results in the halving of the number of links. Note that ktot: = kin + kout and kin = kout. One finds in this case that

\mathcal{P}  (k_{in}, k_{out}) =  \mathcal{P} (k_{in})  \mathcal P( k_{out}),
\mathcal{P}  (k_{*}) = \frac{{z_{*}}^{k_{*}}  e^{-z_{*}}}{k_*!},  \quad *={in, out, tot},
2zin = 2zout = ztot = ptotn = (pin + pout)n,

where ptot corresponds to p of the undirected case, pin = pout = 0.5ptot and z = ztot.

The relationship between the degree distributions of the directed and undirected case are given by

\mathcal{P} (k) = \sum_{k_{in}} \mathcal{P} (k_{in}, k - k_{in}).

In the case of a directed random graph one finds

\sum_{k_{in}} \mathcal{P} (k_{in}, k - k_{in}) = \sum_{k_{in}} \frac{{z_{in}}^{k_{in}}  e^{-z_{in}}}{k_{in}!}   \frac{{\langle k- k_{in} \rangle}^{k-k_{in}}  e^{\langle k- k_{in} \rangle}}{(k-k_{in})!}
=  z_{in}^k e^{-z_{tot}} \sum_{k_{in}} \frac{1}{k_{in}! (k-k_{in})!}
=  \frac{{z_{tot}}^{k}  e^{-z_{tot}}}{k!}  = \frac{{z}^{k}  e^{-z}}{k!} = \mathcal{P} (k),

by noting that

\langle k- k_{in} \rangle = z_{in},
2^k = \sum_i \frac{k!}{i!(k-i)!}.

The last identity is given by Pascal's triangle and the rules for binomial coefficients.