Percolation with inhibition - part 1

25 Apr 2016

In the previous posts we have discussed synchronous and asynchronous bootstrap percolation, processes which model the dissemination of information in a graph.

In these previous models we only studied vertices which could excite their neighbours. This is a good basic model for the spread of diseases or gossip. However in other settings we might instead have competing forces. For instance the messages might represent product recommendations from friends. If all your friends recommend some brand you might be triggered to buy it. However, if some of your friends recommend another you might change your decision on what to buy or simply be confused. Similarly in the brain some of the neurons are excitatory and send positive messages while others are inhibitory and send negative messages. The inhibitory neurons are quite important because if excitation is abundant the activity can run out of control which can lead to epileptic seizures.

Thus it becomes natural to study the question what happens if instead we allowed some of the nodes to be negative? That is exactly what we did in (Einarsson, Lengler, Panagiotou, Mousset, & Steger, 2014). We made some interesting observations which I will highlight in follow up posts.

Below you can see an implementation of asynchronous bootstrap percolation with inhibition made with d3js. The green nodes send positive messages and the red nodes send negative messages. Each vertex keeps track of how many positive messages it has seen minus the number of negative vertices. We refer to this as the potential of the vertex. A vertex turns active (and remains active) if its potential ever reaches $K$. You can try to control which fraction of the green vertices turn active by changing the number of negative vertices. When the potential of a vertex becomes negative we color the vertex blue. Vertices which reach this state have a lower chance of ever turning active. They can but for most of them they are essentially frozen.

Number of positive vertices (green)
Number of negative vertices (red)
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.