03. Random Networks¶

Contents¶

• 03.01. Introduction
• 03.02. The Random Network Model
  • Box 03.01. Defining Random Networks
  • Box 03.02. Random Networks: a Brief History
• 03.03. Number of Links
  • Box 03.03. Binomial Distribution: Mean and Variance
• 03.04. Degree Distribution
  • 03.04.01. Binomial Distribution
  • 03.04.02. Poisson Distribution
• 03.05. Real Networks are Not Poisson
  • Box 03.04 Why are Hubs Missing?
• 03.06. The Evolution of a Random Network
  • Box 03.05. Network Evolution in Graph Theory
• 03.07. Real Networks are Supercritical
• 03.08. Small Worlds
  • Box 03.06. 19 Degrees of Separation
  • Box 03.07. Six Degrees: Experimental Confirmation
  • Box 03.08. 19 Degrees of the WWW
• 03.09. Clustering Coefficient
  • Box 03.09. Watts-Strogatz Model
• 03.10. Summary: Real Networks are Not Random
• ...
• 03.16. Advanced Topic 3.E Fully Connected Regime

03.01. Introduction¶

03.02. The Random Network Model¶

$N$ nodes, connected w/ probability $p$

Box 03.01. Defining Random Networks¶

• $G(N,L)$ model :
  • $N$ labeled node are connedted with $L$ randomly placed links
  • fixes the total num of links $L$
  • average degree of node $\langle k \rangle = \frac{2L}{N}$
• $G(N,p)$ model :
  • $N$ labeled nodes is connected with probability $p$
  • fixes prob $p$

¶

random graph (random network, Erdős-Rényi network)

Box 03.02. Random Networks: a Brief History¶

• Anatol Rapoport
• Random graph theory Pál Erdős and Alfréd Rényi
• Edgar Nelson Gilbert

03.03. Number of Links¶

• prob that $L$ of attempts to connect $\frac{N(N-1)}{2}$ pairs of nodes have result in link, is $p^L$
• prob that the remaining $\frac{N(N-1)}{2}$ pairs of nodes have not resulted in a link is $(1-p)^{\frac{N(N-1)}{2}-L}$
• conmbinational factor $$\binom{\frac{N(N-1)}{2}}{L} \tag{3.0}$$

$$p_L = \binom{\frac{N(N-1)}{2}}{L} p^L (1 - p)^{\frac{N (N - 1)}{2} - L} \tag{3.1}$$

expected num of links

$$\langle L \rangle = \sum_{L=0}^{\frac{N(N-1)}{2}} LP_L = p \frac{N(N-1)}{2} \tag{3.2}$$

$L_{max} = \frac{N(N-1)}{2}$

$$\langle k \rangle = \frac{2 \langle L \rangle}{N} = p (N - 1) \tag{3.3}$$

from $\langle k \rangle = 0$ to $\langle k\rangle = N-1$

$p = \frac{1}{6}$, $N=12$, $L = 10, 18, 8$

$p = .03$, $N = 100$

Box 03.03. Binomial Distribution: Mean and Variance¶

$$p_x = \binom{N}{x} p^x (1-p)^{N-x}$$

$$\langle x \rangle = \sum_{x=0}^N xp_x = Np \tag{3.4}$$

$$\langle x^2 \rangle = \sum_{x=0}^N x^2 p_x = p(1-p)N + p^2 N^2 \tag{3.5}$$

standard deviation

$$\begin{align*} \sigma_x &= \big( \langle x^2 \rangle - \langle x \rangle^2 \big)^{\frac{1}{2}} \\ &= [ p(1 - p) N ]^{\frac{1}{2}} \end{align*} \tag{3.6}$$

03.04. Degree Distribution¶

degree dist $p_k$, degree $k$

		Binominal	Poisson
degree dist	$p_k$	$\binom{N-1}{k}p_k(1-p)^{N-1-k}$	$e^{-\langle k \rangle} \frac{\langle k \rangle}{k!}$
peak at	$k$	$\langle k \rangle = p(N-1)$	$\langle k \rangle$
width	$\sigma_k$	$p(1-p)(N-1)$	$\langle k \rangle^{\frac{1}{2}}$

03.04.01. Binomial Distribution¶

prob that node $i$ has $k$ links is product of 3 terms:

1. prob that $k$ of its links are present / $p^k$
2. prob that remaining ($N-1-k$) links are missing / $(1-p)^{N-1-k}$

3. $$\binom{N-1}{k}$$

$$p_k = \binom{N-1}{k} p^k (1-p)^{N-1-k} \tag{3.7}$$

average degree $\langle k \rangle$ second moment $\langle k^2 \rangle$ & variance $\sigma_k$

03.04.02. Poisson Distribution¶

sparse networks: $\langle k \rangle \ll N$

eq.3.7 is approx'd by Poisson dist

$$p_k = e^{- \langle k \rangle } \frac{\langle k \rangle^k}{k!} \tag{3.8}$$

degree distributioin of a random network

The degree distribution of a random network with ‹k› = 50 and N = 102, 103, 104. Small Networks: Binomial For a small network (N = 102) the degree distribution deviates significantly from the Poisson form (3.8), as the condition for the Poisson approximation, N»‹k›, is not satisfied. Hence for small networks one needs to use the exact binomial form (3.7) (green line).

Large Networks: Poisson For larger networks (N = 103, 104) the degree distribution becomes indistinguishable from the Poisson prediction (3.8), shown as a continuous grey line. Therefore for large N the degree distribution is independent of the network size. In the figure we averaged over 1,000 independently generated random networks to decrease the noise.

03.05. Real Networks are Not Poisson¶

social network $\langle k \rangle \approx 1000$, $N \approx 7 \times10^9$ of individuals

$k_{\text{max}} = 1185$ accuaitances

$k_{\text{min}} = 816$

despersion of random network is $\sigma_k = \langle k \rangle^{\frac{1}{2}}$, for $\langle k \rangle = 1000$ $\sigma_k = 31.62$ $\langle k \rangle \pm \sigma_k$ range

in a large random network the degree of most nodes is in the narrow vicinity of $\langle k \rangle$

Box 03.04. Why are Hubs Missing?¶

$\frac{1}{k!}$

the Stirling approx

$k! \sim \sqrt{2\pi k} \bigg(\frac{k}{e}\bigg)^k$

rewrite eq.3.8 as:

$$p_k = \frac{e^{- \langle k \rangle}}{\sqrt{2\pi k}}\bigg(\frac{e\langle k \rangle}{k}\bigg)^k \tag{3.9}$$

$$k > e \langle k \rangle$$

¶

03.06. The Evolution of a Random Network¶

the size of the largest conneted cluster w/i the network, $N_G$ varies w/ $\langle k \rangle$

• for $p=0$ we have $\langle k \rangle = 0$, ∴ $N_G = 1$ and $\frac{N_G}{N} \rightarrow 0$ for large $N$
• for $p = 1$ we have $\langle k \rangle = N-1$, complete graph, ∴ $N_G = N$ and $\frac{N_G}{N} = 1$

grow from $N_G = 1$ to $N_G = N$ if $\langle k \rangle$ increase from $0$ to $N-1$

Erdős P., Rényi A., 1960 condition for teh emergence of the giant component is (Erdős P., Rényi A., 1960):

$$\langle k \rangle = 1 \tag{3.10}$$

express eq.3.10 in terms of $p$ using eq.3.3 $\langle k \rangle = \frac{2 \langle L \rangle}{N} = p(N-1)$

$$p_c=\frac{1}{N-1}\approx\frac{1}{N} \tag{3.11}$$

the larger network, the smaller $p$ is sufficient for the giant component

4 regimes:

Subcritical regime: $0 < \langle k \rangle < 1$ ($p < \frac{1}{N}$)

for $\langle k \rangle < 1$, $N_G \sim \ln{N}$

∴ $\frac{N_G}{N} \simeq \frac{\ln{N}}{N} \rightarrow 0$, $[N \rightarrow \infty$

Critical point: $\langle k \rangle = 1$ ($p = \frac{1}{N}$)

size of the largest component is $N_G \sim N^{\frac{2}{3}}$

$\frac{N_G}{N} \sim N^{-\frac{1}{3}}$ in the $N \rightarrow \infty$ limit

e.g., $N = 7 \times 10^9$ nodes

for $\langle k \rangle < 1$, $N_G \simeq \ln{N} = \ln{(7\times10^9)} \simeq 22.7$

for $\langle k \rangle = 1$, $N_G \sim N^{\frac{2}{3}} = (7 \times 10^9)^{\frac{2}{3}} \simeq 3\times10^6$

Supercritical Regime: $\langle k \rangle > 1$ ($p > \frac{1}{N}$)

$$\frac{N_G}{N} \sim \langle k \rangle-1 \tag{3.12}$$

or

$$N_G \sim (p-p_c)N \tag{3.13}$$

where $p_c$ is given by eq.3.11 ($p_c = \frac{1}{N-1} \approx \frac{1}{N}$)

Connected Regime: $\langle k \rangle > \ln{N}$ ($p > \frac{\ln{N}}{N}$)

$$N_G \simeq N$$

$$\langle k \rangle = \ln{N} \tag{3.14}$$

$\frac{\ln{N}}{N} \rightarrow 0$ for large $N$

Box 03.05. Network Evolution in Graph Theory¶

$p(N)$ scales as $N^z$ where $z$ is tunable param $[-\infty, 0]$

03.07. Real Networks are Supercritical¶

• $\langle k \rangle = 1$
• $\langle k \rangle > \ln{N}$

Network	$N$	$L$	$\langle K \rangle$	$\ln{N}$
Internet	192,244	609,066	6.34	12.17
Power Grid	4,941	6,594	2.67	8.51
Science Collaboration	23,133	94,437	8.08	10.05
Actor Network	702,388	29,397,908	83.71	13.46
Protein Interactions	2,018	2,930	2.90	7.61

most real networks are in the supercritical regime

giant component coexist w/ many disconnected components

03.08. Small Worlds¶

small world phenomenon aka, six degrees of separation

the distance between two randomly chosen nodes in a network is short

2 questions: - short mean - existenxe of these shord distances

• $\langle k \rangle$ nodes at distance $d = 1$
• $\langle k \rangle^2$ nodes at distance $d = 2$
• $\langle k \rangle^3$ nodes at distance $d = 3$
• ...
• $\langle k \rangle^d$ nodes at distance $d$

num of nodes up to distance $d$

$$\begin{align*} N(d) &\approx 1 + \langle k \rangle + \langle k \rangle^2 + \cdots + \langle k \rangle^d \\ &= \frac{\langle k \rangle^{d+1} - 1}{\langle k \rangle - 1} \end{align*} \tag{3.15}$$

max distance $d_{max}$ or the network's diameter

$$N(d_{max}) \approx N \tag{3.16}$$

assuming the $\langle k \rangle \gg 1$,

$$\langle k \rangle^{d_{max}} \approx N \tag{3.17}$$

∴ the diamter of network follows

$$d_{max} \approx \frac{\ln{N}}{\ln{k}} \tag{3.18}$$

• average distance between 2 randomly chosen nodes $\langle d \rangle$

  the small world property is defined by

  $$\langle d \rangle \approx \frac{\ln{N}}{\ln{\langle k \rangle}} \tag{3.19}$$

• $\ln{N} \ll N$, average path length or the diameter depends logarithmically on the system size

• $\frac{1}{\ln{\langle k \rangle}}$ imply the denser the network, the smaller the distance

• in real networks, systematic corrections to eq.3.19

• 1D: $d_{max} \sim \langle d \rangle \sim N$
• 2D: $d_{max} \sim \langle d \rangle \sim N^{\frac{1}{2}}$
• 3D: $d_{max} \sim \langle d \rangle \sim N^{\frac{1}{3}}$
• 4D: $d_{max} \sim \langle d \rangle \sim N^{\frac{1}{d}}$

$N \approx 7 \times 10^9$, $\langle k \rangle \approx 10^3$

$\langle d \rangle \approx \frac{\ln{7\times10^9}}{\ln{10^3}} = 3.28$

(de Sola Pool, I., Kochen, M., 1978 [20])

Box 03.06. 19 Degrees of Separation¶

finite size scaling (Albert, R., 1999)

$\langle d \rangle \approx 0.35 + 0.89 \ln{N}$

$\langle d \rangle \approx 18.69$ (Lawrence, S., Giles, C.L., 1999)

19 degrees of separation

¶

Network	$N$	$L$	$\langle k \rangle$	$\langle d \rangle$	$d_{max}$	$\frac{\ln{N}}{\ln{\langle k \rangle}}$
Internet	192,244	609,066	6.34	6.98	26	6.58
WWW	325,729	1,497,134	4.60	11.27	93	8.31
Power Grid	4,941	6,594	2.67	18.99	46	8.66
Mobile-Phone Calls	36,595	91,826	2.51	11.72	39	11.42
Email	57,194	103,731	1.81	5.88	18	18.4
Science Collaboration	23,133	93,437	8.08	5.35	15	4.81
Actor Network	702,388	29,397,908	83.71	3.91	14	3.04
Citation Network	449,673	4,707,958	10.43	11.21	42	5.55
E. Coli Metabolism	1,039	5,802	5.58	2.98	8	4.04
Protein Interactions	2,018	2,930	2.90	5.61	14	7.14

Box 03.07. Six Degrees: Experimental Confirmation¶

Box 03.08. 19 Degrees of the WWW¶

03.09. Clustering Coefficient¶

clustering coefficient $C_i$, the density of the links in node $i$'s immediate neighborhood

expected number of links $L_i$

$$\langle\ L_i \rangle = p \frac{k_i(k_i-1)}{2} \tag{3.20}$$

local clustering coefficient:

$$\begin{align*} C_i &= \frac{2\langle L_i \rangle}{k_i(k_i - 1)} \\ &= p \\ &= \frac{\langle k \rangle}{N} \end{align*} \tag{3.21}$$

plot $\frac{\langle C \rangle}{\langle k \rangle}$ in fn of $N$

$\frac{\langle C \rangle}{\langle k \rangle}$ NOT decrease as $N^{-1}$

Box 03.09. Watts-Strogatz Model¶

• Small World Property average distance depends logarithmically on $N$
• High Clustering average clustering coef of real netw is higher than expected for a rand netw of similar $N$ and $L$

Watts-Strogatz model (small-world model) interpolate

• Regular lattice:
  • High clustering
  • Small-world property(-)
• Random netw:
  • Low clustering
  • Small-world property(+)

03.10. Summary: Real Networks are Not Random¶

03.16. Advanced Topic 3.E Fully Connected Regime¶

$(1-p)^{N_G} \approx (1-p)^N$ in the $N_G \simeq N$

the num of isolated nodes is

$$\begin{align*} I_N &= N (1-p)^N \\ &= N \Big(1 - \frac{N \cdot p}{N} \Big)^N \\& \approx Ne^{-Np} \end{align*} \tag{3.40}$$

for large $n$,
$(1 - \frac{x}{n})^n \approx e^{-x}$

only one node is disconnected

$I_N = 1$, eq.3.40, $Ne^{-Np} = 1$

$$p = \frac{\ln{N}}{N} \tag{3.41}$$

leads to eq.3.14 $\langle k \rangle = \ln{N}$

¶

¶

¶

¶

¶