A Central Limit Theorem for Diffusion in Sparse Random Graphs

• We consider bootstrap percolation and diffusion in sparse random graphs with fixed degrees, constructed by configuration model. Every vertex has two states: it is either active or inactive. We assume that to each vertex is assigned a nonnegative (integer) threshold. The diffusion process is initiated by a subset of vertices with threshold zero which consists of initially activated vertices, whereas every other vertex is inactive. Subsequently, in each round, if an inactive vertex with threshold theta has at least theta of its neighbours activated, then it also becomes active and remains so forever. This is repeated until no more vertices become activated. The main result of this paper provides a central limit theorem for the final size of activated vertices. Namely, under suitable assumptions on the degree and threshold distributions, we show that the final size of activated vertices has asymptotically Gaussian fluctuations.

Subject headings

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

NATURVETENSKAP  -- Matematik -- Sannolikhetsteori och statistik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Probability Theory and Statistics (hsv//eng)

Keyword

Contagion

Bootstrap percolation

Central limit theorem

Sparse random graphs

Publication and Content Type

ref (subject category)

art (subject category)