Chapter 2

Random Graphs

In this chapter we describe some key concepts in graph theory. In Section 2.1 we
introduce graphs and random graphs, and look at four particular scaling features as
these graphs become large. (More scaling features are discussed in Chapter 1.) In
Section 2.2 we analyse the simplest random graph model, due to Erdős and Rényi,
where edges occur randomly and independently, and show that it exhibits a perco-
lation transition.
Random graphs are models for complex networks (randomness is often synony-
mous to complexity). They are inspired by real-world networks, and are used as
null-models. They play an important role in analysing and explaining the empirical
properties observed in real-world networks. They can also be used to make predic-
tions.

2.1 Graphs, random graphs, four scaling features

2.1.1 Graphs
A graph G = (V, E ) consists of a set of vertices V (also called nodes or sites) and a set
of edges E (also called links or bonds) connecting pairs of vertices. A graph is called
simple when there are no self-edges (= no edges between a vertex and itself) and no
multiple edges (= at most one edge between a pair of vertices). A graph that is not
simple is called a multi-graph. Edges are undirected. Graphs with directed edges
are called directed graphs. See Fig. 2.1.

s s s
s s
s s s s @@s s s s s s

Figure 2.1: Examples 1–3 are complete graphs. Examples 1–3 and 5 are simple graphs, ex-
amples 4 and 6 are multi-graphs. Examples 1 and 5 contain isolated vertices. Example 5 has
two clusters.

Not all pairs of vertices need to be connected by an edge. A graph that is simple
and has all pairs of vertices connected by an edge is called a complete graph. Some
vertices may have no edge at all. Such vertices are called isolated. A connected com-
ponent, which in the graph theory literature is also called a cluster, is any maximal

55
56 CHAPTER 2. RANDOM GRAPHS

subset of vertices that are connected by edges (= maximally connected component).

The size of a cluster is the number of vertices it contains. An isolated vertex is a clus-
ter of size 1. The degree of a vertex is the number of edges attached to it. An isolated
vertex has degree 0. A vertex with a loop has degree 2.
The degree sequence of a graph G is the vector

⃗
k = (k i )i ∈V (2.1)

with k i the degree of vertex i . The degree distribution is the probability distribution

fG = |V |−1 δk i ,
X
(2.2)
i ∈V

where |V | is the cardinality of V and δki is the point distribution concentrated at k i ,

i.e.,
δki (k) = 1{k=ki } , k ∈ N0 , (2.3)

with N0 the set of non-negative integers. Note that fG is a probability distribution

on N0 , whose weights

fG (k) = |V |−1 |{i ∈ V : k i = k}|, k ∈ N0 , (2.4)

represent the fraction of vertices with degree k. Therefore fG can also be interpreted
as the probability distribution of the degree of a vertex that is drawn randomly from
V.
A triple of distinct vertices i 1 , i 2 , i 3 forms a wedge when the edges i 1 i 2 and i 2 i 3
are present, and a triangle when the edges i 1 i 2 , i 2 i 3 and i 3 i 1 are present. The global
clustering coefficient of G is the ratio

∆G
CG = ∈ [0, 1], (2.5)
WG

where

∆G =
X X
1{i 1 i 2 ,i 2 i 3 ,i 3 i 1 are present} , WG = 1{i 1 i 2 ,i 2 i 3 are present} , (2.6)
i 1 ,i 2 ,i 3 ∈V i 1 ,i 2 ,i 3 ∈V

i.e., ∆G is 3! = 6 times the number of triangles in G and WG is 2! = 2 times the number

of wedges in G. This definition is sometimes referred to as the wedge-triangle global
clustering coefficient. (In Section 1.2.3 the notion of local clustering coefficient is in-
troduced, which is different but has a similar flavour, applied to the neighbourhood
of individual vertices.) A complete graph has global clustering coefficient 1 (when
n ≥ 3), a tree graph has global clustering coefficient 0.
The typical distance in G is the ratio
P
i , j ∈V : i ↔ j , i ̸= j d (i , j )
HG = P ∈ [1, ∞), (2.7)
i , j ∈V : i ↔ j , i ̸= j 1

where i ↔ j means that i and j are connected, and d (i , j ) denotes the graph dis-
tance between i and j (= the minimal number of edges in a path between i and j ).
In words, HG is the average distance between two vertices drawn uniformly from
all pairs of connected vertices. The complete graph has typical distance 1, a linear
graph has typical distance roughly one third of its length.
2.1. GRAPHS, RANDOM GRAPHS, FOUR SCALING FEATURES 57

2.1.2 Random graphs and scaling features

A random graph is a graph where the vertices and/or edges are chosen randomly.
There are many possible ways in which this can be done, and various different choices
have been made with the aim to model real-world networks of different types. Sev-
eral examples will be discussed during this course.
Since networks tend to grow, it is natural to consider sequences of random graphs

G = (G n )n∈N , (2.8)

where n denotes the number of vertices in G n . This is referred to as a random graph

process. We use the symbol P to denote the probability distribution of G and the
symbol E to denote expectation with respect to P, i.e., if Ωn is the set of graphs with
n vertices, then E(g (G n )) = G∈Ωn g (G)P(G n = G) for any function g : Ωn → R. In
P

what follows we give a precise mathematical definition of four scaling features of

random graph processes, following van der Hofstad [3, Chapter 1]:

(1) G is called sparse when

lim fG n (k) = f (k), k ∈ N0 , (2.9)

n→∞

for some non-random probability distribution f on N0 , where the above con-

vergence, depending on each model, will be established either in probability
or in distribution. Roughly speaking, sparse means that most vertices have a
degree that stays bounded, with degree frequencies stabilising, as n → ∞.

(2) G is called scale free with exponent τ when it is sparse and

log f (k)
lim =τ (2.10)
k→∞ log(1/k)

for some τ ∈ (1, ∞), i.e., f (k) = k −τ+o(1) as k → ∞. Roughly speaking, scale free
means that the graph “looks similar on all scales”.

(3) G is called highly clustered when

E(∆G n )
lim =C (2.11)
n→∞ E(WG n )

for some C ∈ (0, 1]. Roughly speaking, not highly clustered means that locally
the graph “looks like a tree”.

(4) G is called a small world when

lim P(HG n ≤ K log n) = 1 (2.12)

n→∞

for some K ∈ (0, ∞). If the latter holds with K log n replaced by an upper bound
that is o(log n), then G is called an ultra-small world. In such cases the upper
bound is often K log log n. Small world means that typical distances grow only
very slowly with the size of the graph (and are almost independent of the size).

[Begin intermezzo]
58 CHAPTER 2. RANDOM GRAPHS

In asymptotic analysis, three symbols are used frequently: o, O and Θ. The symbol
o stands for “is of smaller order than”: a n = o(b n ) when limn→∞ a n /b n = 0. The
symbol O stands for “is at most of the same order as": a n = O(b n ) when lim supn→∞
a n /b n < ∞. The symbol Θ stands for “is of the same order as”: a n = Θ(b n ) when
both a n = O(b n ) and b n = O(a n ). This is also written as a n ≍ b n .
[End intermezzo]

2.2 Erdős-Rényi random graph

The simplest example of a random graph is the Erdős-Rényi random graph. Here, ¡for¢
each n ∈ N, we consider the complete graph K n on n vertices, and for each of the n2
edges we decide to retain it with probability p ∈ (0, 1) and remove it with probabil-
ity 1 − p, independently for different edges. (The retained edges are called “open”,
the removed edges are called “closed”.) The resulting graph is a random subgraph
of K n , and is denoted by ERn (p). It was introduced in 1959 by the Hungarian math-
ematicians Paul Erdős and Alfred Rényi [2], and marked the beginning of random
graph theory. Chapter 3 describes algorithms to simulate ERn (p). See Fig. 2.2 for
two realizations of ER100 (1/200) and ER100 (3/200).

Figure 2.2: Two realizations of Erdős-Rényi random graphs with 100 vertices and edge prob-
abilities 1/200, respectively, 3/200. The three largest clusters are ordered by the darkness of
their edge colors (dark blue, blue, light blue). The remaining edges all have the lightest shade
(grey). Courtesy Remco van der Hofstad.

Homework 2.1 Find the distribution of the number of edges in ERn (p)? Compute its
mean and its variance, and explain why these are such that the distribution satisfies
the law of large numbers and the central limit theorem in the limit as n → ∞ (look
these up on Wikipedia; a proof is not requested). Hint: Use that the number of edges
is e Ye , where the sum runs over the n2 edges of the complete graph K n , and Ye =
P ¡ ¢

1{e is retained} are i.i.d. (= independent and identically distributed) random variables
taking the values 1 with probability p and 0 with probability 1 − p. Note that E(Ye ) =
P(e is retained) = p. □

The Erdős-Rényi random graph is not really suitable as a model of a real-world

network, for which typically neither the number of vertices is fixed nor the edges are
2.2. ERDŐS-RÉNYI RANDOM GRAPH 59

retained or removed independently. Yet, it captures a basic feature of a real-world

network: complexity.

2.2.1 Percolation transition

We follow the exposition in van der Hofstad [3, Chapter 4]. The Erdős-Rényi ran-
dom graph exhibits an interesting phenomenon: ERn (p) has a percolation transition
when we pick p = λ/n with λ ∈ (0, ∞) and let n → ∞. Namely, the largest cluster has
size

• Θ(log n) when λ < 1,

• Θ(n 2/3 ) when λ = 1,

• Θ(n) when λ > 1.

Thus, there is a critical value λc = 1 such that ERn (λ/n) consists of a large number of
small disconnected components when λ < λc (“subcritical regime”), but has a large
connected component containing a positive fraction of all the vertices when λ > λc
(“supercritical regime”). At λ = λc there is a percolation transition: the small clusters
coagulate into a large cluster. It can be shown that for λ > λc there is only one cluster
of size Θ(n), while all the other clusters are of size Θ(log n). It can also be shown that
for λ = λc there are multiple clusters of size Θ(n 2/3 ).
The fact that λc = 1 can be explained heuristically as follows. Pick any vertex
and call it ⋆. In the complete graph K n , ⋆ has n − 1 neighbours. In the Erdős-
Rényi random graph ERn (λ/n), ⋆ has a random number of neighbours, taking values
0, 1, . . . , n − 1. The average number of neighbours equals (n − 1)(λ/n), which tends to
λ as n → ∞. Thus, as we explore the graph starting from ⋆, we find that the average
number of vertices connected to ⋆ via a path of length d roughly equals λd (below
we make this more precise). As d becomes large, this average shrinks to 0 when
λ < 1 and grows to infinity when λ > 1. In the former case the cluster containing ⋆
apparently is small, in the latter case it apparently is large.
Before we provide more details, we make a brief digression into the mathematics
of branching processes.

[Begin intermezzo]
A branching process is a simple model for a population evolving over time. Sup-
pose that, in each generation, each individual in the population independently gives
birth to a random number of children, chosen according to a prescribed probabil-
ity distribution f called the offspring distribution, i.e., f (k) is the probability that
an individual has k children. Let Zn denote the number of individuals in the n-th
generation, where for convenience we pick Z0 = 1. Then Zn satisfies the recursion
relation
Zn
n ∈ N0 ,
X
Zn+1 = X i ,n , (2.13)
i =1

where (X i ,n )i ∈N,n∈N0 is an “array” of i.i.d. random variables with common distribu-

tion f . (X i ,n represents the number of children of individual i in generation n; the
sum in (2.13) counts the total number of children produced in generation n.) Let
X
m= k f (k) (2.14)
k∈N0
60 CHAPTER 2. RANDOM GRAPHS

denote the average number of children produced by an individual in each genera-

tion. One of the key results for branching processes is that if m ≤ 1, then the popu-
lation dies out with probability 1 (unless f = δ1 ), while if m > 1, then the population
has a strictly positive probability to survive forever. In fact, it turns out that the ex-
tinction probability
η = P(∃ n ∈ N : Zn = 0) (2.15)
is the smallest solution of the equation (see Fig. 2.3)
X k
η = G f (η), G f (x) = x f (k), x ∈ [0, 1]. (2.16)
k∈N0

A branching process is subcritical when m < 1, critical when m = 1, and supercritical

when m > 1. (The case f = δ1 is uninteresting and is excluded.)

G f (x)

f (0) s s
x
η

Figure 2.3: Plot of the generating function x 7→ G f (x) for the case where m = G ′f (1) > 1.

Exercise 2.1 Show that η = 0 if and only if f (0) = 0. □

Exercise 2.2 When the offspring distribution is given by

f (k) = (1 − p)1{k=0} + p1{k=2}

for some p ∈ (0, 1), we speak of binary branching. Compute G f (x), and show that
η = 1 when 0 < p ≤ 12 and η = (1 − p)/p when 21 < p < 1. □

[End intermezzo]

We are now ready to explain in more detail what drives the percolation transition
in the Erdős-Rényi random graph. Again consider the vertex ⋆, and paint it green.
Think of this as stage 0 of an exploration process, and put N0 = 1 to count the number
of vertices painted green at stage 0. Next, consider the vertices that are connected to
⋆. These vertices all lie at distance 1 from ⋆, and are painted green as well. Write N1
to denote their number, and think of N1 as counting the number of vertices painted
green at stage 1. Next, consider the vertices connected to the N1 vertices just painted
green, but exclude ⋆. These vertices all lie at distance 2 from ⋆, and are painted
green as well. Write N2 to denote their number, and think of N2 as counting the
number of vertices painted green at stage 2. Continue in this way, each time adding
green vertices that have not been painted green before. Note that the exploration
2.2. ERDŐS-RÉNYI RANDOM GRAPH 61

terminates after a finite number of stages, say M , when all the vertices in C ⋆ , the
cluster containing ⋆, have been painted green. We think of the random sequence

(Nd )dM=0 (2.17)

PM
as the sizes of the stages in the exploration process. Note that d =0 Nd = |C ⋆ |. For an
algorithm that explores the vertices of the Erdős-Rényi random graph, starting from
any given vertex ⋆, we refer the reader to [3, Chapter 4].
Unfortunately, (Nd )dM=0 is not easy to analyse in detail. This has two reasons: (1)
as the exploration proceeds, more and more vertices get painted green and so it gets
harder and harder to find unpainted vertices (this is called the depletion effect); (2)
vertices painted green at a given stage may be a neighbour of two or more vertices
painted green at the previous stage (this is called the overlap effect). Fortunately, as
n → ∞ both effects become negligible because the exploration process rarely creates
loops. In fact, it turns out that (Nd )dM=0 is close to a branching process when n is large.

Exercise 2.3 The distribution of N1 is BINOMIAL(n−1, p), the binomial distribution

with parameters (n − 1, p) given by
à !
n −1 k
f n−1,p (k) = P(N1 = k) = p (1 − p)n−1−k , k = 0, . . . , n − 1. (2.18)
k

Show that as n → ∞:
(a) E(N1 ) = p(n − 1) → λ and Var(N1 ) = p(1 − p)(n − 1) → λ.
(b) E(N2 ) = E([1 − (1 − p)N1 ](n − 1 − N1 )) → λ2 .
Hint: To compute E(N2 ), condition on N1 , compute the expected number of vertices
different from ⋆ that are connected to at least one of the N1 vertices that are connected
to ⋆, and average over N1 . In the limit as n → ∞ the resulting expression simplifies. □

Exercise 2.3 shows that, for large n, the random sequence (Nd )dM=0 is close to a branch-
ing process
(Ñd )d ∈N0 , (2.19)
at least as long as d does not become too large. The offspring distribution of (Ñd )d ∈N0
has mean λ. Therefore, according to the above intermezzo, we have limd →∞ Ñd = 0
with probability 1 when λ < 1 and limd →∞ Ñd = ∞ with positive probability when
λ > 1. Hence we see that ⋆ lies in a small cluster when λ < 1, but has a positive
probability of lying in a large cluster when λ > 1.

Homework 2.2 The probability that ⋆ has degree k equals

f n−1,p (k) = P (N1 = k).

Show that
lim f n−1,λ/n (k) = f λ (k), k ∈ N0 ,
n→∞

with f λ = POISSON(λ) the Poisson distribution with parameter λ given by

λk
f λ (k) = e −λ , k ∈ N0 . (2.20)
k!

Hint: Use that limn→∞ (1 − n −1 )n = e −1 . Show that the first moment of f λ equals λ
and the variance of f λ equals λ, which fits with Exercise 2.3(a). □
62 CHAPTER 2. RANDOM GRAPHS

In other words, the branching process (Ñd )d ∈N has offspring distribution f λ . Thus,
for large n, locally the Erdős-Rényi random graph looks like a random tree, namely,
the family tree of a branching process with offspring distribution f λ .

• λ > 1: As long as d = o(log n), the approximation Nd ≈ Ñd is good (recall

Homework 2.3) and we have E(Nd ) ≈ E(N˜d ) = λd . When d reaches values in
the range ≈ log n/ log λ, E(Nd ) reaches values in the range ≈ n (after which the
approximation Nd ≈ Ñd begins to break down). Hence, ⋆ has a strictly posi-
tive probability to lie in a cluster of size Θ(n).

• λ < 1: When d reaches values in the range ≈ log n/ log(1/λ), E(Nd ) reaches
values in the range ≈ 1/n.

The following comparison is valid for any n without approximation.

Exercise 2.4 Show that (Nd )d ∈N is stochastically smaller than (Ñd )d ∈N , i.e., there
exists a coupling of the two random sequences such that Nd ≤ Ñd for all d ∈ N with
probability 1. □

[Begin intermezzo]

A coupling of two random variables X 1 and X 2 is any pair of random variables

( X̄ 1 , X̄ 2 ) such that the marginal probability distributions of ( X̄ 1 , X̄ 2 ) coincide with
the probability distributions of X 1 and X 2 , respectively. Given X 1 and X 2 , there are
many ways to construct a coupling. For instance, if X 1 and X 2 have the same dis-
tribution, then the pair (X 1 , X 2 ) with independent components is a coupling, but
also the pairs (X 1 , X 1 ) and (X 2 , X 2 ) with identical components are. We say that X 1 is
stochastically smaller than X 2 when there exists a coupling such that X̄ 1 ≤ X̄ 2 with
probability 1.
An example is the following. Throw two coins. Let

X i = 1{coin i comes up head} , i = 1, 2.

Let p i = P(X i = 1), i = 1, 2, with p 1 ≤ p 2 . If we throw the coins independently, then

it may not be the case that X 1 ≤ X 2 . But we can throw the coins in a dependent
way as follows: (1) put X̄ 1 = 1 with probability p 1 and X̄ 1 = 0 with probability 1 − p 1 ;
(2) if X¯1 = 1, then put X̄ 2 = 1; (3) if X̄ 1 = 0, then put X̄ 2 = 1 with probability q =
(p 2 − p 1 )/(1 − p 1 ) and X̄ 2 = 0 with probability 1 − q. Since p 1 + (1 − p 1 )q = p 2 , this
way of producing two outcomes ( X̄ 1 , X̄ 2 ) results in X¯1 ≤ X̄ 2 , and it is easy to see that
the probability distribution of X¯i is the same as the probability distribution of X i ,
i = 1, 2.

[End intermezzo]

We will encounter coupling again in Chapter 7.

2.2.2 Scaling features

Since the degree distribution of ERn (λ/n) converges to f λ , the Erdős-Rényi random
graph is sparse. Since f λ has a thin tail, i.e., f λ (k) decays faster than polynomially in
k as k → ∞, the Erdős-Rényi random graph is not scale free.
2.2. ERDŐS-RÉNYI RANDOM GRAPH 63

Homework 2.3 Compute the average number of wedges E(WERn (λ/n) ) and the aver-
age number of triangles E(∆ERn (λ/n) ) in the Erdős-Rényi random graph. Show that

lim n −1 E(WERn (λ/n) ) = 21 λ2 , lim E(∆ERn (λ/n) ) = λ3 , (2.21)

n→∞ n→∞

which implies that C = 0 in (2.11). □

Consequently, the Erdős-Rényi random graph is not highly clustered.

The Erdős-Rényi random graph is a small world in the supercritical regime λ > 1.
In this regime, typical distances are at most K log n with K = 1/ log λ by the following
heuristic argument. As long as Nd is small compared to n, we know that Nd is close
to Ñd in distribution. Since E(Ñd ) = λd , it follows that Nd = Θ(n) when d ∼ K log n.
Since there are not more than n vertices, the exploration process from vertex ⋆ must
stop after at most ∼ K log n iterations. At criticality, for λ = 1, it is known that the
typical distance in the clusters of size Θ(n 2/3 ) is Θ(n 1/3 ) (Addario-Berry, Broutin and
Goldschmidt [1]). So the small world property fails at criticality.
Finally, it is possible to consider a generalised Erdős-Rényi random graph in which
the parameter λ is chosen randomly according to a distribution with a power law
tail. In this way the random graph can be made to be scale free and highly clustered
as well. In Chapter 4 we look at more realistic models to construct random graphs
with these properties.

Take home message: Random graphs serve as models of real-world networks.

The probability distribution according to which a random graph is drawn needs
to be chosen with care, depending on the empirical properties of the network it
aims to model. The Erdős-Rényi random graph is the simplest possible model.
It has a percolation transition, it is sparse (for p = λ/n) and small-world (when
supercritical), but it is not scale free and not highly clustered (for p = λ/n). Other
models are needed to capture the latter two properties.
Bibliography

[1] L. Addario-Berry, N. Broutin and C. Goldschmidt, Critical random graphs: lim-

iting constructions and distributional properties, Electron. J. Probab. 15 (2010)
741–775 (paper no. 25).

[2] P. Erdős and A. Rényi, On random graphs, I. Publ. Math. Debrecen 6 (1959) 290–
297.

[3] R. van der Hofstad, Random Graphs and Complex Networks, Volume I, mono-
graph in preparation. File can be downloaded from [Link]
nl/~rhofstad/

64