A random graph is a probability distribution over graphs. In this set of lecture notes, we’ll begin our exploration of several random graphs.
Why should we even study random graphs? There are a few reasons!
Random graphs allow us to build our intuition and skills in the study of networks. In many simple random graphs, quantities of interest (clustering coefficients, diameters, etc) can be calculated with pencil and paper. This allows us to build mathematical insight into the structure of many real-world models, without the need for detailed simulations.
Many properties of even simple random graphs are still under investigation by research mathematicians. While some properties can be calculated simply, others require extremely sophisticated machinery in order to understand. There are many mathematicians who spend their careers studying random graphs, and their cousins, random matrices.
Suppose that you compute the global clustering coefficient (Definition 1.11) of a graph and find it to be \(0.31\). How do we interpret that? Is that high? Low? In this case, we should ask: compared to what? Random graphs allow us one way to make a comparison: that clustering coefficient is “high” if it’s larger than the clustering coefficient in a suitably chosen, comparable random graph. How to choose a comparable random graph is an important question, and the answer is not always clear!
In this way, random graphs often serve as the null hypothesis, in exactly the same way you might have heard of the null hypothesis for other kinds of statistical tests.
Many statistical algorithms for tasks like graph clustering, ranking, and prediction come from random graph models. The idea, generally speaking, is to imagine that we observe a graph, and then try to make the best educated guess possible about the model that generated that graph. This is classical statistical inference, and we’ll see a few examples later in the course.
The model of Erdős and Rényi (1960) is the simplest and most fundamental model of a random graph. Our primary interest in the ER model is for mathematical insight and null modeling. The ER model is mostly understood in its major mathematical properties, and it’s almost never used in statistical inference.
We can imagine visiting each possible pair of edges \((i,j)\) and flipping a coin with probability of heads \(p\). If heads, we add \((i,j) \in E\); otherwise, we don’t.
Recall that both local and global clustering coefficients were defined in terms of a ratio of realized triangles to possible triangles. Analyzing ratios using probability theory can get tricky, but we can get a pretty reliable picture of things by computing the expectations of the numerator and denominator separately.
Let’s take the global clustering coefficient (Definition 1.11). For this, we need to compute the total number of triangles, and the total number of wedges.
How many triangles are there? Well, there are \(\binom{n}{3}\) ways to choose 3 nodes from all the possibilities, and the probability that all three edges exist to form the triangle is \(p^3\). So, in expectation, there are \(\binom{n}{3}p^3\) triangles in the graph.
How many wedges are there? Well, each triple of nodes contains three possible wedges, and the probability of any given wedge existing is \(p^2\). So, the expected number of wedges is \(\binom{n}{3}p^2\). Our estimate for the expected clustering coefficient is that it should be about \(p\), although we have been fast and loose with several mathematical details to arrive at this conclusion.
We are very often interested in the sparse Erdős–Rényi model. Intuitively, the idea of sparsity is that there are not very many edges in comparison to the number of nodes.
A consequence of sparsity is that \(\mathbb{E}[K_i] = c\); i.e. the expected degree of a node in sparse \(G(n,p)\) is constant. When studying sparse \(G(n,p)\), we are almost always interested in the case \(n\rightarrow \infty\).
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\).
Sparse Erdős–Rényi graphs have vanishing clustering coefficients.
Figure 2.1 shows how the global clustering coefficient of a sparse Erdős–Rényi random graph decays as we increase \(n\). Although the estimate that the global clustering coefficient should be equal to \(p\) was somewhat informal, experimentally it works quite well.
import networkx as nx
from matplotlib import pyplot as plt
import numpy as np
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")
semil = ax.semilogx()
labels = ax.set(xlabel = "Number of nodes",
ylabel = "Global clustering coefficient")
plt.show()
A triangle is an example of a cycle of length \(3\).
You’ll prove a generalization of Theorem 2.1 in an upcoming homework problem.
Graphs in which cycles are very rare are often called locally tree-like. A tree is a graph without cycles; if cycles are very rare, then we can often use techniques that are normally guaranteed to only work on trees without running into (too much) trouble.
How far apart are two nodes in \(G(n,p)\)? Again, exactly computing the length of geodesic paths involves some challenging mathematical detail. However, we can get a big-picture view of the situation by asking a slightly different question:
Given two nodes \(i\) and \(j\), what is the expected number of paths of length \(k\) between them?
Call the number of \(k\)-paths between \(i\) and \(j\) \(R(k)\). 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 are \(n-2\) possibilities for \(\ell\) (excluding \(i\) and \(j\)), and so we obtain the approximate relation
\[ r(k) \approx (n-2)p r(k-1)\;. \]
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 \qquad(2.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 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, I’ve also approximated \(\log n-1 \approx \log n\) for \(n\) large.
So, 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}\). This is pretty short, actually! For example, 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. This seems a little high to me (maybe I’m antisocial), but the resulting value of \(k\) here is around 3.3.
In other words, this calculation suggests that, if the world were an ER network, it would be the case that any two individuals would be pretty likely to have at least one path between them of length no longer than \(4\).
More formal calculations regarding the diameter of the ER graph confirm that the diameter of the ER graph grows slowly as a function of \(n\), even in relatively sparse cases.
If you spend some time looking at Equation 2.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 2.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}\;. \]
If we now use Markov’s inequality, we find that the probability that there is a path of any length between nodes \(i\) and \(j\) is no larger than
\[ \frac{p}{1-c} = \frac{c}{(1-c)(n-1)}\rightarrow 0\;. \]
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.
We’re now going to ask ourselves about the size of a “typical” component in the Erdős–Rényi model. In particular, we’re going to be interested in whether there exists a component that fills up “most” of the graph, or whether components tend to be vanishingly small in relation to the overall graph size.
Our first tool for thinking about this question is the branching process approximation. Informally, a branching process is a process of random generational growth. We’ll get to a formal mathematical definition in a moment, but the easiest way to get insight is to look at a diagram:
We start with a single entity, \(X_0\). Then, \(X_0\) has a random number of “offspring”: \(X_1\) in total. Then, each of those \(X_1\) offspring has some offspring of their own; the total number of these offspring is \(X_2\). The process continues infinitely, although there is always a chance that at some point no more offspring are produced. In this case, we often say that the process “dies out.”
Some of this exposition in this section draws on these notes by David Aldous.
Technically, this is a Galton-Watson branching process, named after the two authors who first proposed it (Watson and Galton 1875).
History note: Galton, one of the founders of modern statistics, was a eugenicist. The cited paper is explicit about its eugenicist motivation: the guiding question was about whether certain family names associated with well-to-do aristocrats were giving way to less elite surnames.
Branching processes create trees – graphs without cycles. The reason that branching processes are helpful when thinking about Erdős–Rényi models is that cycles are rare in Erdős–Rényi random graphs. So, if we can understand the behavior of branching processes, then we can learn something about the Erdős–Rényi random graph as well.
Here’s the particular form of the branching process approximation that we will use:
The idea behind this approximation is:
The mean of a \(\text{Poisson}(c)\) random variable is again \(c\). As you’ll show in homework, 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.
In particular, for \(a\) very large, we are guaranteed that \(\mathbb{P}(T > a)\) is very small.
Summing up, when \(c < 1\), the GW branching process dies out quickly and contains a relatively small number of nodes: \(\frac{1}{1-c}\) in expectation.
If we now translate back to the Erdős–Rényi random graph, the branching process approximation now suggests the following heuristic:
Let’s check this experimentally. The following code block computes the size of the component in an ER graph containing a random node, and averages the result across many realizations. The experimental result is quite close to the theoretical prediction.
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 5.45.
Theoretical expectation is 5.00.Note that the expected (and realized) component size is very small, even though the graph contains 5,000 nodes!
For this reason, we say that subcritical ER contains only small connected components, in the sense that each component contains approximately 0% of the graph as \(n\) grows large.
This explains our result from earlier about path lengths. The probability that any two nodes have a path between them is the same as the probability that they are on the same connected component. But if every connected component is small, then the probability that two nodes occupy the same one is vanishes.
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\).
Using our correspondence between components of the ER model and branching processes, this suggests that, if we pick a random node, the component it is in has the potential to be very large. In fact (and this requires some advanced probability to prove formally), when \(c > 1\), there is a giant component. This is our first example of a phase transition.
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 2.2 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.
import networkx as nx
from matplotlib import pyplot as plt
fig, axarr = plt.subplots(1, 2)
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]}")
Perhaps surprisingly, while it’s difficult to prove that there is a giant component, it’s not hard at all to estimate its size.
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:
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} \qquad(2.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 2.3). Not bad!
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")
plt.scatter(C,
U,
label = "Experiment")
plt.gca().set(xlabel = "Mean degree",
ylabel = "Proportion of graph in largest component")
plt.legend()