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 α 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α. Our analysis determines three phases for the percolation subgraph Gp of the small-world graph, depending on the value of α. • If α<1, there is a p<1 such that, with high probability, there are Ω(n) nodes that are reachable in Gp from one another in O(log⁡n) hops; • If 1<α<2, there is a p<1 such that, with high probability, there are Ω(n) nodes that are reachable in Gp from one another in logO(1)⁡(n) hops; • If α>2, for every p<1, with high probability all connected components of Gp have size O(log⁡n).