PhilippeBlanchard, Tyll
Krueger
Overview

Complex dynamics with threshold: SOC,generalized epidemic and percolation
processes

Percolation
Bootstrap
percolation
inhomogeneous
random graphmodelsapplications

Philippe Blanchard, Tyll Krueger

Bangalore 2011

Overview

PhilippeBlanchard, Tyll
Krueger
Overview
Percolation

1. classical percolation
2. bootstrap percolation
3. SOC versus bootstrap
4. bootstrap on Erdös&Renyi
5. BJR graphs
6. bootstrap on BJR graphs
7. some applications

Bootstrap
percolation
inhomogeneous
random graphmodelsapplications

What is percolation?

PhilippeBlanchard, Tyll
Krueger
Overview
Percolation
Bootstrap
percolation
inhomogeneous
random graphmodelsapplications

real life percolation

PhilippeBlanchard, Tyll
Krueger
Overview
Percolation
Bootstrap
percolation
inhomogeneous
random graphmodelsapplications

Percolation
I studied since 1957 (Broadbent&Hammersley)
I on the Z2
lattice graph:
Iwith prob. p keep edges
I with prob 1
p remove edges
I the resulting object is a random subgraph ΛpZ2
I percolation question: is there an in…nite connected
subgraph of Λp
I Theorem:

9 pc 2 (0, 1) such that(1)for p < pc ) with prob 1 no in…nite cluster (2)for p > pc ) with prob 1 is an in…nite cluster (3)I Kesten 1980: pc = 1/2
I the above model is called bond percolation
I removing/keeping sites instead of edges de…nes site

percolation

PhilippeBlanchard, Tyll
Krueger
Overview
Percolation
Bootstrap
percolation
inhomogeneous
random graphmodelsapplications

some pictures

Philippe
Blanchard, Tyll
Krueger
Overview
Percolation
Bootstrap
percolation
inhomogeneous
random graphmodelsapplications

PhilippeBlanchard, Tyll
Krueger
OverviewPercolation
Bootstrap
percolation
inhomogeneous
random graphmodelsapplications

variants of the classical percolation problem
I di¤erent lattices Zn with di¤erent neighborhood

structure
I random graphs
Igiant component
1
I on complete graph K
N : pc = N
I on trees it is closely related to critical branchingprocesses
I continuum percolation
I directed percolation
I …rst passage percolation
I for all these generalizations is a critical threshold pc

Philippe
Blanchard, Tyll
Krueger
Overview
Percolation
Bootstrap
percolation
inhomogeneous
random graphmodelsapplicationsPhilippeBlanchard, Tyll
Krueger
Overview

I very active …eld of research

Percolation

I many open questions

Bootstrap
percolation

I

what happens at pc
I how to determine pc
I theory is well developed for lattices in high dimensions
I applications:IImaterial science (erosion of materials)
spreading phenomena: forest …re, epidemics,....

inhomogeneous
random graphmodelsapplications

The origin of the nameI the American version of "the adventures of Baron

Münchhausen"
I the Baron pulled himself out of a swamp by hisbootstraps (on his hairs in the German version)

PhilippeBlanchard, Tyll
Krueger
Overview
Percolation
Bootstrap
percolation
inhomogeneous
random graphmodelsapplications

IBootstrap percolation

PhilippeBlanchard, Tyll
Krueger
Overview

I two states 0 and 1 (infected)

Percolation

I infect initially at random vertices with probability p0

Bootstrap
percolation

I infected vertices remain infected foreverI deterministic discrete dynamics: vertex gets infected if

it has∆ infected neighbors

I how large is the …nally infected set?
I studied in physics literature since 70s (mainly dualprocess)I mainly studied on lattices, hypercube(Balogh,Bollobas,Morris 2009) and regular trees(Biskup, Schoneman 2009)

inhomogeneous
random graphmodelsapplications

some bootstrap percolation pictures

PhilippeBlanchard, Tyll
Krueger
Overview
Percolation
Bootstrap
percolation
inhomogeneous
random graphmodelsapplications

PhilippeBlanchard, Tyll
Krueger
Overview
Percolation
Bootstrap
percolation
inhomogeneous
random graphmodelsapplications

SOC versus Bootstrap
I Formal similarities:

PhilippeBlanchard, Tyll
Krueger

IOverview

IPercolation

local dynamics highly nonlinear e.g. threshold functionSOC: if "infection" of site is larger ∆ ) infect neighbors
I Boot: if "infection" of neighbors is larger ∆ ) infectsite
I this is a kind of local duality
I Di¤erences:I

SOC is not restricted to local threshold dynamics(example: Bak&Sneppen model of puncturedequilibrium)
I in general SOC is : a dynamical balance betweenIII

triggering the system slowly
dissipation at small set/boundary

this can cause the system to stabilize at a critical state(phase transition)
I to make Bootstrap-SOC one would have to include suche¤ects (loss of infection + feed in of infection)
I possible candidate: competing bootstrap infections

Bootstrap
percolation
inhomogeneous
random graphmodelsapplications

Bootstrap percolation on regular trees

PhilippeBlanchard, TyllKrueger

I …nd pc s.t. for p > pc the whole dtree becomes
infected eventually with probability one
I ∆ = 2, d > 3 : (Blanchard, Krueger 2005) and(Balogh,Peres,Pete 2006):
pc = 1(d(d 2)2d 51)d 2 (d 3)d 3

Overview
Percolation
Bootstrap
percolation(4)

I for random trees with GF g (z ) and min-outdegree∆ = 2 : pc = 1 q where q 2 (0, 1) is the smallest
value s.t. the following equation has a real positivesolutionz= (1 z ) g 0 (z ) + g (z )(5)q(Blanchard,Krueger 2005)
I similar results for regular random graphs (Balogh,Pittel2007)

inhomogeneous
random graphmodelsapplications

Bootstrap on fat trees

PhilippeBlanchard, Tyll
Krueger
Overview

I local clustering accelerates the infection spread (inclassical epidemics clustering slows down the spread)pI pcfat = 3
2 < pctree = 192IPercolation
Bootstrap
percolation
inhomogeneous
random graphmodelsapplications

generalized tree; the grey
vertices where inital black
but got eventually corrupt(local threshold =2)4-tree with initialwhite and black
vertices

Bootstrap on Erdös&Renyi graphs
I for G

Philippe
Blanchard, Tyll
Kruegern, p = nc one has

Overview
Percolation

st + 1 = 1p0 ) e cst(1l =∆ 1∑

l =0= 1(cst )ll!

p0 ) Pr fPois (cst ) < ∆g(1(6)(7)

I for ∆ = 2pc = 1c1
12+2c1+c12ppc2c 2 3 2c )(8)
3I the critical window around pc is of order n2c12

inhomogeneous
random graphmodelsapplications

I there is at most one critical pc

2e (Bootstrap
percolation

Dynamics at the critical density

Philippe
Blanchard, Tyll
Krueger

I Example: p0 = 0.08, c = 3.2, ∆ = 2yOverview

1

Percolation
Bootstrap
percolation

0 .7 5inhomogeneous
random graphmodelsapplications

0.5

0 .2 5000 .2 5

0.50 .7 51xI around pc long transient phases
I for p0 > p c : s is close to the ∆0core of the graphabove and below the critical densityyPhilippe
Blanchard, Tyll
Krueger

10.75

Overview
Percolation

0.5

Bootstrap
percolation
0.25

inhomogeneous
random graphmodels

00

0.25

0.5

0.75

1x

y

1

0.75

0.5

0.25

000.25

0.5

0.75

1x

applications

The …xed point set as a function of the initial
density (c=4)

Philippe
Blanchard, Tyll
Krueger
Overview

1

Percolation

0.9

Bootstrap
percolation

y0.8

inhomogeneous
random graphmodels0.7

applications

0.6
0.5
0.4
0.30.20.10-0.25-0.12500.125

0.25

0.375

0.5

0.625

0.75

0.875

1xBollobas-Janson-Riordan graphs (2005)
I generalizations of Erdös-Renyi graphs
I good balance between simpli…cation and complexity
I provide gauge models for more real life graph models
I inhomogeneous in vertex properties but independentedges
I exact mathematical estimations for many graphproperties possible
I some parts of theory easy to extend to weighted graphs
I includes also evolving graphs
I appropriate for SIR processes with individual dependent

infection ratesPhilippeBlanchard, Tyll
Krueger
Overview
Percolation
Bootstrap
percolation
inhomogeneous
random graphmodelsapplications

general setting for BJR graphs

PhilippeBlanchard, Tyll
Krueger
Overview
Percolation

I the n vertices have properties f ω i g with values in

Bootstrap
percolation

ground space S

inhomogeneous
random graphmodelsI the values f ω i g are asymptotically µ distributed

I the edge probabilities for vertices of given types areapplications

independent and de…ned via a kernel κPr (ij) =κ (ω i , ω j )n(9)the giant component

PhilippeBlanchard, Tyll
Krueger

I let ρ ( ω ) =Overview
Percolation

Pr fPoisson process starting with type ω survivesg
IBootstrap
percolationρ (ω ) is solution offwith Tf (ω )Tf= 1e=κ (ω, η ) f (η ) d µ (η )ZI the giant component is given by nR(10)(11)ρ (ω ) d µ (ω )(vertices where the associated Poisson process does notdie out join the giant component

I threshold: kT k = 1 =) for kT k = ∞ no epidemic

threshold!

inhomogeneous
random graphmodelsapplications

Bootstrap percolation on BJR graphs

PhilippeBlanchard, TyllKrueger

I Let κ ( ω, η ) be of …nite type

Overview

I Theorem (Bl,D,Kr,S-S 2010):
IPercolation

Letfrom a …nite critical set
n p0 be disjoint
opc1 , ...., pcl , and let S be the asymptotic size of thebootstrap process
on G (n, κ, µ): whp S = ns + o (n)Rwhere s = s (ω ) d µ (ω ) and s (ω ) is the smallest
solution > p0 ofs (ω )= 1(1l =∆ 1∑l =0p0 ) e
1l!

ZRκ ( ω ,η )s ( η )d µ ( η )l[κ (ω, η ) s (η )] d µ (η )!

I Remark: For ∆ = 1 and p0 & 0 the formula reduces tothe survival probability for the associated Poissonprocess

Bootstrap
percolation
inhomogeneous
random graphmodelsapplications

generalized epidemic processes

PhilippeBlanchard, Tyll
KruegerI the states of infection are encoded by a …nite alphabet
Ie.g.

n0 , not infected, 1 , infected, 2 , immune

oI the infection process takes place on a graph G (V , E )the dynamics is de…ned via local transition probabilitiese.g.:Pr χi (t + 1) = k j χi (t ) = k 0= floc χB 1 (i ) (t )III

Bootstrap
percolation
inhomogeneous
random graphmodelsalong edges e 2 EI

Overview
Percolation

fmean (χG (t ))

(12)
(13)

B1 (i ) : set of neighbors of i + vertex iχ (t ) : state function at time tclassical assumption on floc : the infection events alongedges are independent

applications

local threshold processes as bootstrap percolation
I infection events along edges no longer independent
Iin many applications there are local thresholds ∆ (i )# infected neighbors< ∆ (i ) :=) small infection rate εPhilippeBlanchard, Tyll
Krueger
Overview
Percolation
Bootstrap
percolation
inhomogeneous
random graphmodelsapplications# infected neighbors=)∆ (i ) :high infection rate αI ε = 0, α = 1 corresponds to bootstrap percolation
I examples: neuron dynamics, corruption, prejudices,knowledge spread, opinion spreadradical opinion formation and terrorism

PhilippeBlanchard, Tyll
Krueger
Overview

I …rst studied by S.Galam in 2002 as a classicalpercolation problem
I his model: terrorist wants to move (spatially, on alattice) from A to B
I he needs to follow a "continuos" path of passive

supporters
I the lattice is determined by social dimension
I below pc : terrorism is regionally restricted
I above pc : terrorism becomes a global phenomena

Percolation
Bootstrap
percolation
inhomogeneous
random graphmodelsapplications

the war in Afghanistan

Philippe
Blanchard, Tyll
Krueger
Overview
Percolation
Bootstrap
percolation
inhomogeneous
random graphmodelsapplications

passive supporters and terrorism
I Q: what is the e¤ect of "collateral damages" on theprevalence of passive supporters?
I

example: Afghanistan

I Warning:I

it is not a real life approximation
I the model shows a possible qualitative dynamic process
I assume that on average:Ito capture/eliminate an active terrorist causes m civilianvictims
I relatives/friends of victims are likely to become passive
supporters (state 1)
I hence a counter terrorist action induces about rm new

passive supportersI

typically rm

101000PhilippeBlanchard, Tyll
Krueger
Overview
Percolation
Bootstrappercolation
inhomogeneous
random graphmodelsapplications