License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SAND.2023.3
URN: urn:nbn:de:0030-drops-179392
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17939/
Becchetti, Luca ;
Clementi, Andrea ;
Pasquale, Francesco ;
Trevisan, Luca ;
Ziccardi, Isabella
Bond Percolation in Small-World Graphs with Power-Law Distribution
Abstract
Full-bond percolation with parameter p is the process in which, given a graph, for every edge independently, we keep the edge 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 G_p 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 G_p from one another in ?(log n) hops;
- If 1 < α < 2, there is a p < 1 such that, with high probability, there are Ω(n) nodes that are reachable in G_p from one another in log^{?(1)}(n) hops;
- If α > 2, for every p < 1, with high probability all connected components of G_p have size ?(log n).
BibTeX - Entry
@InProceedings{becchetti_et_al:LIPIcs.SAND.2023.3,
author = {Becchetti, Luca and Clementi, Andrea and Pasquale, Francesco and Trevisan, Luca and Ziccardi, Isabella},
title = {{Bond Percolation in Small-World Graphs with Power-Law Distribution}},
booktitle = {2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
pages = {3:1--3:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-275-4},
ISSN = {1868-8969},
year = {2023},
volume = {257},
editor = {Doty, David and Spirakis, Paul},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17939},
URN = {urn:nbn:de:0030-drops-179392},
doi = {10.4230/LIPIcs.SAND.2023.3},
annote = {Keywords: Information spreading, gossiping, epidemics, fault-tolerance, network self-organization and formation, complex systems, social and transportation networks}
}
|
Keywords: |
|
Information spreading, gossiping, epidemics, fault-tolerance, network self-organization and formation, complex systems, social and transportation networks |
|
Collection: |
|
2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
12.06.2023 |
