Random Graphs

/* Undirected */

New page

=Undirected=

A random undirected Erdős–Rényi graph consists of ''n'' nodes, ''l'' links and link
probability ''p'' with binomial degree distribution
: <math> \mathcal{P} (k_i = k) = {n\choose k} p^k (1-p)^{n-k}, </math>
where <math>k_i</math> 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
: <math> l_{max} = \frac{1}{2} n (n-1), </math>
and it holds that
: <math> z := \langle k \rangle = \frac{l}{n} = p (n-1). </math>

In the limit of large ''n'' the following approximation become exact
: <math> \mathcal{P} (k) \approx \frac{z^k e^{-z}}{k!},</math>
: <math> z \approx p n.</math>

This can be seen by noting that
: <math> e^{-z} = \lim_{n \to \infty} \left( 1 + \frac{-z}{n} \right), </math>
: <math> 1 =\lim_{n \to \infty} \left( \frac{n!}{n^k (n-k)!} \right).</math>

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

=Directed=

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

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 <math>k_{tot} := k_{in} + k_{out}</math> and <math>k_{in} =
k_{out}</math>. One finds in this case that
: <math>\mathcal{P} (k_{in}, k_{out}) = \mathcal{P} (k_{in}) \mathcal P( k_{out}),</math>
: <math>\mathcal{P} (k_{*}) = \frac{{z_{*}}^{k_{*}} e^{-z_{*}}}{k_*!}, \quad *={in, out, tot}, </math>
: <math>2 z_{in} = 2 z_{out} = z_{tot} = p_{tot} n = (p_{in} + p_{out}) n,</math>

where <math>p_{tot}</math> corresponds to ''p'' of the undirected case, <math>p_{in}
= p_{out} = 0.5 p_{tot}</math> and <math>z = z_{tot}</math>.

The relationship between the degree distributions of the directed and
undirected case are given by
: <math> \mathcal{P} (k) = \sum_{k_{in}} \mathcal{P} (k_{in}, k - k_{in}).</math>

In the case of a directed random graph one finds
: <math> \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})!} </math>
: <math> = z_{in}^k e^{-z_{tot}} \sum_{k_{in}} \frac{1}{k_{in}! (k-k_{in})!} </math>
: <math> = \frac{{z_{tot}}^{k} e^{-z_{tot}}}{k!} = \frac{{z}^{k} e^{-z}}{k!} = \mathcal{P} (k),</math>
by noting that
: <math> \langle k- k_{in} \rangle = z_{in},</math>
: <math> 2^k = \sum_i \frac{k!}{i!(k-i)!}.</math>
The last identity is given by Pascal's triangle and the rules for binomial coefficients.

[[Category:Physics]]

Physics

/* In-Depth */

 * [[Fun with Non-Linear Dynamics]]
+* [[Random Graphs]]
 ===Beyond the Current World View===

TechWiki - Recent changes [en]

Random Graphs

Physics