Generate a random graph with geometrical degree distribution

I'm working on graph generation, trying to implement the RT-nested-Smallworld network model described in this paper.

We are talking about generating an undirected graph in a slightly different way than what the Watts-Strogatz model does.

One of the very first steps of the algorithm is


instead of selecting links to connect most immediate $\langle k \rangle / 2$ neighbors to form a regular lattice, our model selects a
number $k$ of links at random from a local neighborhood $N_{d_0}$ with
the distance threshold of $d_0$, where $k$ comes from a geometric
distribution. The local neighborhood is defined as the group of
close-by nodes with mutual node number difference less than the
threshold $d_0$, that is $N^{(i)}_{d_0} = \{j; |j-i| < d_0\}$, for
node $i$. It is worth noting that our model adopts a geometric
distribution with the expectation $\langle k \rangle$ of for the
initial node degree settings (i.e, for the link selection).

In other words, each node with index $i$ should have a (possibly different) random degree $k$, obtained by linking it with nodes with an index-distance $d_0$.

First of all, I need to choose the parameter $p$ to generate the geometric distribution. If the average is $\langle k \rangle$, I choose $p = 1/\langle k \rangle$.

However, picking $n$ node degrees from a geometric distribution may not result in a feasible graph of $n$ nodes.

Moreover, Since this is an undirected graph we are talking about, going through each node and creating a random number $k$ of links will most likely not produce the desire average degree. E.g. during the ith iteration, the node i may already have more than $k$ links, created by the previous iterations of nodes randomly linking to it.

I tried to implement my own algorithm to distribute the node degrees as close as possible to the distribution outcome. Pseudocode

```
k_values = n values from the geometric distribution with p = 1/
for each node in [0, n)
if degree(node) < k_values[node]

You can use the configuration model for this. Create a "stub" array where each of the $n$ vertices appears in the array $k_i \sim \text{Geom}(p)$ times. Shuffle the array and then treat each adjacent pair in the array as an edge in the graph. Here's some python code to illustrate.

from numpy.random.mtrand import geometric
from random import shuffle
from _collections import defaultdict

if __name__ == '__main__':
    # Number of vertices
    n = 1000

    # Geometric distribution probability parameter
    p = 0.5

    stubs = []
    for i in xrange(0, n):
        # Sample the degree from the geometric distribution
        degree = geometric(p) 
        # Insert into the stubs array the current vertex label degree times
        stubs += [i] * degree

    # Shuffle the values
    shuffle(stubs)

    # Build the graph
    G = {}
    for i in xrange(0, n):
        G[i] = []

    for i in xrange(1, len(stubs), 2):
        G[stubs[i]].append(stubs[i-1])
        G[stubs[i-1]].append(stubs[i])

    # Recover the degree distribution
    degrees = { i : len(neighbors) for i, neighbors in G.items() }

    dist = defaultdict(int)
    for (vertex, degree) in degrees.items():
        dist[degree] += 1

    print("Degree, empirical, theoretical")
    for (degree, freq) in dist.items():
        print("%d %f %f" % (degree, freq / float(n),  pow((1 - p), degree - 1) * p ))

Sample output:

Degree, empirical, theoretical
1 0.496000 0.500000
2 0.254000 0.250000
3 0.128000 0.125000
4 0.071000 0.062500
5 0.023000 0.031250
6 0.018000 0.015625
7 0.005000 0.007812
8 0.003000 0.003906
9 0.002000 0.001953

For more detailed description of the the configuration model, see Section 13.2 p. 435 of Networks by Newman.

StackExchange Computer Science Q#42156, answer score: 3