Transcript PPT - Eurecom

Random Graph Models: Create/Explain Complex
Network Properties
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
Random Graph Models: Why do we Need Them?
 The networks discussed are quite large!

Impossible to describe or visualize explicitly.
 Consider this example:




You have a new Internet routing algorithm
You want to evaluate it, but do not have a trace of the Internet
topology
You decide to create an “Internet-like” graph on which you will run
your algorithm
How do you describe/create this graph??
 Random graphs: local and probabilistic rules by which
vertices are connected
 Goal: from simple probabilistic rules to observed complexity
Q: Which rules gives us (most of) the observed properties?
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
2
Emergence of Complexity
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
3
Emergent Complexity in Cellular Automata
Local Rules
Each cell either white or blue (“live”)
Each cell interacts with its 8 neighbors
Time is discrete (rounds)
Any blue cell with fewer than two live
neighbors  becomes white
2. Any blue cell with two or three blue
neighbors lives on to the round
3. Any blue cell with more than three blue
neighbors  becomes white
4. Any white cell with exactly three blue
neighbors  become blue



1.
 This is “Conway’s game of life” (many other automata)
 http://www.youtube.com/watch?v=ma7dwLIEiYU&feature=relat
ed (demo)
 http://www.bitstorm.org/gameoflife/ (try your own)
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
4
Back to Networks: (Erdös-Rényi) Random Graphs
 A very (very!) simple local rule:
(any) two vertices are connected with probability p
 Only inputs: number of vertices n and probability p

Denote this class of graphs as G(n,p)
Erdös-Rényi model (1960)
Connect with probability p
p=1/6 N=10
k ~ 1.5
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
5
How Many Networks in G(n,p)?
N and p do not uniquely define the
network– we can have many different
realizations of it. How many?
𝑁(𝑁−1)
2 2
G(N,L): a graph with N nodes and L links
The probability to form a particular graph G(N,L) is
P(G(N,L))  pL (1 p)
Thrasyvoulos Spyropoulos / [email protected]
N(N1)
L
2
Eurecom, Sophia-Antipolis
G(10,1/6)
N=10
p=1/6
That is, each graph G(N,L)
appears with probability
P(G(N,L)).
Relation of G(N,p) to G(N,L)
P(L): the probability to have exactly L links in a network of N nodes and probability p:
The maximum number of
links in a network of N
nodes.
N 
N(N1)
L
  L
2
P(L)  2 p (1 p)
 
 L 

Number of different ways we can
choose L links among all potential
links.
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
Binomial distribution...
G(N,p) statistics
P(L): the probability to have a network of exactly L links
N 
N(N1)
L
  L
2
P(L)  2 p (1 p)
 
 L 
 The average number of links <L> in a random graph

 L 
N(N 1)
2

L 0
N(N 1)
LP(L)  p
2

 The standard deviation
N(N 1)
  p(1  p)
2
 k  p( N  1)
2
Thrasyvoulos Spyropoulos / [email protected]
Average node degree <k>
Eurecom, Sophia-Antipolis
G(N,p) as N  ∞
1  p

2 


 L   p N ( N  1) 
1/ 2
1
 O 
N
As the network size increases, the distribution becomes increasingly narrow—which
means that we are increasingly confident that the number of links the graph has is in
the vicinity of <L>.
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
Random Graphs: Degree Distribution
 The degree distribution follows
a binomial


 N  1 k
p (1  p)(N1) k
p(k)  B(k;N,p)  
 k 
average degree is <k> = p(N-1)
variance σ2 = p(1-p)(N-1)
 Assuming z=Np is fixed, as N → ∞,
zk z
p(k)  P(k; z) 
e
k!
B(N,k,p) is approximated by a
Poisson distribution
 As N → ∞



 1 p 1 
σk

 k   p (N  1) 
Highly concentrated around the mean
Probability of very high node degrees is exponentially small
Very different from power law!
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
1/2

1
(N  1)1/2
10
Are Erdos-Renyi (Poisson) Graphs Small-World?
The secret behind the small world effect –
Looking at the network volume
S ( d )  4d
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
The Volume of Geometric Graphs
The secret behind the small world effect –
Looking at the network volume
d
N (d )   4 x  2d (d  1) ~ d 2
x 1
Polynomial growth
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
The Exploding Volume of Random Graphs
The secret behind the small world effect –
Looking at the network volume
d
N (d )   4 x  2d (d  1) ~ d 2
x 1
Polynomial growth
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
The Exploding Volume of Random Graphs (2)
The secret behind the small world effect –
Looking at the network volume
k d 1  1
N (d )   k 
~ kd
k 1
x 1
d
d
N (d )   4 x  2d (d  1) ~ d 2
x
x 1
Exponential growth
k
Polynomial growth
N
d
d  log k N

d 
ln N
ln k
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
Distance in Random Graphs Compare with Real Data
l max 
log N
log k
Given the huge differences in scope, size, and average degree, the
agreement is excellent!
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
Random Graphs: Clustering Co-efficient
 Consider a random graph G(n,p)
Q: What is the probability that two of your neighbors are
also neighbors?
A: It is equal to p, independent of local structure
 clustering coefficient C = p
 when z is fixed (sparse networks): C = z/n =O(1/n)
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
16
Clustering in Random Graphs Compare with Real Data
Given the huge differences in scope, size, and average degree,
there is a clear disagreement.
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
Summary: Are Real Networks Random Graphs?
 Erdos-Renyi Graphs are “small world”

path lengths are O(logn)
√
 Erdos-Renyi Graphs are not “scale-free”


Degree distribution binomial and highly-concentrated (no powerlaw)
Exponentially small probability to have “hubs” (no heavy-tail)
 Erdos-Renyi Graphs are not “clustered”

C  0, as N becomes larger
X
X
Conclusion: ER random graphs are not a good model of real
networks

BUT: still provide a great deal of insight!
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
18
Poisson Graph Diameter: Growth is slightly slower
Exponential growth:
d 
ln N
ln k
Clustering inhibits the small-worldness
Some of your neighbors neighbors are also your own
S (1)  k
S (0)  1
S ( 2)  k 2

S (1)  k
S (d )  k d
 N  k 1 
2
S (2)  k 2 
  k 1  p 
N


 N  k 2 (1  p )  k 
  k 3 (1  kp)
S (3)  kS (2)
N



S (d  1)  S (d  2) 

d
d 2
S (d )  kS(d  1)1 
  k 1 k p
N



Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis

Small World Graphs: Watts-Strogatz Model
 Short paths must be combined with

High clustering coefficient
Watts and Strogatz model [WS98]
 Start with a ring, where every node is connected to the next k nodes
 With probability p, rewire every edge (or, add a shortcut) to a random node
order
p=0
Thrasyvoulos Spyropoulos / [email protected]
randomness
0<p<1
Eurecom, Sophia-Antipolis
p=1
20
Small World Graphs (2)
Clustering Coefficient – Characteristic Path Length
log-scale in p
For small p, C ~ ¾
L ~ logn
When p = 0, C = 3(k-1)/2(2k-1) ~ ¾
L = n/k
The Watts Strogatz Model: It takes a lot of randomness to ruin
the clustering, but a very small amount to overcome locality
Thrasyvoulos Spyropoulos / [email protected]
Eurecom, Sophia-Antipolis
21