Transcript It*sa Small World - University of Warwick

It’s a Small World
by
Jamie Luo
Introduction
• Small World Networks and their place in
Network Theory
• An application of a 1D small world network to
model the spread of an infection
(Cristopher Moore and M.E.J. Newman)
Random Graphs
• In 1959 Erdos and Renyi define a random graph as N labelled nodes
connected by n edges, which are chosen randomly from the N(N21)/2
possible edges.
• Eg: Below are cases for N=10 with n=0 and n=7
Regular Lattices
• On the other extreme you have regular lattices.
• Eg: Z2 or the one dimensional lattice depicted below
Some Definitions
• For a G graph of n vertices labelled v1, ..., vn:
• Characteristic path length, l(G).
l is defined as the number of edges in the shortest path between two
vertices, averaged over all pairs of vertices.
• Clustering coefficient, C(G).
# edges that exist between th e neighbours of vi
Ci 
kvi (kvi  1) / 2
where kvi  the number of neighbours of vi
1 n
C (G )   Ci
n i 1
A Small World Network
• In 1998 Duncan J. Watts & Steven H. Strogatz produce a new network
model with a parameter 0 < p < 1, that is regular lattice at φ=0 but is a
random graph at p=1.
Crossover
• l ~ L , linearly on a regular lattice, where L=linear dimension
• l α log(N)/log(z) , for a random graph, where N=the number of sites
and z=the average degree of the vertices
•
•
•
•
•
The small world model lies yet again between these two extremes.
If we fix p then:
For small N,
l(N,p) ~ L linearly
For large enough N ,
l(N,p) ~ log(N)
It turns out there is a crossover from the small world to a ‘large one’.
Scaling
• Similar to the correlation length behaviour in statistical mechanics, at
some intermediate system value N = l, where the transition occurs, we
expect, l ∼ p-τ.
• Additionally, close to the transition point, l(N, p) should obey the finitesize scaling relation:
l(N, p) ~ p  f (Np )
where f(u) is a universal scaling function obeying,
f (u) ∼ u
if u << 1
f (u) ∼ ln u
if u>>1
• It has been analytically demonstrated that for this model τ=1.
Another Small World
• To investigate the spread of an epidemic infection we make an alteration
to the construction of Strogatz and Watts’ model.
• Instead of rewiring edges we simply add shortcuts between vertices with
a probability φ for each bond.
An Infectious Model
• The two parameters we are interested in for this model of the spread of
an infectious disease are susceptibility, the probability that an individual in
contact with a disease will contract it and transmissibility, the probability
that contact between an infected individual and a healthy but susceptible
individual will result in the latter contracting the disease.
• To deal with susceptibility and transmissibility you can incorporate into the
model site and bond percolation respectively.
• We will deal with the site percolation case in detail.
• So take our small world and say any individual is assumed to be
susceptible with probability p. Then we just fill the sites in our small world
(the individuals ) to indicate they are susceptible with probability p.
Idea
• We always start with one infected individual from which the disease
spreads.
• We partition our model into ‘local clusters’ which are those collections of
connected filled sites before the shortcuts are introduced.
• All sites in the local cluster containing the infected individual are infected
immediately. Then in the next time step every local cluster connected to
the infected cluster by a single step along a shortcut is then infected and
this infected cluster grows accordingly.
Analysis
• We know that the probability that two random sites are connected by a
shortcut is,
  1  (1  2 / L2 ) kL  (2k ) / L
The approximation is true for sufficiently large L.
• For k=1, the average number of local clusters of length i is,
N i  (1  p ) 2 p i L
• Define v to be a vector at each time step, with vi = the probability that a
local cluster of size i has just been added to the infected cluster. This is our
means for constructing the infected cluster.
• We want to know v’ from v.
• At or below the percolation threshold, the vi are small and so the vi ‘
depend linearly on the vi according to a transition matrix M and thus,
vi '   M ij v j
j
where,
M ij  N i [1  (1  )ij ]
Eigenvalues
•
•
•
•
Consider the largest eigenvalue of M, call it λ.
Case 1:
λ<1,
then v tends to 0.
Case 2:
λ>1
then v grows to towards the size of the system.
Thus the percolation threshold occurs at λ=1. Generally finding λ is
difficult but for large L we can approximate M by,
M ij  ij N i
which is the outer product of two vectors. So we can rewrite,
vi '  v j  i  jv j
j
with the eigenvectors of M have the form,

1

vi    jv j 
  i N i
 j

pc
• This simplifies to give,
   j2N j
j
and thus for k=1
1 p 
1 p 
  2 

  Lp
1 p 
1 p 
• Setting λ=1 allows us to derive values for,
  (1  pc ) / 2 pc (1  pc )
4 2  12  1  2  1
pc 
4
More Results
• For general k,
and at the threshold then,
2  (1  p ) k
  2kp
(1  p ) k
(1  pc ) k
 
2kpc [ 2  (1  pc ) k ]
which implies that pc is then the root of a k+1 order polynomial.
• For bond percolation we have an analogous scenario to site percolation
for the case k=1.
• For general k there is a method to find solutions but this becomes very
tedious for larger k.
• Numerical results exist in the case when both site and bond percolation
are allowed but no analytical solutions.
Summary
• Small Worlds interpolate between the
extreme models of random graphs and regular
lattices
• They exhibit the shorter characteristic length
scales of random graphs and the higher
clustering coefficients regular lattices
• Thus they can be applied usefully to model
real world networks which share these
properties.