CoChat
Sign Up
Cited by 18Complex Network Analysis TechniquesTheoretical and Computational PhysicsStochastic processes and statistical mechanics

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

Open access
Di Muro, Matías A., Valdez, Lucas D., Stanley, H. Eugene, Buldyrev, Sergey V., Braunstein, Lidia A.·2019·Physical Review E
DOI 10.1103/physreve.99.022311
Open this paper in CoChat — free accountOpen PDF

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 P_{∞b} and P_{∞c}, respectively. We solve this problem analytically for arbitrary randomly connected graphs and arbitrary threshold distributions, and we show that P_{∞b} and P_{∞c} 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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1103/physreve.99.022311

Cites

30 of 30 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 27

  1. [1]1. M. Granovetter, Am. J. Sociol. 83, 1420 (1978).
  2. [2]2. S. Morris, Rev. Econ. Stud. 67, 57 (2000).
  3. [5]5. D. J. Watts, Proc. Natl. Acad. Sci. U.S.A. 99, 5766 (2002).
  4. [6]6. K.-M. Lee, C. D. Brummitt, and K.-I. Goh, Phys. Rev. E 90, 062816 (2014).
  5. [7]7. G. Bizhani, M. Paczuski, and P. Grassberger, Phys. Rev. E 86, 011128 (2012).
  6. [8]8. D. Cellai, A. Lawlor, K. A. Dawson, and J. P. Gleeson, Phys. Rev. E 87, 022134 (2013).
  7. [9]9. W. Wang, M. Tang, P. Shu, and Z. Wang, New J. Phys. 18, 013029 (2016).
  8. [10]10. B. Mønsted, P. Sapieżyński, E. Ferrara, and S. Lehmann, PLoS One 12, e0184148 (2017).
  9. [11]11. D. Centola, Science 329, 1194 (2010).
  10. [12]12. S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Phys. Rev. Lett. 96, 040601 (2006).
  11. [13]13. D. Cellai, A. Lawlor, K. A. Dawson, and J. P. Gleeson, Phys. Rev. Lett. 107, 175703 (2011).
  12. [14]14. G. J. Baxter, S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Phys. Rev. E 83, 051134 (2011).
  13. [15]15. J. Adler and A. Aharony, J. Phys. A: Math. Gen. 21, 1387 (1988).
  14. [16]16. G. J. Baxter, S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Phys. Rev. E 82, 011103 (2010).
  15. [17]17. D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. Lett. 85, 5468 (2000).
  16. [18]18. M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. E 64, 026118 (2001).
  17. [19]19. M. E. J. Newman, Phys. Rev. E 66, 016128 (2002).
  18. [20]20. L. A. Braunstein, Z. Wu, Y. Chen, S. V. Buldyrev, T. Kalisky, S. Sreenivasan, R. Cohen, E. López, S. Havlin, and H. E. Stanley, Int. J. Bifurc. Chaos 17, 2215 (2007).
  19. [21]21. K. Chung, Y. Baek, D. Kim, M. Ha, and H. Jeong, Phys. Rev. E 89, 052811 (2014).
  20. [22]22. J. C. Miller, J. Complex Netw. 4, 201 (2015).
  21. [23]23. J. P. Gleeson and D. J. Cahalane, Phys. Rev. E 75, 056103 (2007).
  22. [24]24. J. Lorenz, S. Battiston, and F. Schweitzer, Eur. Phys. J. B 71, 441 (2009).
  23. [25]25. R. Pastor-Satorras, C. Castellano, P. Van Mieghem, and A. Vespignani, Rev. Mod. Phys. 87, 925 (2015).
  24. [26]26. J. C. Miller, Phys. Rev. E 94, 032313 (2016).
  25. [27]27. S. Janson et al., Electron. J. Probab. 14, 86 (2009).
  26. [28]28. M. A. Di Muro, L. D. Valdez, H. H. Aragão Rêgo, S. V. Buldyrev, H. E. Stanley, and L. A. Braunstein, Sci. Rep. 7, 15059 (2017).
  27. [29]29. M. Molloy and B. Reed, Combinator., Probab. Comput. 7, 295 (1998).

Cited by

Sorted by citations

Related

Authors
Di Muro, M. A., Valdez, L. D., Stanley, H. E., Buldyrev, S. V., & Braunstein, L. A.
Affiliations
  • Boston University (US)
  • Consejo Nacional de Investigaciones Científicas y Técnicas (AR)
ORCID
Venue
Physical Review E
Publisher
American Physical Society (APS)
Published
2019-02-21
Volume
99
Issue
2
Pages
022311-022311
ISSN
  • 2470-0045 (ISSN-L)
  • 2470-0053
DOI
10.1103/physreve.99.022311
OpenAlex
W2900364084
Semantic Scholar
0c96eeac2b80b5255889e5bdc3d82febd3dad97d
Cited by
18
References
30
Citations by year
2026: 1 · 2025: 2 · 2024: 2 · 2023: 4 · 2022: 1 · 2021: 2 · 2020: 5 · 2019: 1
FWCI
1.04
Type
journal article
Language
en
Open access
Licence
Locations
  • Physical review. E (publishedVersion)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) (submittedVersion, cc-by)
  • arXiv (Cornell University)
Funders
  • Universidad Nacional de Mar del Plata (EXA 853/18)
  • Consejo Nacional de Investigaciones Científicas y Técnicas (PIP 00443/2014)
  • National Science Foundation (PHY-1505000, CMMI-1125290, CHE-1213217)
  • Defense Threat Reduction Agency (HDTRA1-14-1-0017)
Topics
  • Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
  • Physical Sciences › Physics and Astronomy › Condensed Matter Physics › Theoretical and Computational Physics
  • Physical Sciences › Mathematics › Mathematical Physics › Stochastic processes and statistical mechanics
Keywords
bootstrap percolation, k-core percolation, giant component, threshold distribution, branching theory

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review