Abstract
In this work we investigate a bootstrap percolation process on random graphs generated by a random graph model which combines preferential attachment and edge insertion between previously existing vertices. The probabilities of adding either a new vertex or a new connection between previously added vertices are time dependent and given by a function f called the edge-step function. We show that under integrability conditions over the edge-step function the graphs are highly susceptible to the spread of infections, which requires only 3 steps to infect a positive fraction of the whole graph.
| Original language | English |
|---|---|
| Pages (from-to) | 1221-1239 |
| Number of pages | 19 |
| Journal | Alea (Rio de Janeiro) |
| Volume | 19 |
| Issue number | 2 |
| DOIs | |
| State | Published - 2022 |
Funding
Received by the editors April 21st, 2021; accepted August 4th, 2022. 2010 Mathematics Subject Classification. Primary 05C82; Secondary 60K40, 68R10. Key words and phrases. preferential attachment, random graphs, Bootstrap percolation, Karamata’s theory, regular varying function. C.A. was supported by the Noise-Sensitivity everywhere ERC Consolidator Grant 772466.
Keywords
- Bootstrap percolation
- Karamata’s theory
- Preferential attachment
- Random graphs
- Regular varying function