DOC PREVIEW
SBU CSE 590 - Percolation Theory and Network Connectivity

This preview shows page 1-2-3-19-20-39-40-41 out of 41 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Percolation Theory and Network Percolation Theory and Network CConnectivity onnectivity Jie GaoComputer Science DepartmentStony Brook UniversityPapersPapers• 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 dayOn 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 transitionPhase 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 PercolationBond 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.25Bond PercolationBond 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.75Bond PercolationBond 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.49No path from left to rightBond PercolationBond 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.51There is a path from left to right!Bond PercolationBond Percolation• There is a critical threshold p=0.5. The probability that there is a “bridge” cluster that spans from left to right.Bond PercolationBond 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 Infinite cluster ≠≠connected graphconnected graphMain problems in percolationMain 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 PercolationExamples 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 timevariation, 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 examplesMore 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 percolationBond 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 percolationBond 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:1DAn 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 happen2d: 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.


View Full Document

SBU CSE 590 - Percolation Theory and Network Connectivity

Download Percolation Theory and Network Connectivity
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Percolation Theory and Network Connectivity and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Percolation Theory and Network Connectivity 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?