8  Degree-Preserving Random Graphs

Sampling From Configuration Models

It’s surprisingly complicated to draw a sample from a configuration model random graph. We can draw approximate samples from the configuration model using the stub-matching algorithm.

In stub-matching, we create a list of “stubs,” or half-edges. Each node \(i\) with degree \(k_i\) appears in this list \(k_i\) times. We form edges by picking two stubs at a time out of the list and forming an edge between them. Let’s implement this stub-matching algorithm. Before we do, we’ll load in our favorite example graph and extract its degree sequence.

Show code

import networkx as nx
import numpy as np
from matplotlib import pyplot as plt
plt.style.use('seaborn-v0_8-whitegrid')
plot_kwargs = {"node_size" : 100, "edgecolors" : 'white', "node_color" : "steelblue", "width" : 0.5, "edge_color" : "darkgrey"}


G_Karate = nx.karate_club_graph()
deg_seq = [k for n, k in G_Karate.degree()]
fig, ax = plt.subplots(1, 1, figsize = (4, 3))
ax.scatter(np.arange(0, len(deg_seq)), np.sort(deg_seq),  s = 10)
labs = ax.set(xlabel = "Node (sorted by degree)", ylabel = "Degree", title = "Karate Club Degree Sequence")

Now we’ll implement an algorithm to perform stub-matching. First, we create the list of stubs. Each node appears a number of times equal to its degree.

stubs = np.repeat(np.arange(len(deg_seq)), deg_seq)
print(stubs)

[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1
  1  2  2  2  2  2  2  2  2  2  2  3  3  3  3  3  3  4  4  4  5  5  5  5
  6  6  6  6  7  7  7  7  8  8  8  8  8  9  9 10 10 10 11 12 12 13 13 13
 13 13 14 14 15 15 16 16 17 17 18 18 19 19 19 20 20 21 21 22 22 23 23 23
 23 23 24 24 24 25 25 25 26 26 27 27 27 27 28 28 28 29 29 29 29 30 30 30
 30 31 31 31 31 31 31 32 32 32 32 32 32 32 32 32 32 32 32 33 33 33 33 33
 33 33 33 33 33 33 33 33 33 33 33 33]

Now we need to take random pairs from this list of stubs. We could do this with a loop, but another way is to shuffle the list and then reshape it into a list of pairs:

mixed_stubs = np.random.permutation(stubs)
edge_list = mixed_stubs.reshape(len(mixed_stubs)//2, 2)

Now we can create a graph from our newly-constructed edge-list. Importantly, this graph might contain both self-loops and multi-edges, and so we need to use the nx.MultiGraph constructor.

G = nx.MultiGraph()
edges = G.add_edges_from(edge_list)

Here’s how our random graph compares to our original:

Show code

fig, axarr = plt.subplots(1, 2, figsize = (6, 3))
axarr[0].set(title = "Karate Club Graph")

pos = nx.spring_layout(G_Karate)

nx.draw(G_Karate, pos, ax = axarr[0], **plot_kwargs)

nx.draw(G, pos, ax = axarr[1], **plot_kwargs)
axarr[1].set(title = "Configuration Model Graph")

The stub-matching algorithm can produce multiedges and self-loops, which can cause the graph to not be simple. However, Bollobás (1980) proved that, when the graph is sparse, the expected number of multi-edges and self-loops does not grow with network size. One can, as a result, show these structures are rare, and can often be ignored in arguments. In practical terms, we often discard the self-loops and multi-edges when constructing the graph; this results in the degree sequence no longer being exactly preserved, but the effect is u sually small.

Fosdick et al. (2018) discuss the subtleties that arise due to whether we allow or disallow multiedges and self-loops and whether we choose to label stubs distinctly (as opposed to only labeling vertices). These choices result in different spaces of graphs from which we are sampling. If we want to sample a simple graph from a configuration model with exactly the specified degree sequence, stub-matching is no longer sufficient. Instead, we need to rely on edge-rewiring algorithms, which randomly swap edges between nodes of the graph to randomize the graph while ensuring that the degrees of nodes remain constant. NetworkX implements a version of such an algorithm. The user needs to specify how many rewiring steps should be performed.

G = nx.random_reference(G_Karate, connectivity = False, niter = 1000)

Here’s how this looks:

Show code

fig, axarr = plt.subplots(1, 2, figsize = (6, 3))
axarr[0].set(title = "Karate Club Graph")

nx.draw(G_Karate, pos, ax = axarr[0], **plot_kwargs)

nx.draw(G, pos, ax = axarr[1], **plot_kwargs)
axarr[1].set(title = "Configuration Model \nGraph (Rewiring)")

The Friendship Paradox

Suppose we model a social network of friends with degree-preserving random graph. How many friends does your friend have?

To see this, let’s calculate the average degree of a neighbor of a randomly chosen node using the edge-biased degree distribution.

\[ \begin{align} \sum_k k \frac{1}{\langle k \rangle}kp_k = \frac{1}{\langle k \rangle}\sum_k k^2 p_k\,. \end{align} \]

Let \(n\) be the total number of nodes and \(n_k\) be the number of nodes of degree \(k\).

Now we’ll simplify our expression with a reindexing trick. As written, we’ve indexed over node degrees \(k\), but we could choose to index over node labels \(i\) instead. Remembering that \(p_k = \frac{1}{n}n_k\), this gives: \[ \begin{align} \frac{1}{\langle k \rangle}\sum_k k^2 \frac{1}{n}n_k = \frac{1}{\langle k \rangle n}\sum_i k_i^2 = \frac{\langle k^2 \rangle}{\langle k \rangle}\,, \end{align} \tag{8.1}\]

Let’s compare this value to the expected degree of a randomly chosen node:

\[ \begin{aligned} \frac{\langle k^2 \rangle}{\langle k \rangle} - \langle k \rangle = \frac{1}{\langle k \rangle}\left(\langle k^2 \rangle - \langle k \rangle^2\right) = \frac{\sigma_k^2}{\langle k \rangle}\,, \end{aligned} \tag{8.2}\]

where \(\sigma_k^2 = \langle k^2 \rangle - \langle k \rangle^2\) is the empirical variance of the degree distribution. As we know, the variance of a random variable is 0 if and only the random variable is constant. In the context of degrees, this corresponds to a \(k\)-regular graph. So, unless the graph is \(k\)-regular, \(\sigma_k^2 > 0.\) Thus,

\[ \begin{align} \frac{\sigma_k^2}{\langle k \rangle} &> 0, \\ \Rightarrow \frac{\langle k^2 \rangle}{\langle k \rangle} - \langle k \rangle &> 0, \\ \Rightarrow \frac{\langle k^2 \rangle}{\langle k \rangle} &> \langle k \rangle \,. \end{align} \]

That is, the expected degree of a node’s neighbor (lefthand side) is greater than the expected node degree \(c\) … in other words, (in expectation), your friends have more friends than you do!

The intuition behind this idea is that a node with degree \(k\) appears as a neighbor to \(k\) other nodes, so high degree nodes are over-represented in the calculations.

The friendship paradox has some practical applications in network analysis and interventions. For example, to interrupt the spread of an illness with a limited number of vaccines, it’s useful to target high-degree nodes in social networks, as they are more likely to be infected and to infect others. But how to identify the high-degree nodes? The friendship paradox suggests a simple way: pick some people at random and ask them to recommend one of their friends. This is sometimes called acquaintance immunization and can be a relative effective strategy for vaccine distribution. See Rosenblatt et al. (2020) for some discussion of this and related strategies.

Let’s visualize the degree of each node in comparison to the average degree of its neighbors to get a feel for this result:

Show code

mean_degree = np.mean(deg_seq)


neighbor_degrees = list(nx.average_neighbor_degree(G_Karate).values())

fig, ax = plt.subplots(1, 1, figsize = (5, 4))
ax.scatter(deg_seq, neighbor_degrees, s = 10, alpha = 0.5)
ax.plot([0, 17], [0, 17], color = "grey", linestyle = "--", linewidth = 0.75)
t = ax.set(xlabel = "Node Degree", ylabel = "Mean degree of neighbors", title = "Friendship Paradox in the Karate Club Graph")

For most nodes (but not all), the mean degree of their neighbors is higher than their own degree. On average, the mean degree of a node in this graph is just half of the mean degree of that node’s neighbors.

We can verify Equation 8.1 by computing the appropriate quantities in two ways.

Let’s compare our computational result to the result expected by theory.