# Alfredo Braunstein

/home /code /teaching /research /rand

The k-LTM dynamics or (Bootstrap percolation dynamics) is defined as follows. At every time $$t\in\mathbb N_0$$. each node $$i$$ on a graph can be in one of two states $$x_i^t\in \{0,1\}$$. Once a node becomes 1, it will never go back, i.e. $$x_i^{t+1}\geq x_i^t$$. A node will become 1 if it has at least k neighbors that are 1. The dynamics is specified then as: $x_i^{t+1}=\mathbb{I}(\sum_{j\in\partial i} x_j^t \geq k(1-x_i^t))$

The following Postscript code simulates the spread dynamics on a square lattice starting by a random configuration at time 0. You can adjust the parameters by just editing the first lines of the postscript file: theta (k), n (side of the lattice), T (final time), seedprob (independent probability of being 1 at time t=0). By flipping rapidly through the 100 printed pages you would see something like this:

Postscript code:

Warning! Real printing not advised. This code, although being less than two kilobytes long, produces T=100 pages of output! Did you know that Postscript is a real programming language? If you are as environment friendly as I am, you will save a rainforest or two by running the following command instead of printing the Postscript file:

Of course, initial conditions need not to be random. One could seek such conditions with the smallest possible number of 1s such that the propagation still covers the full graph. Can you guess what is the optimal solution for the case above (k=2)? We investigated this issue, in order to solve the important problem of producing the following carpet designs (here k=3):

or for an hexagonal lattice (each site has six neighbors) with k=5:

See more serious results on random graphs, and an application to viral marketing: slides, [1; 2]

1. Altarelli, F, Braunstein, A, Dall’Asta, L, and Zecchina, R, 2013, “Optimizing spread dynamics on graphs by message passing” J. Stat. Mech. 2013(09) P09011, http://iopscience.iop.org/1742-5468/2013/09/P09011.
2. Altarelli, F, Braunstein, A, Dall’Asta, L, and Zecchina, R, 2013, “Large deviations of cascade processes on graphs” Phys. Rev. E 87(6) 062115, http://link.aps.org/doi/10.1103/PhysRevE.87.062115.