Network Models I.: Random
Networks & Small Worlds
IV124
Josef Spurný & Eva Výtvarová
Faculty of Informatics, Masaryk University
March 17, 2023
Random Graphs
Random Graph Model
Why model a random graph:
Properties can be mathematically derived
Useful for comparison with a real network:
What are the differences?
What does it tell us about the network?
Erdös-Rényi random graph model:
G(N, L) model, where L is a number of links randomly placed
among N nodes (proposed by Erdös and Rényi)
G(N, p), where N is the number of nodes and p is the probability
of connection between two nodes (more commonly used, but
actually proposed by Edgar Gilbert in 1959)
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 2 / 33
Random Graphs
Erdös-Rényi Model: Properties
A probability, that a random network has exactly |E| edges, is defined
by binomial distribution:
P(|E|) = Emax
|E| p|E|(1 − p)Emax−|E|
where Emax = N(N − 1)/2 is the maximum number of edges
A probability that a randomly selected node has a degree k:
Binomial distribution: P(k) = N−1
k pk(1 − p)N−1−k
N−1
k selection of k nodes
pk
: probability of k edges forming
(1 − p)N−1−k
: absence of remaining edges
k = p(N − 1)
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 3 / 33
Random Graphs
Erdös-Rényi Model: CC
Clustering coefficient
Ci = Li
ki(ki−1)
substituting Li with pki(ki−1)
2 – probability of a link between
neighbors
hence Ci = pki(ki−1)
ki(ki−1) = p
For real sparse networks, C is indeed very small.
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 4 / 33
Random Graphs
Erdös-Rényi Model: Average Path Length
Derivation
consider a network with a given k
on average, a node has k
d
neighbors at a distance of d
thus, the number of nodes at a distance of d is N(d) = k
d+1
−1
k−1
but N(d) ≤ N, so k
dmax
≈ N and dmax = log(N)
log(k)
for most networks, a good approximation for the average path
length is d ≈ ln(N)
ln(k)
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 5 / 33
Random Graphs
Erdös-Rényi Model: Average Path Length
δ = k = average degree
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 6 / 33
Random Graphs
Gephi demo: Random Graphs
...
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 7 / 33
Random Graphs
Netlogo demo: Random Graphs
...
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 8 / 33
Giant Component
Giant Component
NG = size of the largest component
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 9 / 33
Giant Component
Giant Component
Subcritical regime k < 1
no giant component
largest clusters NG ≈ ln N
clusters are trees of comparable size, there is no "winner"
clusters grow much slower than network, hence NG/N → 0 as
N → ∞
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 10 / 33
Giant Component
Giant Component
Critical point k = 1
no giant component, numerous small components
largest clusters are typically much larger than in subcritical
regime, NG ≈ N2/3
still, the largest cluster connects only an insignificant fraction of
all nodes
clusters may contain loops
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 11 / 33
Giant Component
Giant Component
Supercritical regime k > 1
one giant component
relevant to most real-world systems
largest clusters NG ≈ (p − pc)N, where pc is 1
N
small clusters are trees (isolated vertices)
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 12 / 33
Giant Component
Giant Component
Fully connected regime k ≥ ln N
one giant component
giant component absorbs all nodes and clusters, hence NG = N
(no isolated nodes)
yet the network is still relatively sparse
we receive complete graph only when k = N − 1
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 13 / 33
Giant Component
Giant Component Evolution
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 14 / 33
Giant Component
Netlogo demo: Component
...
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 15 / 33
Giant Component
Giant Component: Resistance to Node Failure
ER(2000, 0.015)
We may need to remove up to 70% nodes before network partitions.
Removing 95% nodes, half of the remaining are still connected
through a path.
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 16 / 33
Small Worlds
Strength of Weak Links1
Research question: How do people seek a new job?
Hypothesis: Your family would help you
Study results: Most commonly, a friend of a friend will give you a
good tip
1
Granovetter, M. S. (1973). The strength of weak ties.
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 17 / 33
Small Worlds
Small World Problem2
What is the probability that two randomly selected people will know
each other?
300 individuals from different places in the USA
the goal was to deliver a letter to a target person in Boston
through personal contacts
Results:
64 successful chains
on average 6.2 steps: 6 degrees of separation
2
Milgram, S. (1967). The small world problem. Psychology today, 2(1),
60-67.
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 18 / 33
Small Worlds
Milgram’s Experiment: Why as low as 6?
Random social networks:
assumes 500-1500 contacts per person3
for a random network, three steps involve ∼ 5003 = 125 · 106
individuals
Small World Property: d ≈ ln(N)
ln(k)
for US pop ≈ 330M and 500 contacts, d ≈ 3.16 (EU pop ≈ 450M,
then d ≈ 3.20)
in general, ln(N) ≪ N, therefore path length is of orders of
magnitude smaller than network size
small world phenomenon depends logarithmically on network size
3
Pool & Kochen (1978)
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 19 / 33
Small Worlds
Which Model to Choose?
Desired properties:
small diameter (average path length): l ≈ ln(N)
high clustering coefficient: C ≫ Crand
model clusters small diameter
Erdös Rényi no yes
Barabási-Albert4 no yes
grid yes no
? yes yes
4
this model did not yet exist at the time
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 20 / 33
Small Worlds
Watts-Strogatz Model5
WS(N, k, p)
Procedure:
start with N nodes connected to their k nearest neighbors
for each edge, with probability p, randomly rewire the target
node
For certain values of p, we obtain both high C and low l
5
Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of
‘small-world’networks. Nature, 393(6684), 440-442.
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 21 / 33
Small Worlds
Watts-Strogatz Model
6
6
Sporns O. (2011)
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 22 / 33
Small Worlds
Watts-Strogatz Model
7
http://bit.ly/1O2WBIL
7
Sporns O. (2011)
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 23 / 33
Small Worlds
Watts-Strogatz: ukázka
...
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 24 / 33
Small Worlds
Forest Fire Model8
Motivation:
Watts-Strogatz model does not create a scale-free network
Random rewiring is difficult to interpret
Procedure:
At each step, we add a node u
We randomly select and ignite a connection point
The fire iteratively spreads with probability p, r times less likely
through incoming edges
We attach the burned edges to u
8
Leskovec et. al (2005)
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 25 / 33
Small Worlds
Forest Fire Model – Properties
Preferential attachment: power-law degree distribution
Community-driven attachment: clustering
Only two parameters
9
9
Leskovec et. al (2005)
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 26 / 33
Small Worlds
Small Worlds vs Efficiency10
Intuition:
In physical networks (transportation, neural, etc.), there is a
trade-off between maximum connectivity and the cost of
building connections
The evaluation function E = λL + (1 − λ)W
L is the characteristic path length, W is the total cost of
connections (for a single edge, it depends on the distance
between nodes), λ indicates a preference for L vs W
10
Mathias & Gopal (2000)
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 27 / 33
Small Worlds
Small worlds vs efficiency
Result:
When network minimizes wiring (λ → 0), regular graphs are
obtained
When network maximizes wiring (λ → 1), random networks are
obtained
For intermediate values, we get small worlds with hubs – note
that hubs do not emerge in classic WS model
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 28 / 33
Small Worlds
11
11
Mathias & Gopal (2000). Small Worlds: How and Why
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 29 / 33
Small Worlds
Milgram’s Experiment – Navigation
Observation:
with each step, the letters get closer to their addressee
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 30 / 33
Small Worlds
Milgram’s Experiment Nowadays12
Navigation over geo-tagged Twitter Network:
knowing only location, it is quite easy to reach the right city
however, on a smaller scale (inside the city), a letter gets ’lost’
and spends much more time looking for the right addressee
In Milgram’s experiment, participants used other than just
geographic info (e.g., occupation, social status...)
12
Szüle et al. (2014). Lost in the City: Revisiting Milgram’s Experiment
in the Age of Social Networks.
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 31 / 33
Small Worlds
Kleinberg’s Model13
Motivation:
Utilize local knowledge of the geographic location of the target
and other nodes
Procedure:
Nodes are placed on a grid
Random edges are added:
p(u, v) = d(u, v)−α
where α > 0
Findings:
there is a specific value of α which allows optimal (fast)
navigation (α = 2)
any other value requires asymptotically larger delivery time
13
Kleinberg, J. (2000). Navigation in a small world.
J. Spurný, E. Výtvarová ·Network Models ·March 17, 2023 32 / 33