Tuesday 22nd July
Networks
Dr Mark Walters
http://en.wikipedia.org/wiki/Percolation_theory
In mathematics, percolation theory describes the behaviour of connected clusters in a random graph.
The above image shows a three-dimensional site percolation graph.
Consider the two dimensional graph below showing islands in a river connected by bridges.
Imagine that each bridge has a half chance of getting destroyed and half of them do get destroyed. What is the chance we can still cross the river?
In principle this can be solved. There is 2 x E13 possibilities.
P is the probability of getting across the bridge and p – 1 is the probability of not getting across the bridge
Consider an infinite square lattice.
Suppose we are on the infinite square lattice . The probability that the edge is open is p and the probability it is closed is 1 – p. Can we drive forever starting from the origin O without going back there or repeating an edge? The answer is we can’t.
In the above image the black lines are the open bridges and the red bridges are closed.
Is there any starting point we can drive forever
Back to the first picture
Probability (we can drive from 0) £ P we can drive from 0 or time t for any t
In the image below the green line represents a particular path. Fix the path at length t. What is the chance I can drive along this path (that is the chance all the bridges on it are open)? Just
Path of length 3 = 36
Number of paths of length
What is the chance some paths are open
Each channel has a ½ chance of being open. 0 if p = 1.
This is exactly the same as the previous examples of cars and bridges. The chance the ship can go along the river = the chance the car can go across the bridge (exactly one car and exactly one ship). So p(ship) + p(car) = 1
P(ship + car) = 0
p(ship) p(car) = ½
Blue lines indicate open channels. If the car can’t drive forever the boat can sail around the origin.
The aim is to show the boat is not likely to be able to sail around the origin.
Fix a cycle about the origin with a length t. What is the probability the boat can sail that loop?
The cycle must cross the X axis and not be too far around the origin, somewhere between 0 and t/2. Number of cycles of length t
therefore the chance the ship can sail around the origin on a cycle of length t is
The chance there is some cycle around the origin is
If p is close to 1 this sum is small (i.e. less than 1) there is some chance the car can drive forever from the origin