Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Bootstrap Percolation in Power-Law Random Graphs
 
research article

Bootstrap Percolation in Power-Law Random Graphs

Amini, Hamed
•
Fountoulakis, Nikolaos
2014
Journal Of Statistical Physics

A bootstrap percolation process on a graph is an "infection" process which evolves in rounds. Initially, there is a subset of infected nodes and in each subsequent round each uninfected node which has at least infected neighbours becomes infected and remains so forever. The parameter is fixed. Such processes have been used as models for the spread of ideas or trends within a network of individuals. We analyse this process in the case where the underlying graph is an inhomogeneous random graph, which exhibits a power-law degree distribution, and initially there are randomly infected nodes. The main focus of this paper is the number of vertices that will have been infected by the end of the process. The main result of this work is that if the degree sequence of the random graph follows a power law with exponent , where , then a sublinear number of initially infected vertices is enough to spread the infection over a linear fraction of the nodes of the random graph, with high probability. More specifically, we determine explicitly a critical function such that with the following property. Assuming that is the number of vertices of the underlying random graph, if , then the process does not evolve at all, with high probability as grows, whereas if , then there is a constant such that, with high probability, the final set of infected vertices has size at least . This behaviour is in sharp contrast with the case where the underlying graph is a random graph with . It follows from an observation of Balogh and Bollobas that in this case if the number of initially infected vertices is sublinear, then there is lack of evolution of the process. It turns out that when the maximum degree is , then depends also on . But when the maximum degree is , then .

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

10955_2014_Article_946.pdf

Type

Publisher's Version

Version

http://purl.org/coar/version/c_970fb48d4fbd8a85

Access type

openaccess

Size

274.15 KB

Format

Adobe PDF

Checksum (MD5)

b68096366e6b68d306d7665367158391

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés