Bootstrap percolation on complex networks

• Published in: Physical review. E, Statistical, nonlinear, and soft matter physics Statistical, nonlinear, and soft matter physics, 2010-07, Vol.82 (1 Pt 1), p.011103-011103, Article 011103
• Main Authors: Baxter, G J, Dorogovtsev, S N, Goltsev, A V, Mendes, J F F
• Format: Article
• Language: English
• Subjects: Action Potentials - physiology; Animals; Computer Simulation; Feedback, Physiological - physiology; Humans; Models, Neurological; Nerve Net - physiology
• ISSN: 1539-3755; 1550-2376
• DOI: 10.1103/PhysRevE.82.011103

We consider bootstrap percolation on uncorrelated complex networks. We obtain the phase diagram for this process with respect to two parameters: f, the fraction of vertices initially activated, and p, the fraction of undamaged vertices in the graph. We observe two transitions: the giant active component appears continuously at a first threshold. There may also be a second, discontinuous, hybrid transition at a higher threshold. Avalanches of activations increase in size as this second critical point is approached, finally diverging at this threshold. We describe the existence of a special critical point at which this second transition first appears. In networks with degree distributions whose second moment diverges (but whose first moment does not), we find a qualitatively different behavior. In this case the giant active component appears for any f>0 and p>0, and the discontinuous transition is absent. This means that the giant active component is robust to damage, and also is very easily activated. We also formulate a generalized bootstrap process in which each vertex can have an arbitrary threshold.