Prof. Götz Pfeiffer

School of Mathematics, Statistics and Applied Mathematics

NUI Galway

In [ ]:

```
import numpy as np
import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
```

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 ...

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 [ ]:

```
```