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 E¹³ 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