Bootstrap percolation

27 Mar 2016

If you have ever heard about percolation it might have been in the context of making coffee. That is, when brewing by filtering water through grinded coffee beans it is a desireable feature that the water can eventually pass through. Consequently the particles need to be large enough for the material to be porous and for the water to percolate through. This article is not about brewing coffee unless you want to get really creative but bear in mind that copious amounts of caffeine were part of its creative process regardless.

So what kind of percolation are you talking about then? Please explain like I’m five.

Imagine that your friend just got a new shiny toy. He shows it to you and you want it. You ask your parents but they say no. In time more of your friends get the toy and you still want it. Still your parents say no but they realise this will be a great gift and they buy the toy for your next birthday.

You probably already made the connection of how this short example relates to brewing coffee. If not let me explain. Think of yourself as an empty cell defined by the finely grained coffee bean particles around you. If it is not too disturbing you can think of your friends as adjacent cells. When one of your friends got a new toy in this analogy their cell was filled with water. For a single adjacent cell full of water the pressure is not sufficient for the water to enter your cell but once enough many adjacent cells get filled yours gets filled as well.

So you see, percolation has something to do with the dissemination of information in a network. Some other good examples are gossip and rumor spreading as well as advertising campaigns – it is important to know which individuals in a social network one should pay to advertise a product in order to reach as many potential customers as possible (you can start throwing your free products at me now). It is also valuable to know if a banking network is stable and how many individuals need to default on their loans for the network to collapse (Amini & Minca, 2014). Another great example is the spread of diseases. For every encounter with an infected individual the chances of becoming infected increase. My favorite example of bootstrap percolation is the way neurons communicate in the brain. Neurons communcate by sending spikes to their neighbors. If a neuron receives a couple of spike signals it will also spike and thus inform all of its neighbors, quite amazing. Finally percolation can be described by a cellular automaton which is the setting in which it was first studied (Chalupa, Leath, & Reich, 1979) (but motivated by physics) and since then it has been extensively studied on the grid in arbitrarily many dimensions (Balogh, Bollobás, Duminil-Copin, & Morris, 2012).

As you might have realised percolation is literally everywhere around us. It is therefore not surprising how interest in it has percolated. Below I will define more formally the process. This is where things start to get just slightly technical. In case you want to skip the technical parts just scroll down to the bottom of the article to play with the javascript simulation.

Bootstrap percolation (also known as iterative retrieval) is a simple model for the spread of activity in a graph/network. The vertices in the process have two states, either they are active or inactive. The process traditionally proceeds in rounds. Let K>0 be a threshold parameter. In any given round all inactive vertices turn active which have at least K active neighbours from previous rounds. Once a vertex turns active it remains active for the rest of the process. The bootstrap just refers to the set of initially active vertices and percolation refers to this spread of activity.

This is the most common definition but there are also some variations of the process which I will not cover in this post. When a vertex turns active in the description above you can think of it as the vertex telling all its neighbours that it turned active and this message takes one round to be delivered.

Generally the process is studied formally on some specific graph classes where as I mention above the lattice was the first candidate. I’ve been fortunate to work with some amazing people on a couple of projects involving bootstrap percolation (Einarsson, Lengler, Panagiotou, Mousset, & Steger, 2014) which will be the topic of a future post. Our study was sparked by the results by Janson, Luczak, Turova and Vallier (Janson, Łuczak, Turova, & Vallier, 2012) which analysed bootstrap percolation, the process above, on the Erdös Renyi random graph. The random graph is quite simple, each edge is present independently with some probability p which is a parameter of the model. For n vertices the expected number of neighbors is thus np. Janson et. al discovered that percolation has a threshold property on the random graph. If the bootstrap is below the threshold then almost no additional vertices turn active. But if it is above the threshold the activity percolates, that is almost every vertex turns active.

You can play with the process on the random graph below. The parameters can be chosen below and additionally you can turn the vertices between an active and an inactive state by clicking on them. The simulation was made with visjs and the code is available on my github page. Please note that at the moment the code scales quadratically in n so simulations for large values of n will be slow. Additionally the network layout has a hard time converging to a stable state when there are many vertices and the graph is not sparse.

The next post discusses a variation of the process which is not round based.

Number of vertices (n)
Expected degree (np), average number of neighbors
Activation threshold (K)
Probability of being in the bootstrap
Time step length in milliseconds (1000 ms = 1 second)

Acknowledgements

Thanks to Guðmundur for reading a draft of this post.

References

1. Amini, H., & Minca, A. (2014). Inhomogeneous Financial Networks and Contagious Links. Available at SSRN.
2. Chalupa, J., Leath, P. L., & Reich, G. R. (1979). Bootstrap percolation on a Bethe lattice. Journal of Physics C: Solid State Physics, 12(1), L31.
3. Balogh, J., Bollobás, B., Duminil-Copin, H., & Morris, R. (2012). The sharp threshold for bootstrap percolation in all dimensions. Transactions of the American Mathematical Society, 364(5), 2667–2701.
4. Einarsson, H., Lengler, J., Panagiotou, K., Mousset, F., & Steger, A. (2014). Bootstrap percolation with inhibition. ArXiv Preprint ArXiv:1410.3291.
5. 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.