Insights into bootstrap percolation: Its equivalence with k-core percolation and the giant component

Matías A. Di Muro, Lucas D. Valdez, H. Eugene Stanley, Sergey V. Buldyrev, and Lidia A. Braunstein
Phys. Rev. E 99, 022311 – Published 21 February 2019

Abstract

K-core and bootstrap percolation are widely studied models that have been used to represent and understand diverse deactivation and activation processes in natural and social systems. Since these models are considerably similar, it has been suggested in recent years that they could be complementary. In this manuscript we provide a rigorous analysis that shows that for any degree and threshold distributions heterogeneous bootstrap percolation can be mapped into heterogeneous k-core percolation and vice versa, if the functionality thresholds in both processes satisfy a complementary relation. Another interesting problem in bootstrap and k-core percolation is the fraction of nodes belonging to their giant connected components Pb and Pc, respectively. We solve this problem analytically for arbitrary randomly connected graphs and arbitrary threshold distributions, and we show that Pb and Pc are not complementary. Our theoretical results coincide with computer simulations in the limit of very large graphs. In bootstrap percolation, we show that when using the branching theory to compute the size of the giant component, we must consider two different types of links, which are related to distinct spanning branches of active nodes.

  • Figure
  • Figure
  • Figure
  • Figure
  • Received 13 November 2018

DOI:https://doi.org/10.1103/PhysRevE.99.022311

©2019 American Physical Society

Physics Subject Headings (PhySH)

Networks

Authors & Affiliations

Matías A. Di Muro*

  • Instituto de Investigaciones Físicas de Mar del Plata (IFIMAR)-Departamento de Física, Facultad de Ciencias Exactas y Naturales, Universidad Nacional de Mar del Plata-CONICET, Funes 3350, (7600) Mar del Plata, Argentina

Lucas D. Valdez and H. Eugene Stanley

  • Center for Polymer Studies, Boston University, Boston, Massachusetts 02215, USA

Sergey V. Buldyrev

  • Department of Physics, Yeshiva University, 500 West 185th Street, New York, New York 10033, USA and Politecnico di Milano, Department of Management, Economics and Industrial Engineering, Via Lambruschini 4, BLD 26, 20156 Milano, Italy

Lidia A. Braunstein

  • Instituto de Investigaciones Físicas de Mar del Plata (IFIMAR)-Departamento de Física, Facultad de Ciencias Exactas y Naturales, Universidad Nacional de Mar del Plata-CONICET, Funes 3350, (7600) Mar del Plata, Argentina and Center for Polymer Studies, Boston University, Boston, Massachusetts 02215, USA

  • *mdimuro@mdp.edu.ar

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 99, Iss. 2 — February 2019

Reuse & Permissions
Access Options
CHORUS

Article Available via CHORUS

Download Accepted Manuscript
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×