Bond percolation in small-world graphs with power-law distribution

Full-bond percolation with parameter p is the process in which, given a graph, we keep each edge independently with probability p and delete it with probability 1 - p. Bond percolation is studied in parallel computing and network science to understand the resilience of distributed systems to random link failure and the spread of information in networks through unreliable links. Moreover, the full-bond percolation is equivalent to the Reed-Frost process , a network version of SIR epidemic spreading. We consider one-dimensional power-law small-world graphs with parameter a obtained as the union of a cycle with additional long-range random edges: each pair of nodes {u, v} at distance L on the cycle is connected by a long-range edge {u, v}, with probability proportional to 1/L-alpha. Our analysis determines three phases for the percolation subgraph G(p) of the small-world graph, depending on the value of alpha. center dot If alpha < 1, there is a p < 1 such that, with high probability, there are Omega(n) nodes that are reachable in G(p) from one another in O(log n) hops; center dot If 1 < alpha < 2, there is a p < 1 such that, with high probability, there are Omega(n) nodes that are reachable in G(p) from one another in log(O(1)) (n) hops; center dot If alpha > 2, for every p < 1, with high probability all connected components of G(p) have size O(log n).