Asynchronous bootstrap percolation

08 Apr 2016

In the previous post we discussed bootstrap percolation, a process which models the dissemination of information in a graph. In this post we will see a slight variation of the process. Percolation is traditionally defined to be round based. However, in reality processes such as rumor spreading, disease transmission and neural signals are usually not synchronous. This leads to an asynchronous variant of the process (scroll down if you are eager to see the visualisation).

As before, when a vertex turns active, you can think of it as sending a message to all its neighbours notifying them of its new state (or infecting them with some disease). The messages do not arrive instantly. In the synchronous setting we had to wait for one round until they arrived, corresponding to a time delay of 1. In the asynchronous setting these delays can be arbitrary. In (Einarsson, Lengler, Panagiotou, Mousset, & Steger, 2014) we studied for instance the case when all the edges draw their delay from an exponential distribution with expected delay 1. Recall that as in (Janson, Łuczak, Turova, & Vallier, 2012) we studied the process on $G_{n,p}$, the Erdős–Rényi random graph model. As it turned out, such a slight modification had an interesting quantitative effect on the process. The activity percolated much faster!

We showed that asymptotically such a process requires only constant time in expectation to activate all the vertices whereas the synchronous process can require up to $\sim\log\log(np)$ rounds in expectation. This improved speed is due to the fact that once enough many messages are being delivered almost certainly some of them will be extremely fast which further fuels the process. You can think of the process in terms of three phases, the startup phase, which decides if the activity survives or not, the explosion phase where almost all the vertices turn active (and is the main contributor to the double exponential speed of the round based process) and finally the clean up phase where the last few vertices turn active. In our setting the explosion phase is instantaneous, formally it takes time $o(1)$ (less than constant) to activate almost all the vertices (after the initial hurdle of getting the process started).

Below you can see an implementation of asynchronous bootstrap percolation where the expected delay of a message is initially set to five seconds (you can play with the parameters in the box below, be warned though, too many vertices can slow down the performance). If you choose the parameters nicely you will notice that the slow messages are usually too slow to make any difference. The simulation was made using d3js. Since javascript is asynchronous it is a perfect candidate to perform these simulations.

The next post extends this process with inhibitory vertices.

Number of vertices (n)
Expected degree (np), average number of neighbors
Activation threshold (K)
Probability of being in the bootstrap
Expected edge delay (seconds)

References

1. Einarsson, H., Lengler, J., Panagiotou, K., Mousset, F., & Steger, A. (2014). Bootstrap percolation with inhibition. ArXiv Preprint ArXiv:1410.3291.
2. Janson, S., Łuczak, T., Turova, T., & Vallier, T. (2012). Bootstrap percolation on the random graph G_ {n, p} . The Annals of Applied Probability, 22(5), 1989–2047.