Abstract
A bootstrap percolation process on a graph G 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 r infected neighbours becomes infected and remains so forever. The parameter \(r\geqslant 2\) is fixed.
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 a(n) 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 2 < β < 3, 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 a c (n) such that a c (n) = o(n) with the following property. Assuming that n is the number of vertices of the underlying random graph, if a(n) ≪ a c (n), then the process does not evolve at all, with high probability as n grows, whereas if a(n) ≫ a c (n), then there is a constant ε > 0 such that, with high probability, the final set of infected vertices has size at least εn. This behaviour is in sharp contrast with the case where the underlying graph is a G(n,p) random graph with p = d/n. Recent results of Janson, Łuczak, Turova and Vallier have shown that if the number of initially infected vertices is sublinear, then with high probability the size of the final set of infected vertices is approximately equal to a(n). That is, essentially there is lack of evolution of the process.
It turns out that when the maximum degree is o(n 1/(β − 1)), then a c (n) depends also on r. But when the maximum degree is Θ(n 1/(β − 1)), then \(a_c (n)=n^{\beta -2 \over \beta -1}\).
L. Carroll The Hunting of the Snark.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Adler, J., Lev, U.: Bootstrap percolation: visualizations and applications. Brazilian Journal of Physics 33(3), 641–644 (2003)
Amini, H.: Bootstrap percolation and diffusion in random graphs with given vertex degrees. Electronic Journal of Combinatorics 17, R25 (2010)
Amini, H.: Bootstrap percolation in living neural networks. Journal of Statistcal Physics 141, 459–475 (2010)
Amini, H., Cont, R., Minca, A.: Resilience to contagion in financial networks (2011), preprint http://ssrn.com/abstract=1865997
Balogh, J., Bollobás, B.: Bootstrap percolation on the hypercube. Probability Theory and Related Fields 134(4), 624–648 (2006)
Balogh, J., Bollobás, B., Duminil-Copin, H., Morris, R.: The sharp threshold for bootstrap percolation in all dimensions. Trans. Amer. Math. Soc. 364, 2667–2701 (2012)
Balogh, J., Bollobás, B., Morris, R.: Bootstrap percolation in three dimensions. Annals of Probability 37, 1329–1380 (2009)
Balogh, J., Peres, Y., Pete, G.: Bootstrap percolation on infinite trees and non-amenable groups. Combinatorics, Probability and Computing 15(5), 715–730 (2006)
Balogh, J., Pittel, B.G.: Bootstrap percolation on the random regular graph. Random Structures & Algorithms 30(1-2), 257–286 (2007)
Bollobás, B.: Random Graphs. Cambridge studies in advanced mathematics, 2nd edn. Cambridge University Press (2001)
Bollobás, B., Janson, S., Riordan, O.: The phase transition in inhomogeneous random graphs. Random Structures & Algorithms 31(1), 3–122 (2007)
Cerf, R., Manzo, F.: The threshold regime of finite volume bootstrap percolation. Stochastic Processes and their Applications 101(1), 69–82 (2002)
Chalupa, J., Leath, P.L., Reich, G.R.: Bootstrap percolation on a Bethe lattice. Journal of Physics C: Solid State Physics 12, L31–L35 (1979)
Chung, F., Lu, L.: Connected components in random graphs with given expected degree sequences. Annals of Combinatorics 6, 125–145 (2002)
Chung, F., Lu, L.: The average distance in a random graph with given expected degrees. Internet Mathematics 1(1), 91–113 (2003)
Chung, F., Lu, L., Vu, V.: The spectra of random graphs with given expected degrees. Internet Mathematics 1(3), 257–275 (2004)
Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. In: SIGCOMM 1999: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, pp. 251–262 (1999)
Fontes, L., Schonmann, R.: Bootstrap percolation on homogeneous trees has 2 phase transitions. Journal of Statistical Physics 132, 839–861 (2008)
Gilbert, E.N.: Random graphs. Annals of Mathematical Statistics 30, 1141–1144 (1959)
Holroyd, A.E.: Sharp metastability threshold for two-dimensional bootstrap percolation. Probability Theory and Related Fields 125(2), 195–224 (2003)
Janson, S., Łuczak, T., Ruciński, A.: Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley Interscience, New York (2000)
Janson, S., Łuczak, T., Turova, T., Vallier, T.: Bootstrap percolation on the random graph G n,p . To Appear in The Annals of Applied Probability (2010), http://arxiv.org/abs/1012.3535
Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A.: Extracting large scale knowledge bases from the web. In: Proceedings of the 25th VLDB Conference, pp. 639–650 (1999)
Sabhapandit, S., Dhar, D., Shukla, P.: Hysteresis in the random-field Ising model and bootstrap percolation. Physical Review Letters 88(19), 197202 (2002)
Söderberg, B.: General formalism for inhomogeneous random graphs. Physical Review E 66, 066121 (2002)
Tlusty, T., Eckmann, J.P.: Remarks on bootstrap percolation in metric networks. Journal of Physics A: Mathematical and Theoretical 42, 205004 (2009)
Toninelli, C., Biroli, G., Fisher, D.S.: Jamming percolation and glass transitions in lattice models. Physical Review Letters 96(3), 035702 (2006)
van der Hofstad, R.: Random Graphs and Complex Networks (2011) (book in preparation), http://www.win.tue.nl/rhofstad/NotesRGCN2011.pdf
Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: KDD 2003: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146. ACM, New York (2003)
Chen, N.: On the approximability of influence in social networks. SIAM Journal on Discrete Mathematics 23(3), 1400–1415 (2009)
Kleinberg, J.: Cascading behavior in networks: algorithmic and economic issues. In: Algorithmic Game Theory, pp. 613–632. Cambridge University Press, Cambridge (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Amini, H., Fountoulakis, N. (2012). What I Tell You Three Times Is True: Bootstrap Percolation in Small Worlds. In: Goldberg, P.W. (eds) Internet and Network Economics. WINE 2012. Lecture Notes in Computer Science, vol 7695. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35311-6_34
Download citation
DOI: https://doi.org/10.1007/978-3-642-35311-6_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35310-9
Online ISBN: 978-3-642-35311-6
eBook Packages: Computer ScienceComputer Science (R0)