7  Random Graphs: Erdős–Rényi

Degrees

Clustering

What does this imply for our estimation of the global clustering coefficient from before? Well, we expect the global clustering coefficient to be about \(p\), and if \(p = c/(n-1)\), then \(p \rightarrow 0\) as \(n \to \infty\) for sparse \(G(n,p)\). We’ve given a heuristic argument showing that \(T \approx p\), and so our analysis predicts:

Sparse Erdős–Rényi graphs have vanishing clustering coefficients.

Figure 7.2 shows how the global clustering coefficient of a sparse Erdős–Rényi random graph decays as we increase \(n\).

Show code

c = 5
N = np.repeat(2**np.arange(5, 15), 10)

def global_clustering(n, c):
    G = nx.fast_gnp_random_graph(n, c/(n-1))
    return nx.transitivity(G)

T = [global_clustering(n, c) for n in N]

fig, ax = plt.subplots(1)

theory = ax.plot(N, c/(N-1), color = "black", label = "Estimate")

exp = ax.scatter(N, T, label = "Experiments", color = "steelblue", s = 10)
semil = ax.loglog()
labels = ax.set(xlabel = "Number of nodes", 
       ylabel = "Global clustering coefficient")
plt.show()

Although the estimate that the global clustering coefficient should be equal to \(p\) was somewhat informal, experimentally it works quite well.

Path Lengths

Given two nodes \(i\) and \(j\), what is the expected number of paths of length \(k\) between them?

Let \(R(k)\) denote the number of \(k\)-paths between \(i\) and \(j\). Let \(r(k) = \mathbb{E}[R(k)]\). Let’s estimate \(r(k)\).

First, we know that \(r(1) = p\). For higher values of \(k\), we’ll use the following idea: in order for there to be a path of length \(k\) from \(i\) to \(j\), there must be a node \(\ell\) such that:

• There exists a path from \(i\) to \(\ell\) of length \(k-1\). In expectation, there are \(r(k-1)\) of these.
• There exists a path from \(\ell\) to \(j\) of length \(1\). This happens with probability \(p\).

There are \(n-2\) possibilities for \(\ell\) (excluding \(i\) and \(j\)), and so we obtain the approximate relation

\[ r(k) \approx (n-2)r(k-1)p\;. \]

Proceeding inductively and approximating \(n-2 \approx n-1\) for \(n\) large, we have the relation

\[ r(k) \approx (n-1)^{k-1}p^{k-1}r(1) = c^{k-1}p \tag{7.1}\]

in the sparse ER model.

Using this result, let’s ask a new question:

What path length \(k\) do I need to allow to be confident that there’s a path of length \(k\) between nodes \(i\) and \(j\)?

Well, suppose we want there to be \(q\) paths. Then, we can solve \(q = c^{k-1}p\) for \(k\), which gives us:

\[ \begin{aligned} q &= c^{k-1}p \\ \log q &= (k-1)\log c + \log p \\ \log q &= (k-1)\log c + \log c - \log n \\ \frac{\log q + \log n}{\log c} &= k \end{aligned} \]

Here, we’ve also approximated \(\log (n-1) \approx \log n\) for \(n\) large. This result tells us that distances between nodes grow very slowly in \(G(n,p)\), roughly at the rate \(\log n\). This is very slow growth. For example, supposing that I want there to be at least one path in expectation (\(q = 1\)), I need to allow \(k = \frac{\log n}{\log c}\). The population of the world is about \(8\times 10^9\), and Newman estimates that an average individual knows around 1,000 other people; that is, \(c = 10^3\) in the world social network. The resulting value of \(k\) here is around 3.3. If on the other hand we wanted to be quite confident that a path exists, we might instead wish to require 1000000 paths, leading to a required path length of roughly 5.3.

More formal calculations regarding the diameter (length of longest shortest path) of the ER graph confirm that the diameter of the ER graph grows slowly as a function of \(n\).

A Caveat

If you spend some time looking at Equation 7.1, you might find yourself wondering:

Hey, what happens if \(c \leq 1\)?

Indeed, something very interesting happens here. Let’s assume \(c < 1\) (i.e. we’re ignoring the case \(c = 1\)), and estimate the expected number of paths between \(i\) and \(j\) of any length. Using Equation 7.1, we get

\[ \mathbb{E}\left[\sum_{k = 1}^{\infty} R(k)\right] = \sum_{k = 1}^\infty c^{k-1}p = \sum_{k = 0}^\infty c^kp = \frac{p}{1-c}\;. \]

\[ \frac{c}{(1-c)(n-1)}\rightarrow 0 \text{ as } n \to \infty\;. \]

So, this suggests that, if \(c < 1\), any two nodes are likely to be disconnected! On the other hand, if \(c > 1\), we’ve argued that we can make \(k\) large enough to have high probability of a path of length \(k\) between those nodes.

So, what’s special about \(c = 1\)? This question brings us to one of the first and most beautiful results in the theory of random graphs. To get there, let’s study in a bit more detail the sizes of the connected components of the ER graph.

The Subcritical Case

The mean of a \(\text{Poisson}(c)\) random variable is again \(c\). This implies that \(X_t\), the number of offspring in generation \(t\), satisfies \(\mathbb{E}[X_t] = c^{t}\). It follows that, when \(c < 1\), \(\mathbb{E}[T] = \frac{1}{1-c}\).

Now using Markov’s inequality, we obtain the following results:

So, the probability that the branching process hasn’t yet “died out” decays exponentially with timestep \(t\). In other words, the branching process becomes very likely to die out very quickly. What about the total number of nodes produced in the branching process? Again using Markov’s inequality, we find that

In particular, for \(a\) very large, we are guaranteed that \(\mathbb{P}(T > a)\) is very small.

import networkx as nx
import numpy as np

def component_size_of_node(n, c):
    G = nx.fast_gnp_random_graph(n, c/(n-1))
    return len(nx.node_connected_component(G, 1))

c = 0.8
sizes = [component_size_of_node(5000, c) for i in range(1000)]

out = f"""
Average over experiments is {np.mean(sizes):.2f}.\n
Theoretical expectation is {1/(1-c):.2f}.
"""

print(out)

Average over experiments is 4.82.

Theoretical expectation is 5.00.

The Giant Component

So far, we’ve argued using the branching process approximation that there is no giant component in the Erdős–Rényi model with \(c < 1\). The theory of branching processes also suggests to us that there could be a giant component when \(c > 1\).

Examples of phase transitions include freezing, in which a liquid undergoes a qualitative change into a solid in response to a small variation in temperature.

Figure 7.4 shows two sparse ER random graphs on either side of the \(c = 1\) transition. We observe an apparent change in qualitative behavior between the two cases.

Show code

import networkx as nx
from matplotlib import pyplot as plt

fig, axarr = plt.subplots(1, 2, figsize = (6, 3))

n = 500
c = [0.7, 1.3]

for i in range(2):
    G = nx.fast_gnp_random_graph(n, c[i]/(n-1))
    nx.draw(G, ax = axarr[i], node_size = 1)
    axarr[i].set(title = f"c = {c[i]}")

Size of the Giant Component

Let \(S\) be the size of the giant component in an Erdős–Rényi random graph, assuming there is one. Then, \(s = S/n\) is the probability that a randomly selected node is in the giant component. Let \(u = 1 - s\) be the probability that a given node is not in the giant component.

Let’s take a random node \(i\), and ask it the probability that it’s in the giant component. Well, one answer to that question is just “\(u\).” On the other hand, we can also answer that question by looking at \(i\)’s neighbors. If \(i\) is not in the giant component, then it can’t be connected to any node that is in the giant component. So, for each other node \(j\neq i\), it must be the case that either:

1. \(i\) is not connected to \(j\). This happens with probability \(1-p\).
2. \(i\) is connected to \(j\), but \(j\) is not in the giant component either. \(i\) is connected to \(j\) with probability \(p\), and \(j\) is not in the giant component with probability \(u\).

There are \(n-1\) nodes other than \(i\), and so the probability that \(i\) is not connected to any other node in the giant component is \((1 - p + pu)^{n-1}\). We therefore have the equation

\[ u = (1 - p + pu)^{n-1}\;. \]

Let’s take the righthand side and use \(p = c/(n-1)\): \[ \begin{aligned} u &= (1 - p(1-u))^{n-1} \\ &= \left(1 - \frac{c(1-u)}{n-1}\right)^{n-1}\;. \end{aligned} \] This is a good time to go back to precalculus and remember the limit definition of the function \(e^x\): \[ e^x = \lim_{n \rightarrow \infty}\left(1 + \frac{x}{n}\right)^{n}\;. \] Since we are allowing \(n\) to grow large in our application, we approximate

\[ u \approx e^{-c(1-u)}\;. \] So, now we have a description of the fraction of nodes that aren’t in the giant component. We can get a description of how many nodes are in the giant component by substituting \(s = 1-u\), after which we get the equation we’re really after: \[ s = 1- e^{-cs} \tag{7.2}\]

This equation doesn’t have a closed-form solution for \(s\), but we can still plot it and compare the result to simulations (Figure 7.5). Not bad!

Show code

import numpy as np
from matplotlib import pyplot as plt
import networkx as nx

# experiment: compute the size of the largest connected 
# component as a function of graph size for a range of mean degrees. 

def largest_component(n, p):
    G = nx.fast_gnp_random_graph(n, p)
    S = max(nx.connected_components(G), key=len)
    return len(S) / n

n = 50000
C = np.repeat(np.linspace(0.5, 1.5, 11), 10)
U = np.array([largest_component(n, c/(n-1)) for c in C])

# theory: prediction based on Newman 11.16

S = np.linspace(-.001, .6, 101)
C_theory = -np.log(1-S)/S

# plot the results to compare

plt.plot(C_theory, 
         S, 
         color = "black", 
         label = "Theoretical prediction", 
         zorder = -1, 
         linestyle = "--")

plt.scatter(C, 
            U, 
            label = "Experiment", 
            facecolor = "steelblue", 
            color = "white", 
            alpha = 0.8, 
            s = 150)

plt.gca().set(xlabel = "Mean degree", 
              ylabel = "Proportion of graph in largest component")

plt.legend()