CS4423 - Networks

Prof. Götz Pfeiffer
School of Mathematics, Statistics and Applied Mathematics
NUI Galway

6. Power Laws and Scale-Free Graphs

Lecture 21: Power Laws

In [ ]:
import numpy as np
import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt

Degree Distribution

Recall degree distribution:

The degree distribution of an undirected graph $G = (X, E)$ is the function $k \mapsto p_k:= n_k/n$, where $n = |X|$ and $n_k$ is the number of nodes of degree $k$ (and thus $p_k$ is the probability that a random node $x \in X$ has degree $k$).

In an ensemble of graphs of order $n$, one sets $p_k:= \overline{n_k}/n$, where $\overline{n_k}$ is the expected value of the random variable $n_k$ over the ensemble of graphs.

In this sense, the degree distribution in a random $G(n, p)$ graph is binomial : $$ p_k = \binom{n-1}{k}p^k (1-p)^{n-1-k}, $$ or, in the limit $n \to \infty$ and $p \to 0$ with $np$ constant, it is a Poisson distribution: $$ p_k = e^{-z} \frac{z^k}{k!}, $$ where $z = np$.

A power law degree distribution is strikingly different: $$ p_k = c k^{-\gamma}, $$ for certain constants $c$ and $\gamma$. (Typically $2 \leq \gamma \leq 3$.)

In [ ]:
def binomial(n, k):
    prd, top, bot = 1, n, 1
    for i in range(k):
        prd = (prd * top) // bot
        top, bot = top - 1, bot + 1
    return prd
In [ ]:
def b_dist(n, p, k):
    return binomial(n, k) * p**k * (1-p)**(n-k)
In [ ]:
from math import exp, factorial
def p_dist(l, k):
    return exp(-l) * l**k / factorial(k)
In [ ]:
n, p = 1000, 0.015
mm = 50
l = p * (n-1)
bb = [b_dist(n-1, p, k) for k in range(mm)]
pp = [p_dist(l, k) for k in range(mm)]
In [ ]:
df = pd.DataFrame()
df['binom'] = bb
df['poisson'] = pp
df.plot()
In [ ]:
def power_dist(c, gamma, k):
    return c * k**(-gamma)
In [ ]:
c = 0.15
po1 = [power_dist(c, 1, k) for k in range(1,mm+1)]
po2 = [power_dist(c, 2, k) for k in range(1,mm+1)]
po3 = [power_dist(c, 3, k) for k in range(1,mm+1)]
In [ ]:
df['power1'] = po1
df['power2'] = po2
df['power3'] = po3
df.plot()
In [ ]:
df.plot(loglog=True)
In [ ]:
G = nx.read_pajek("c_elegans_undir.net")
G = nx.Graph(G)
In [ ]:
n, m = G.number_of_nodes(), G.number_of_edges()

A random graph R of same degree $n$ and size $m$.

In [ ]:
R = nx.gnm_random_graph(n, m)
hist = nx.degree_histogram(R)
hist = [(i, hist[i]) for i in range(len(hist)) if hist[i] > 0]
df = pd.DataFrame(hist)
df.plot.scatter(x = 0, y = 1)
In [ ]:
pd.DataFrame(nx.degree_histogram(G)).plot.bar()
In [ ]:
pd.DataFrame(nx.degree_histogram(R)).plot.bar()

A $(n, d, p)$-Watts-Strogatz graph has $n$ nodes and $dn$ edges

In [ ]:
d = m//n
p = 0.2
W = nx.watts_strogatz_graph(n, 2*d, p)
In [ ]:
W.number_of_nodes(), W.number_of_edges()
In [ ]:
hist = nx.degree_histogram(W)
hist = [(i, hist[i]) for i in range(len(hist)) if hist[i] > 0]
df = pd.DataFrame(hist)
df.plot.scatter(x = 0, y = 1)

Does the degree histogram of the worm brain network follow a power law degree distribution? Here is a standard plot and a loglog plot of it ...

In [ ]:
hist = nx.degree_histogram(G)
hist = [(i, hist[i]) for i in range(len(hist)) if hist[i] > 0]
df = pd.DataFrame(hist)
df.plot.scatter(x = 0, y = 1)
In [ ]:
df.plot.scatter(x = 0, y = 1, loglog=True)