Percolation Theory and Network Connectivity Jie Gao Computer Science Department Stony Brook University Papers Geoffrey Grimmett Percolation first chapter Second edition Springer 1999 Massimo Franceschetti Lorna Booth Matthew Cook Ronald Meester and Jehoshua Bruck Continuum percolation with unreliable and spread out connections Journal of Statistical Physics v 118 N 3 4 February 2005 pp 721 734 On a rainy day Observe the raindrops falling on the pavement Initially the wet regions are isolated and we can find a dry path Then after some point the wet regions are connected and we can find a wet path There is a critical density where sudden change happens Phase transition In physics a phase transition is the transformation of a thermodynamic system from one phase to another The distinguishing characteristic of a phase transition is an abrupt sudden change in one or more physical properties in particular the heat capacity with a small change in a thermodynamic variable such as the temperature Solid liquid and gaseous phases Different magnetic properties Superconductivity of medals This generally stems from the interactions of an extremely large number of particles in a system and does not appear in systems that are too small Bond Percolation An infinite grid Z2 with each link to be open appear with probability p independently Now we study the connectivity of this random graph p 0 25 Bond Percolation An infinite grid Z2 with each link to be open appear with probability p independently Now we study the connectivity of this random graph p 0 75 Bond Percolation An infinite grid Z2 with each link to be open appear with probability p independently Now we study the connectivity of this random graph No path from left to right p 0 49 Bond Percolation An infinite grid Z2 with each link to be open appear with probability p independently Now we study the connectivity of this random graph There is a path from left to right p 0 51 Bond Percolation There is a critical threshold p 0 5 The probability that there is a bridge cluster that spans from left to right Bond Percolation There is a critical threshold p 0 5 When p 0 5 there is a unique infinite size cluster almost always When p 0 5 there is no infinitely size cluster When p 0 5 the critical value there is no infinite cluster Percolation theory studies the phase transition in random structures Infinite cluster connected graph Main problems in percolation The critical threshold for the appearance of some property e g an infinite cluster Behavior below the threshold We know all clusters are finite How large are they Distribution of the cluster size Behavior above the threshold We know there exists an infinite cluster Is it unique What is the asymptotic size with respect to p and n the network size Behavior at the threshold Is there an infinite cluster or not What is the size of the clusters Examples of Percolation Spread of epidemics virus infection on the Internet Each sick node has probability p to infect a neighbor node Denote by p the contagious parameter If p is above the percolation threshold then the disease will spread world wide The real model is more complicated taking into account the time variation healing rate etc Gossip based routing content distribution in P2P network software upgrade The graph is important in deciding the critical value An interesting result is about the scale free graphs also called power law that model the topology of the Internet or social network in one of such models random attachment with preferential rule the percolation threshold vanishes More examples Connectivity of unreliable networks Each edge goes down randomly Is there a path between any two nodes with high probability Resilience or fault tolerance of a network to random failures Random geometric graph density of wireless nodes or critical communication range Wireless nodes with Poisson distribution in the plane Nodes within distance r are connected by an edge There is a critical threshold on the density or the communication range such that the graph has an infinitely large connected component Bond percolation A grid Zd each edge appears with probability p C x the cluster containing the grid node x By symmetry the shape of C x has the same distribution as the shape of C 0 where 0 is the origin p the probability that C 0 has infinite size Clearly when p 0 p 0 when p 1 p 1 Percolation theory there exists a threshold pc d such that p 0 if p pc d p 0 if p pc d Bond percolation This is people s belief on the percolation probability p It is known that p is a continuous function of p except possibly at the critical probability However the possibility of a jump at the critical probability has not been ruled out when 3 d 19 An easy case 1D 1D case a line Each edge has probability p to be turned on If p 1 there are infinitely many missing edges to the left and to the right of the origin Thus p 0 The threshold pc 1 1 For general d dimensional grid Zd it can be embedded in the d 1 dimensional grid Zd 1 Thus if the origin belongs to an infinite cluster in Zd it also belongs to an infinite cluster in Zd 1 This means pc d 1 pc d In fact it can be proved that pc d 1 pc d 2d interesting things start to happen Theorem For d 2 pc d 1 2 There are 2 phases Subcritical phase p pc d p 0 every vertex is almost surely in a finite cluster Thus all the clusters are finite Supercritical phase p pc d p 0 every vertex has a strictly positive probability of being in an infinite cluster Thus there is almost surely at least one infinite cluster At the critical point this is the most interesting part Lots of unknowns For d 2 or d 19 there is no infinite cluster The problem for the other dimensions is still open Site Percolation An infinite grid Z2 with each vertex to be open appear with probability p independently Now we study the connectivity of this random graph p 0 3 Site Percolation An infinite grid Z2 with each vertex to be open appear with probability p independently Now we study the connectivity of this random graph p 0 80 Site Percolation Percolation threshold is still unknown Simulation shows it s around 0 59 note this is larger than bond percolation p 0 58 Site Percolation Site percolation is a generalization of bond percolation Every bond percolation can be represented by a site percolation but not the other way around Percolation in an infinite connected graph G V E Bond percolation each edge appears with probability p Site percolation each vertex appears with probability