I want to study this pdf file in a 30 minutes. I know almost nothing about its concept and I want you to:
1. create an index from all the contents it provides 2. Give me a comprehensive, but casual description about what it contains in a way that I understand the main points of this pdf file, (If it could make a sense you may gimme an example in which contains a scenario related to the main point of this pdf)


Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 1
Elements of
Random Graph Theory
Part 1
Michela Meo
Telecommunication Networks GroupMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 2
Graphs
• Graphs are used in several different fields for
representing
– state machines
– relationships among elements of a system or of
a population
• The number of possible applications is
huge...Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 3
Definitions
• A graph G is a set of elements G={V,E} with
– V: set of vertices or nodes with total number of nodes |V|=n
– E: set of edges or links with total number of links |E|=l
– edges describe the existence of a relation between two
vertices
– an edge <vi,vj> indicates a relation between vertices vi and vj
• Nodes are connected through links
– Links can be directed or undirected
– Two nodes are neighbors when they are connected through a link
• Example: In a tree, n=l+1Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 4
Definitions
• A path (or walk) is given by a sequence of vertices
– <v1,v2,...,vk> such that and <vi,vi+1>
– A path between nodes is a set of links connecting two nodes through
intermediate nodes
– k is the length of the path
– The length of a path is the number of links in it
• A cycle (or close walk) is a path with
– v1=vk
• The distance between two nodes is the length of the shortest
path
– in directed graphs the distance between A and B can be different from the
distance between B and A
• A node i is reachable from (or connected to) node j if there exists
a path from j to i
v
i
∈V ∈ EMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 5
Definitions
• Degree k: number of links connected to a node
– for directed graphs, we distinguish in-degree ki from outdegree ko
• A graph is connected if there exists a path between any
pair of nodes
– In a connected graph, k≥1 for all nodes
• A graph is acyclic if it contains no loop
• A connected acyclic graph is a treeMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 6
Examples
Connected graph G
Unconnected graphsMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 7
Examples
Connected graph G
TreesMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 8
Examples
i
j •
Distance between i and j is 2 (shortest path)
• There are other paths between i and j with longer
distancesMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 9
Examples
• i has degree 4
• j has degree 3
• m has degree 2
i
m
j
• In a connected graph, the degree k≥1
for all nodesMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 10
Definitions
• A subgraph S={VS,ES} of a graph G={V,E} contains a
subset of the vertices and nodes of G
–
• A graph is a supergraph of G if it contains G as a
subgraph
V
S
⊂V and E
S
⊂ EMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 11
Examples
Graph G
Subgraph of GMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 12
Objective
• Random Graphs (RGs) are graphs built
according to some probabilistic rules
• RGs can be used for modeling complex
systems in which a large number of elements
interactMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 13
Objective
• Examples
– Internet: links and routers
– www: links to pages through HTTP
– P2P systems: L7 (application layer) logical
networks
– social interactions: social networks, co-authors,
friends, ...
– neural networks
– epidemiology phenomena
– ...Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 14
What is a RG?
• A RG is a statistical ensemble of graphs
– a particular graph is a realization in this ensemble
• Statistical ensembles are used in physics and thermodynamic to
represent interacting particles
• A RG is defined by
– A set G of graphs
– A rule to associate a probability to each graph in the set,
for each G ∈ ΓMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 15
Erdos-Renyi RGs
• An ER RG, G(n,p), is a statistical ensemble of
graphs with n vertices in which each graph appears
with a probability that depends on the no. of its
edges m and it is equal to
pm 1 − p
( )M−m with M = 21 n (n − 1)
no. of possible links
Each edge is present with independent probability pMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 16
Example
• n=5, p=1/4 à M=10
• full mesh
• m=M
pM = p10
• disconnected
graph
• m=0
(1 − p)M = (1 − p)10
• disconnected,
• m=4
pm (1 − p)M−m = p4 (1 − p)6
9.5*10-7 0.056 6.9*10-4Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 17
Examples
n=20Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 18
Erdos-Renyi RGs
• Each vertex has a degree distribution given by
P (k) = n − 1
k
⎛⎜⎝
⎞⎟⎠
pk 1 − p
( )n−1−k
n-1 possible other vertices
• With average vertex degree
E[k] = k
i =0
n−1
∑ P(k) = p(n − 1) ≅ pnMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 19
Erdos-Renyi RGs
• For n going to infinite and the average E[k] fixed,
the degree distribution P(k) converges to the
Poisson distribution
P (k) =
e−E [k ] E [k]
( )k
k
!Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 20
Build an ER RG
G(n, p)= Ο # empty set
for i = 1 to n do
for j = i+1 to n do # each possible edge iàj
Generate uniform random number θ ∈ [0, 1)
if θ < p then # with prob. p
G(n, p)= G(n, p) + (i, j) # add edgeMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 21
Characteristics of RGs
• Component: subset of vertices such that each vertex is
reachable from others by some path
– Size of the component: number of vertices belonging to the
component
– Giant component: a graph has a giant component when a
finite fraction of nodes are in the same component
– Important in the limiting behavior for n à ∞
• Radius: maximum distance between nodes in a
component
• Diameter: average distance between nodes in a
componentMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 22
Clustering coefficient
• Degree is a local property of a graph
– For a RG with statistically independent (equivalent)
vertices, the degree distribution determines the statistical
properties of the graph
• Clustering coefficient of vertex v characterizes the
“density” of the connections close to a vertex
C
v
=
no. edges between neighbors of v
tot.no. of possible edges between neighbors of vMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 23
Clustering coefficient
C
v
=
2y
z(z −1)
• In this case y=3, z=5
• The no. of possible edges
is z(z-1)/2 = 10
• C
v=3/10
v
z(z − 1)
2
is the no. of possible edges between neighbors
z is the no. of neighbors and y the no. of existing edges
between themMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 24
Clustering coefficient
• Clustering coefficient of the graph: average
clustering coefficient of the vertices
– average probability that two neighbors of a
vertex are neighbors to each other
• For example: C=1 for a full mesh, all nodes
have C
v=1
E[C] = 1
n
C
i
i =1
n∑Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 25
Non-Poisson distribution of degree
• In some cases it can be interesting to have a graph
with equivalent vertices with a given degree
distribution P(k)=pk
– It can be used when in a real case we observe or
measure the node distribution to be P(k)
1 10
degree
1
10
100
1000
number of autonomous systems
(a) Internet
1 10 100 1000
out−degree
100
102
104
106
10
number of web sites
(b) World−Wide Web
1 10 100 1000
degree
10−2
100
102
104
106
number of authors
mathematics
biomedicine
(c) collaborations
of scientists
1 10 100 1000 10000
degree
100
101
102
103
104
number of actors
(d) collaborations
of film actors
Introduction 5
1 10
degree
1
10
100
1000
number of autonomous systems
(a) Internet
1 10 100 1000
out−degree
100
102
104
106
108
number of web sites
(b) World−Wide WebMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 26
Examples of graphs
Network n [thousand] E[k] Cv
measured
Cv RG
Internet (AS) 6.4 3.8 0.24 0.00063
World-Wide Web 153 35.2 0.11 0.00023
power grid 4.9 2.7 0.08 0.00054
biology
collaborations
1520 15.5 0.081 0.000010
mathematics
collaborations
253 3.9 0.15 0.000015
neural networks 0.282 14 0.28 0.049
Source: “Random graphs as models of networks”, M.E.J. NewmanMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 27
Build an RG with P(k)
Bender and Canfield algorithm
1. Distribute stubs to nodes proportional to P(k)
# assign k stubs to nP(k) nodes
2. Randomly connects stubs
Assign 5 stubs
to nP(5) nodes
Assign 8 stubs
to nP(8) nodes
k
P(k)Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 28
Effect of Non-Poisson P(k)
• Consider a graph with equivalent vertices with
degree distribution P(k)=pk
• The objective is to understand the connectivity of
the graph starting from the local property of the
degree of nodes
• We wonder how many nodes we can reach starting
from a node A in the RGMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 29
Reaching new nodes
• Compute the no. of vertices that can be reached in
2 hops (distance 2) from a node A
– Assume that all nodes reached in 2 hops are new to A
(prob. that they are also neighbors of A is negligible)
A
B
CMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 30
Reaching new nodes
• The degree of the one hop away nodes is different from the
node degree
– A reaches nodes with degree k with a probability that is proportional to
k: the larger k is, the larger is the probability that it is a neighbor of A
• B has degree k with a probability that is equal to the fraction of
links leading to a node with degree k
A
B
C
P
B
(k) ≈ k ⋅ npk
no of nodes with
degree k
no of links leading
to nodes with
degree kMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 31
Reaching new nodes
• Starting from A, the probability qk of reaching k new nodes
through a direct neighbor B of A is equal to the probability
that B has degree k+1 (A is neighbor of B)
A
B
C
q k ≈ (k + 1)p k+1
• B has degree 3
• A reaches 2 new nodes through B
• The distribution is normalized
q k =
(k + 1)pk+1
jp
j
∑jMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 32
Example
A
B • B has degree 1, A does not reach new
nodes through B
• Prob. q0 proportional to p1
A
B • B has degree 2, A reaches 1 new node
through B
• Prob. q1 is proportional to 2p2
A
B
• B has degree 3, A reaches 2 new
nodes through B
• Prob. q2 proportional to 3p3Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 33
Reaching new nodes
• qk is the distribution of the number of new nodes that can
be reached through a neighbor
• The average number of new nodes is
E[q] = kq k =
k=0
∞∑
k(k + 1)p k+1
k=0
∞∑
kp k
k=0
∞∑
=
E[k2 ] −E[k]
E[k]
k(k + 1)p k+1
k=0
∞∑
= k(k + 1)pk+1
k=1
∞∑
= (k −1)kpk =
k=0
∞∑
k2 p k −
k=0
∞∑
kp k
k=0
∞∑Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 34
Reaching new nodes
• Let zi be the number of new nodes that can be reached at
the i-th hop, i.e., at distance i
E[q] =E[k2 ] −E[k]
E[k]
z
2
= E[q]E[k] = E[k 2] −E[k]
E[k]
z
1
= E[k 2] −E[k]
“similar” to the variance
z
m+1
=
E [k2 ] −E [k]
E [k]
z
m
=
z
2
z
1
z
mMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 35
Giant component
z
m+1
=
z
2
z
1
z
m
=
z
2
z
1
⎛⎜⎜⎝
⎞⎟⎟⎠
m
z
1
• is a critical value
• There are two possible regimes
z
2
z
1
> 1 lim
m→∞
z
m
= ∞
z
2
z
1
< 1 lim
m→∞
z
m
= 0
z ⎧⎪⎪⎪⎨⎪⎪⎪⎩
2
= z
1
Giant component
No giant component, network is
fragmented in an infinite no. of
components of finite sizeMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 36
Example: ER
• In ER RGs the distribution of the degree is Poisson,
z
2
= E[k 2] −E[k] = E[k]2 +E[k] −E[k] = E[k]2
z
2
z
1
=
E[k]2
E[k]
= E[k]
• If E[k]>1 there exists a Giant component
– A finite fraction of nodes are connectedMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 37
Example: Constant degree
• Consider a RG with constant degree E[k]=k
z
2
= E[k 2] −E[k] = k 2 −k
z
2
z
1
=
k2 −k
k
= k − 1
• If k>2 there exists a Giant component
– A finite fraction of nodes are connected
z
2
z
1
> 1 → k > 2Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 38
ExampleMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 39
Diameter
• The diameter of a RG is the average distance (no.
of hops of the shortest path) among pairs of nodes
– When there is a giant component, the diameter is
measured in the giant component
• When z2>>z1, the value of zm grows very fast, so
that for the diameter l, it is z l ≅ n
z
2
z
1
⎛⎜⎜⎝
⎞⎟⎟⎠
l −1
z
1
≅ n
l −1
( )log z 2
z
1
⎛⎜⎜⎝
⎞⎟⎟⎠
= log n
z
1
⎛⎜⎜⎝
⎞⎟⎟⎠
l = log(n / z 1)
log(z 2 / z 1)
+ 1Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 40
Diameter: Example
• For the ER RGs, z1=z, z2=z2
l = log(n / z 1)
log(z 2 / z 1)
+ 1 ≈ log(n / z)
log(z)
=
log(n) −log(z)
log(z)
≈
log(n)
log(z)
• The diameter grows logarithmically with the number
of nodes n
Small world effectMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 41
Small world
• Random connections guarantee that, even for a
large network, a few hops are needed to reach all
the other nodes
– Already known is social networking, since the Milgram
experiment in the ‘60s about the 6 degrees of separation
– For social networks (like FB) it is only 4 degree
– For P2P networks, this is why random connections
improve network performance w.r.t. choosing neighbors
based on geographical distance
l ≈ log(n)
log(z)Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 42
Small world experimentMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 43
Six degrees ?
Facebook finds only four! (2011)
Network Science Book – Albert BarabasiMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 44
Small world (MSN network)
90
• 90% of people can be reached in 8 hops
• Mean Shortest Path: 6.6 hops Network Science Book – Albert BarabasiMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 45
Clustering coefficient
• Let us compute the clustering coefficient
• The i-th neighbor of A has a no. of other neighbors
equal to ki that is distributed according to qk
A
i
j
q k =
(k + 1)pk+1
jp
j
∑j
ki
kj
• The prob. that i is
connected to j is
k
i
k
j
tot stubs nz
possible stub pairs
between i and jMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 46
Clustering coefficient
• Compute E[C]
E[C] =
E[k
i
k
j
]
nz
=
1 nz
kq k
∑k
⎛⎜⎜⎝
⎞⎟⎟⎠
2
E[C] = 1
nz
E[k2 ] −E[k]
E[k]
⎛⎜⎜⎝
⎞⎟⎟⎠
2
=
z n
E[k2 ] −E[k]
E[k]2
⎛⎜⎜⎝
⎞⎟⎟⎠
2
=
=
z n
E[k2 ] −E[k]2 +E[k]2 −E[k]
E[k]2
⎛⎜⎜⎝
⎞⎟⎟⎠
2
=
z n
C
k
2
+
E[k] − 1
E[k]
⎛⎜⎜⎝
⎞⎟⎟⎠
2
=
z n
C
k
2
+
z − 1
z
⎛⎜⎜⎝
⎞⎟⎟⎠
2
E[C] =z
n
C
k
2
+
z − 1
z
⎛⎜⎜⎝
⎞⎟⎟⎠
2
ki and kj are independent
sum E[k]2-E[k]2Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 47
Clustering coefficient: Example
• In the case of ER RGs, with Poisson distribution of
the degree, the value of Ck2 is 1/z
E[C] =z
n
1 z
+
z − 1
z
⎛⎜⎜⎝
⎞⎟⎟⎠
2
=
z n
1 + z − 1
z
⎛⎜⎜⎝
⎞⎟⎟⎠
2
=
z n
very small
• For the web (links of pages), it was estimated
E[C]=0.11 and z/n=0.00023; so the ER model does
not seem to be adequate for the web
• In several real networks, diameter is small but
clustering coefficient is quite largeMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 48
Heavy-tailed degree
• In heavy-tailed distributions, the mean is not
representative of any behavior
– many with small value of the degree
– some with very large value
• Power law:
– There is a finite probability of nodes with k>>E[k]
– For 2<g<3, E[k2] à infinite
– The graph has high clustering coefficient, small diameter
• Scale free networks
P (k) = p k ≈ ak−γMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 49
Heavy-tailed degree distributionMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 50
Heavy-tailed degree
• Useful to represent several real cases of complex
(and very large) systems that have the properties
– small world
– highly clustered
• Some nodes are “hubs” and are highly connected
and this makes the average distance systematically
shorter than in other RGsMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 51
References
• M.E.J. Newman, Random graphs as models of networks,
https://arxiv.org/pdf/cond-mat/0202208.pdf
• J . Travers, S. Milgram, An Experimental Study of the Small World
Problem, Sociometry, 1969
• D. Watts and S. Strogatz, Collective dynamics of “small-world” networks,
Nature, 1998
• J.Kleinberg, Navigation in Small World, Nature, 2000
• P. Dodds, R. Muhamad, D. Watts, An experimental study of search in
global social networks, 2003
• J. Kleinberg, The small-world phenomenon: An algorithmic perspective,
2000
Additional readings