# Random Graphs

### From TechWiki

# Undirected

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

where *k*_{i} 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

and it holds that

In the limit of large *n* the following approximation become exact

This can be seen by noting that

Observe that now describes a Poisson distribution.

# Directed

Directed networks are described by a joint probability density . Note, however, that generally this function is not factorizable, i.e., .

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 *k*_{tot}: = *k*_{in} + *k*_{out} and *k*_{in} = *k*_{out}. One finds in this case that

- 2
*z*_{in}= 2*z*_{out}=*z*_{tot}=*p*_{tot}*n*= (*p*_{in}+*p*_{out})*n*,

where *p*_{tot} corresponds to *p* of the undirected case, *p*_{in} = *p*_{out} = 0.5*p*_{tot} and *z* = *z*_{tot}.

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

In the case of a directed random graph one finds

by noting that

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