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:

%!PS-Adobe-3.0
%%BoundingBox: 0 0 600 600
/theta 2 def
/T 100 def
/n 100 def
/seedprob .1 def
/size 600 def
/allpages false def


/t 0 def
/c size n div def
/rand01 { rand 2147483647 div } def
 
/m { moveto } bind def
/l { rlineto} bind def


/drawspread {
        0 1 n 1 sub { /y exch def
        0 1 n 1 sub { /x exch def
            spread x get y get dup T eq { pop 0 0 0 setrgbcolor } {
                T div /dd exch def
                dd 0.2 exp 0.3 mul
                dd 0.2 exp 0.6 mul
                dd 0.9 exp
                setrgbcolor
                x c mul y c mul m
                c 0 l 0 c l c neg 0 l closepath fill
            } ifelse
        } for
        } for
    0 0 0 setrgbcolor
    n 2 div c mul n c mul 10 add m
    t 10 string cvs 
    show
} def


 
/isfinite { exch oldspread exch get exch get T lt } bind def

/inccnt { cnt 1 add /cnt exch def } bind def

/neighbors { /y exch def /x exch def /cnt 0 def
    y 1 sub /y1 exch def y1 0 ge {x y1 isfinite { inccnt } if } if
    y 1 add /y1 exch def y1 n lt {x y1 isfinite { inccnt } if } if
    x 1 sub /x1 exch def x1 0 ge {x1 y isfinite { inccnt } if } if
    x 1 add /x1 exch def x1 n lt {x1 y isfinite { inccnt } if } if
    cnt
} bind def

%% /Helvetica findfont
%% 20 scalefont setfont

/iter {
    /moved 0 def
    % copy to oldspread
    0 1 n 1 sub { /x exch def 
        oldspread x get 0 spread x get putinterval
    } for
    t 1 add /t exch def
        0 1 n 1 sub { /x exch def
            0 1 n 1 sub { /y exch def
            oldspread x get y get T eq { 
                x y neighbors theta ge { 
                    spread x get y t put 
                    moved 1 add /moved exch def 
                } if
            } if
            } for 
    } for
} bind def

/oldspread [ n {[ n {T} repeat]} repeat ] def
/spread [ n {[ n { rand01 seedprob lt {0}{T} ifelse } repeat]} repeat ] def
T 1 add { 
    drawspread showpage 
    allpages { drawspread showpage } if
    iter moved 0 eq { exit } if t = 
} repeat
drawspread showpage 
%%EOF
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:
# using Imagemagick to build an animated gif
convert spread.ps spread.gif

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.