CS4423 - Networks

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

6. Power Laws and Scale-Free Graphs

Lecture 22: Configuration Model

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

The Configuration Model

In principle, random graph can be generated in such a way that they have a prescribed degree sequence.

Idea: Choose numbers $d_i$, $i \in X$, so that $\sum d_i = 2m$ is an even number.

Then regard each degree $d_i$ as $d_i$ stubs (half-edges) attached to node $i$.

Compute a random matching of pairs of stubs and build a graph on $X$ with those (full) edges.

Example. Suppose that $X = \{1, 2, 3, 4, 5\}$ and that we want those nodes to have degrees $d_1 = 3$, $d_2 = 2$ and $d_3 = d_4 = d_5 = 1$.

This gives a list of stubs $(1, 1, 1, 2, 2, 3, 4, 5)$ where each node $i$ appears as often as its degree $d_i$ requires.

A random shuffle of that list is $(1, 3, 4, 1, 2, 1, 5, 2)$.

One way to construct a matching is to simply cut this list in half and match entries of the first half with corresponsing entries in the second half. $$ \begin{array}{cccc} 1 & 3 & 4 & 1\\ 2 & 1 & 5 & 2 \end{array} $$ Note that $\sum d_i = 8 = 2m$ yields $m = 4$ edges ...

A Quick Implementation

In [ ]:
degrees = [3, 2, 1, 1, 1]

Recall that, in Python, list addresses start at $0$, and networkx default node names do likewise. Let's adopt this convention here.

Now entry $3$ in position $0$ of the list degrees stands for $3$ entries $0$ in the list of stubs, to be constructed. Entry $2$ in position $1$ stands for $2$ entries $1$ in the list of stubs and so on. In general, entry $d$ in position $i$ stands for $d$ entries $i$ in the list of stubs.

Python's list arithmetic (using m * a for m repetitions of a list a and a + b for the concatenation of lists a and b) can be used to quickly convert a degree sequence into a list of stubs as follows.

In [ ]:
stubs = [degrees[i] * [i] for i in range(len(degrees))]
stubs
In [ ]:
stubs = sum(stubs, [])
stubs

Let's call this process the stubs list of a list of integers and wrap it into a python function

In [ ]:
def stubs_list(a):
    return sum([a[i] * [i] for i in range(len(a))], [])
In [ ]:
stubs_list(degrees)

How to randomly shuffle this list? The wikipedia page on random permutations recommends a simple algorithm for shuffling the elements of a list a in place.

In [ ]:
from random import randint
def knuth_shuffle(a):
    l = len(a)-1
    for k in range(l):
        j = randint(k, l)
        a[j], a[k] = a[k], a[j]
In [ ]:
a = [1,2,3]
knuth_shuffle(a)
a

Let's test whether this shuffle produces uniformly random outcomes ...

In [ ]:
shuffles = {}
for i in range(1000):
    a = [1,2,3]
    knuth_shuffle(a)
    key = tuple(a)
    shuffles[key] = shuffles.get(key, 0) + 1
    
print(shuffles)

But python's random module already contains a function shuffle which does exactly this.

In [ ]:
from random import shuffle
In [ ]:
a = [1,2,3]
shuffle(a)
a

Let's test whether this shuffle produces uniformly random outcomes ...

In [ ]:
shuffles = {}
for i in range(1000):
    a = [1,2,3]
    shuffle(a)
    key = tuple(a)
    shuffles[key] = shuffles.get(key, 0) + 1
    
print(shuffles)

So we shuffle the stubs ...

In [ ]:
shuffle(stubs)
stubs

Then we match pairs, by cutting the list of stubs into halves and transposing the resulting array of 2 rows ...

In [ ]:
m = len(stubs) // 2
In [ ]:
edges = [stubs[:m], stubs[m:]]
edges
In [ ]:
edges = list(zip(*edges))
edges
In [ ]:
G = nx.Graph(edges)
In [ ]:
G.number_of_edges()
In [ ]:
nx.draw(G, with_labels=True, node_color='y')
In [ ]:
G.edges()

All in all, a configuration model can be built as follows.

In [ ]:
def configuration(degrees):
    m = sum(degrees) // 2  # should check if sum(degs) is even ...
    stubs = stubs_list(degrees)
    shuffle(stubs)
    edges = list(zip(stubs[:m], stubs[m:]))
    return nx.Graph(edges)
In [ ]:
G = configuration([3,2,1,1,1])
nx.draw(G, with_labels=True, node_color='y')
print(G.edges())

Now create a power degree distribution ... and generate a graph. Use $\gamma = 2$, since I know that $\zeta(2) = \pi^2/6$ ...

In [ ]:
from math import pi
gamma = 2
c = 6/pi/pi
p = [0] + [c * k**(-gamma) for k in range(1,35)]
print(p, sum(p))

Note how $p_0 = 0$ was explicitly prepended to the list p. Turn this now into a degree histogram on, say, $n = 50$ nodes.

In [ ]:
d = [int(50 * x) for x in p]
print(d)
print(sum(d))

Then recover the degree sequence from the histogram. Incidently, this works exactly as the transformation of the degree sequence above into a list of stubs (why?).

In [ ]:
print(stubs_list(d))
In [ ]:
G = configuration(stubs_list(d))
In [ ]:
G.edges()
In [ ]:
nx.draw(G, with_labels=True, node_color='y')
In [ ]:
nx.degree_histogram(G)

Try again ... This time with $\gamma= 2.5$, an explict value of $c = 2.5$, and $p[1]$ corrected so that $\sum p_k = 1$.

In [ ]:
gamma = 2.5
c = 2.5
p = [0] + [c * k**(-gamma) for k in range(1,35)]
p[1] = p[1] - (sum(p) - 1)
print(p)
print(sum(p))

Lift the degree numbers by $1/2$ so that they are rounded, rather than cut off when converted into integers. Also reduce number of nodes to $25$ for better drawings ...

In [ ]:
d = [int(25 * x + 0.5) for x in p]
print(d)
print(sum(d))
In [ ]:
print(stubs_list(d))
In [ ]:
G = configuration(stubs_list(d))
In [ ]:
G.edges()
In [ ]:
nx.draw(G, with_labels=True, node_color='y')
In [ ]:
nx.degree_histogram(G)

In networkx, configuration models can be generated with the function nx.configuration_model.

In [ ]:
G = nx.configuration_model(degrees)
nx.draw(G, with_labels=True, node_color='m')
In [ ]: