Complex-Network Modelling and Inference

Lecture 9: Random Graphs: Erdos-Renyi random graphs

Matthew Roughan
<[Link]@[Link]>
[Link]
Network_Modelling/

School of Mathematical Sciences,

University of Adelaide

November 5, 2018
 Section 1

Random Graphs

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 2 / 26
 Why?

We often need graphs to use in simulations

I because we aren’t clever enough to do analysis of layers of network
protocols on top of a graph
I e.g., simulations of communications networks
We need statistical ensembles of graphs to test ideas
I and there is only 1 real graph
I e.g., to generate confidence intervals on results
Random graphs can let us test hypotheses
I postulate a particular type of random graph as a model
I look at its features
Often want to understand graph behaviour as it gets larger than any
examples we have
I e.g., how will my algorithm work in the future if the network gets much
bigger?

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 3 / 26
 The idea at the root
We start with the idea that there is an ensemble of graphs
I e.g., Gn = {all graphs with n nodes}
I e.g., Gn,k = {all graphs with n nodes and k edges }
I but these are usually VERY VERY big
Then we apply a probability measure to the ensemble

P(G ), ∀G ∈ Gn
But note that
I P(G ) might be too small to calculate
I P(G ) may be too computationally complex to calculate
I Even if P(G ) is easy, we don’t want to use it directly
F e.g., even if we knew P(G ) = const, we don’t want to search through
all possible graphs to get “the one”
So we need a method for constructing graphs that match a given
probability distribution, or usually that match some observed features
of our graph(s) of interest

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 4 / 26
 Section 2

Gilbert-Erdős-Rényi random graph

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 5 / 26
 Gilbert-Erdős-Rényi random graph [Gil59, ER60]

G (n, p)

Take n = |N| nodes

connect them at random
I for each pair of nodes flip a (biased) coin
I if it is heads connect them
nodes are adjacent with probability p
I number of edges will be binomial as we have n(n − 1)/2 iid Bernoulli
trials, so
 
n(n − 1)/2 k
prob(|E | = k) = p (1 − p)n(n−1)/2−k .
k

all graphs with n nodes, and k edges have equal probability

P(G |k edges) = 1/|Gn,k | = const

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 6 / 26
 Gilbert-Erdős-Rényi random graph features

Average number of links e = |E |

 
n
E [e] = pn(n − 1)/2 = p .
2

Degree distribution is also binomial

 
n−1 k
pk = p (1 − p)n−1−k .
k

critical threshold np = 1
I As p or n increases, the graphs become more and more likely to be
connected

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 7 / 26
 Limits of the Binomial distribution: I

Binomial  
n k
pk = p (1 − p)n−k .
k
Take limit as n → ∞, the Binomial distribution approaches a “Normal”
distribution N (np, np(1 − p)), i.e,
mean is µ = np
variance is σ 2 = np(1 − p)
distribution is Gaussian, i.e.,
1 2 /2σ 2
p(x) ' √ e −(x−µ) .
2πσ 2

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 8 / 26
 Limits of the Binomial distribution: I

Proof: by the Central Limit Theorem which states: take sum of n iid
random variables with finite variance
n
X
Sn = Xn ,
i=1

then in the limit as n → ∞

Sn − nµ d
Zn = √ → N (0, 1),
σ n
d
where → means convergence in distribution. A Binomial distribution is the
sum of n iid Bernoulli random variates to the result is immediate.

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 9 / 26
 Limits of the Binomial distribution: II

Binomial  
n k
pk = p (1 − p)n−k .
k
Take limit as n → ∞, such that np = λ is kept constant. The Binomial
converges to the Poisson distribution:

λk e −λ
pk = .
k!

mean is λ = np
variance is σ 2 = λ = np

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 10 / 26
 Limits of the Binomial distribution: II

Proof: np = λ, so p = λ/n → 0

n!
pk = p k (1 − p)n−k
k!(n − k)!
n!
= p k (1 − λ/n)−k (1 − λ/n)n
k!(n − k)!
n!
' p k 1 exp(−λ)
k!(n − k)!
n! λk
' exp(−λ)
(n − k)!nk k!
λk
' exp(−λ)
k!

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 11 / 26
 Erdős-Rény random graph features

critical piece of information is np = λ and how this behaves as n increases

node degree distribution is approximately Poisson

λk
 
n−1 k
pk = p (1 − p)n−1−k ' exp(−λ)
k k!

average number of links per node is (n − 1)p ' λ

I for λ < 1, average number of links per node is < 1
I for λ > 1, average number of links per node is > 1
probability degree 0 is p0 = exp(−λ)

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 12 / 26
 Connectivity

Take case that n → ∞ with np = λ fixed.

Chance that two nodes are adjacent is p → 0.
What is the chance that they are connected?

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 13 / 26
 Connectivity

What is the chance two nodes are connected by a length 2 path?

prob{i, j are connected by a length 2 path}

= 1 − prob{no length 2 path exists from i to j}
Y
= 1− prob{path i − k − j doesn’t exist}
k6=i,j
Y
= 1− (1 − prob{path i − k − j does exist})
k6=i,j

= 1 − (1 − p 2 )n−2
= 1 − (1 − (λ/n)2 )n−2
→ 0

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 14 / 26
 Connectivity

Some crude approximations

prob{i, j are connected by a length 1 path} = p

prob{i, j are connected by a length 2 path} ' (n − 2)p 2
prob{i, j are connected by a length 3 path} ' (n − 2)(n − 3)p 3
..
.
prob{i, j are connected by a length k path} ' nk−1 p k = λk /n

Sum over all possible path lengths and we get

prob{a path exists} ' (λ + λ2 + · · · + λn−1 )/n

In the limit as n → ∞ the properties of this depend on whether λ is larger

than, or smaller than 1.

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 15 / 26
 Connectivity

λ<1

prob{a path exists} ' (λ + λ2 + · · · + λn−1 )/n

n−1
X
' λi /n
i=1
λn − λ
 
' /n
λ−1
→ 0

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 16 / 26
 Connectivity

λ=1

prob{a path exists} ' (λ + λ2 + · · · + λn−1 )/n

n−1
'
n
→ 1

λ>1

prob{a path exists} ' (λ + λ2 + · · · + λn−1 )/n

λn−1
>
n
→ ∞

(though obviously a real probability can’t go to ∞)

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 17 / 26
 Gilbert-Erdős-Rényi random graph features

critical piece threshold for np = λ

np < 1: the size of the largest connected component grows as
O(log n)
np = 1: the size of the largest connected component grows as
O(n2/3 )
np > 1: the largest connected component will have O(n) nodes, and
the next largest component will contain no more than O(log n) nodes.

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 18 / 26
 Gilbert-Erdős-Rényi random graph features

Clustering
global measure of whether nodes tend to cluster

c = 3t1 /t2 ,

local measure of how close a node and its neigbours are to being a
clique
|{(j, k) ∈ E |j, k ∈ Ni }|
ci = ,
ki (ki − 1)/2
where Ni is the neigbourhood of i, and ki = |Ni |.

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 19 / 26
 Global clustering

c = 3t1 /t2 ,
where

t1 = number of triangles
t2 = number of connected triples

If three nodes are connected, they form a triangle if there is a third

link.
probability of a triangle conditional on the other two links is p.
in the limit as n → ∞ where np = const, the global clustering

c →0

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 20 / 26
 Local clustering

|{(j, k) ∈ E |j, k ∈ Ni }|
ci = ,
ki (ki − 1)/2
where Ni is the neigbourhood of i, and ki = |Ni |.
Conditional on k neighbours, there are k(k − 1)/2 possible other links.
Each exists with probability p
On average p[k(k − 1)/2] of these exists
So as n → ∞
pk(k − 1)/2
E [ci ] =
k(k − 1)/2
= p
→ 0

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 21 / 26
 Gilbert-Erdős-Rényi random graph features

clustering: Gilbert-Erdős-Rényi RGs don’t cluster well

I intuitively the degree of nodes remains roughly the same
I more choices for destinations of links
I so “neighbours” become less densely adjacent

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 22 / 26
 Gilbert-Erdős-Rényi Mark II

Take n = |N| nodes

connect them with m edges, randomly assigned
m
nodes are adjacent with probability p = n(n−1)/2
This is really the Erdős-Rényi graph
in limit pn2 → ∞ the two types of Gilbert-Erdős-Rényi graphs have
similar properties.

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 23 / 26
 Parameter estimation

Whenever we have a model we should ask

I how can I estimate its parameters?
I what data would I need to do so?
So parameter estimation (formally part of statistics) should also be
part of any modelling toolkit

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 24 / 26
 Parameter estimation for Gilbert-Erdős-Rényi

The number of edges is a binomial

|E | ∼ Bin (|N|(|N| − 1)/2, p)

Sufficient statistics for estimating parameters are |E | and |N|
There are numerous estimators for the parameters of Binomial
distributions
I e.g., MLE (Maximum Likelihood Estimator)

2|E |
p̂ =
|N|(|N| − 1)
I Also many ways to compute confidence intervals, etc.

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 25 / 26
 Further reading I

P. Erdős and A. Rényi, On the evolution of random graphs, Publications of the

Mathematical Institute of the Hungarian Academy of Sciences 5 (1960), 17–61.

E.N. Gilbert, Random graphs, Annals of Mathematical Statistics 30 (1959),

1441–1144.

Matthew Roughan (School of Mathematical Sciences, UniversityCNMI

of Adelaide) November 5, 2018 26 / 26