Name
Abstract | ||
|---|---|---|
We study a variant of the classical bootstrap percolation process on Erdos Renyi random graphs. The graphs we consider have inhibitory vertices obstructing the diffusion of activity and excitatory vertices facilitating it. We study both a synchronous and an asynchronous version of the process. Both begin with a small initial set of active vertices, and the activation spreads to all vertices for which the number of excitatory active neighbors exceeds the number of inhibitory active neighbors by a certain amount. We show that in the synchronous process, inhibitory vertices may cause unstable behavior: tiny changes in the size of the starting set can dramatically influence the size of the final active set. We further show that in the asynchronous model the process becomes stable and stops with an active set containing a nontrivial deterministic constant fraction of all vertices. Moreover, we show that percolation occurs significantly faster asynchronously than synchronously. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1002/rsa.20854 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | Field | DocType |
bootstrap percolation,input normalization,random graphs | Population,Discrete mathematics,Diffusion process,Asynchronous communication,Combinatorics,Vertex (geometry),Bootstrap percolation,Mathematics | Journal |
Volume | Issue | ISSN |
55.0 | 4.0 | 1042-9832 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hafsteinn Einarsson | 1 | 9 | 2.20 |
| Johannes Lengler | 2 | 70 | 14.94 |
| Frank Mousset | 3 | 5 | 3.59 |
| Konstantinos Panagiotou | 4 | 290 | 27.80 |
| Angelika Steger | 5 | 995 | 111.50 |