Document Open Access Logo

Bootstrap Percolation on Geometric Inhomogeneous Random Graphs

Authors Christoph Koch, Johannes Lengler

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.147.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Christoph Koch
Johannes Lengler

Cite As Get BibTex

Christoph Koch and Johannes Lengler. Bootstrap Percolation on Geometric Inhomogeneous Random Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 147:1-147:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.147

Abstract

Geometric inhomogeneous random graphs (GIRGs) are a model for scale-free networks with underlying geometry. We study bootstrap percolation on these graphs, which is a process modelling the spread of an infection of vertices starting within a (small) local region. We show that the process exhibits a phase transition in terms of the initial infection rate in this region. We determine the speed of the process in the supercritical case, up to lower order terms, and show that its evolution is fundamentally influenced by the underlying geometry. For vertices with given position and expected degree, we determine the infection time up to lower order terms. Finally, we show how this knowledge can be used to contain the infection locally by removing relatively few edges from the graph. This is the first time that the role of geometry on bootstrap percolation is analysed mathematically for geometric scale-free networks.

Subject Classification

Keywords
  • Geometric inhomogeneous random graphs
  • scale-free network
  • bootstrap percolation
  • localised infection process
  • metastability threshold

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Joan Adler and Uri Lev. Bootstrap percolation: visualizations and applications. Brazilian Journal of Physics, 33(3):641-644, 2003. Google Scholar
  2. William Aiello, Anthony Bonato, Colin Cooper, Jeanette Janssen, and Paweł Prałat. A spatial web graph model with local influence regions. Internet Mathematics, 5(1-2):175-196, 2008. Google Scholar
  3. Michael Aizenman and Joel Lebowitz. Metastability effects in bootstrap percolation. Journal of Physics A: Mathematical and General, 21(19):3801, 1988. Google Scholar
  4. Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002. Google Scholar
  5. Hamed Amini. Bootstrap percolation in living neural networks. Journal of Statistical Physics, 141(3):459-475, 2010. Google Scholar
  6. Hamed Amini, Rama Cont, and Andreea Minca. Resilience to contagion in financial networks. Mathematical Finance, 26(2):329-365, 2016. Google Scholar
  7. Hamed Amini and Nikolaos Fountoulakis. Bootstrap percolation in power-law random graphs. Journal of Statistical Physics, 155(1):72-92, 2014. Google Scholar
  8. József Balogh, Béla Bollobás, Hugo Duminil-Copin, and Robert Morris. The sharp threshold for bootstrap percolation in all dimensions. Transactions of the American Mathematical Society, 364(5):2667-2701, 2012. Google Scholar
  9. József Balogh, Yuval Peres, and Gábor Pete. Bootstrap percolation on infinite trees and non-amenable groups. Combinatorics, Probability and Computing, 15(05):715-730, 2006. Google Scholar
  10. Albert-László Barabási. Network science: Luck or reason. Nature, 489(7417):507-508, 2012. Google Scholar
  11. Gareth Baxter, Sergey Dorogovtsev, Alexander Goltsev, and José Mendes. Bootstrap percolation on complex networks. Physical Review E, 82(1):011103, 2010. Google Scholar
  12. Marián Boguñá, Dmitri Krioukov, and Kimberly Claffy. Navigability of complex networks. Nature Physics, 5(1):74-80, 2009. Google Scholar
  13. Marián Boguñá, Fragkiskos Papadopoulos, and Dmitri Krioukov. Sustaining the internet with hyperbolic mapping. Nature communications, 1:62, 2010. Google Scholar
  14. Milan Bradonjić and Iraj Saniee. Bootstrap percolation on random geometric graphs. Probability in the Engineering and Informational Sciences, 28(02):169-181, 2014. Google Scholar
  15. Karl Bringmann, Ralph Keusch, and Johannes Lengler. Geometric inhomogeneous random graphs. arXiv:1511.00576, 2015. Google Scholar
  16. Karl Bringmann, Ralph Keusch, and Johannes Lengler. Average distance in a general class of scale-free graphs with underlying geometry. arXiv:1602.05712, 2016. Google Scholar
  17. Elisabetta Candellero and Nikolaos Fountoulakis. Bootstrap percolation and the geometry of complex networks. Stochastic Processes and their Applications, 126(1):234-264, 2016. Google Scholar
  18. Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, and Eran Shir. A model of internet topology using k-shell decomposition. Proceedings of the National Academy of Sciences, 104(27):11150-11154, 2007. Google Scholar
  19. Damon Centola. The spread of behavior in an online social network experiment. Science, 329(5996):1194-1197, 2010. Google Scholar
  20. John Chalupa, Paul Leath, and Gary Reich. Bootstrap percolation on a bethe lattice. Journal of Physics C: Solid State Physics, 12(1):L31-L35, 1979. Google Scholar
  21. Or Cohen, Anna Keselman, Elisha Moses, Rodríguez Martínez, Jordi Soriano, and Tsvi Tlusty. Quorum percolation in living neural networks. EPL (Europhysics Letters), 89(1):18008, 2010. Google Scholar
  22. Colin Cooper, Alan Frieze, and Paweł Prałat. Some typical properties of the spatial preferred attachment model. In Anthony Bonato and Jeannette Janssen, editors, Algorithms and Models for the Web Graph: 9th International Workshop, WAW 2012, Halifax, NS, Canada, June 22-23, 2012. Proceedings, pages 29-40, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  23. Sergey Dorogovtsev, Alexander Goltsev, and José Mendes. K-core organization of complex networks. Physical review letters, 96(4):040601, 2006. Google Scholar
  24. Sergey Dorogovtsev and José Mendes. Evolution of networks. Advances in Physics, 51(4):1079-1187, 2002. Google Scholar
  25. Paul Dreyer and Fred Roberts. Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion. Discrete Applied Mathematics, 157(7):1615-1627, 2009. Google Scholar
  26. Hafsteinn Einarsson, Johannes Lengler, Konstantinos Panagiotou, Frank Mousset, and Angelika Steger. Bootstrap percolation with inhibition. arXiv:1410.3291, 2014. Google Scholar
  27. Hafsteinn Einarsson, Johannes Lengler, and Angelika Steger. A high-capacity model for one shot association learning in the brain. Frontiers in Computational Neuroscience, 8(140), 2014. Google Scholar
  28. Paola Flocchini, Elena Lodi, Fabrizio Luccio, Linda Pagli, and Nicola Santoro. Dynamic monopolies in tori. Discrete applied mathematics, 137(2):197-212, 2004. Google Scholar
  29. Jian Gao, Tao Zhou, and Yanqing Hu. Bootstrap percolation on spatial networks. Scientific Reports, 5:14662, 2015. Google Scholar
  30. Allen Gersho and Debasis Mitra. A simple growth model for the diffusion of a new communication service. Systems, Man and Cybernetics, IEEE Transactions on, SMC-5(2):209-216, March 1975. Google Scholar
  31. Mark Granovetter. Threshold models of collective behavior. American Journal of Sociology, 83(6):1420-1443, 1978. Google Scholar
  32. Mark S. Granovetter. The strength of weak ties. American Journal of Sociology, 78(6):1360-1380, 1973. Google Scholar
  33. Randi Griffin and Charles Nunn. Community structure and the spread of infectious disease in primate social networks. Evolutionary Ecology, 26(4):779-800, 2012. Google Scholar
  34. Wei Huang and Chunguang Li. Epidemic spreading in scale-free networks with community structure. Journal of Statistical Mechanics: Theory and Experiment, 2007(01):P01014, 2007. Google Scholar
  35. Emmanuel Jacob and Peter Mörters. Spatial preferential attachment networks: Power laws and clustering coefficients. The Annals of Applied Probability, 25(2):632-662, 2015. Google Scholar
  36. Svante Janson, Tomasz Łuczak, Tatyana Turova, and Thomas Vallier. Bootstrap percolation on the random graph G(n, p). The Annals of Applied Probability, 22(5):1989-2047, 2012. Google Scholar
  37. Jeannette Janssen and Abbas Mehrabian. Rumours spread slowly in a small world spatial network. In F. David Gleich, Júlia Komjáthy, and Nelly Litvak, editors, Algorithms and Models for the Web Graph: 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015, Proceedings, pages 107-118, Cham, 2015. Springer International Publishing. Google Scholar
  38. Amin Karbasi, Johannes Lengler, and Angelika Steger. Normalization phenomena in asynchronous networks. In M. Magnús Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, pages 688-700, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. Google Scholar
  39. Scott Kirkpatrick, Winfried Wilcke, Robert Garner, and Harald Huels. Percolation in dense storage arrays. Physica A: Statistical Mechanics and its Applications, 314(1):220-229, 2002. Google Scholar
  40. Robert Kozma. Neuropercolation. Scholarpedia, 2(8):1360, 2007. Google Scholar
  41. Renaud Lambiotte and Pietro Panzarasa. Communities, knowledge creation, and information diffusion. Journal of Informetrics, 3(3):180-190, 2009. Google Scholar
  42. Cristian Moukarzel and Thomas Sokolowski. Long-range k-core percolation. Journal of Physics: Conference Series, 246(1):012019, 2010. Google Scholar
  43. Javier Orlandi, Jordi Soriano, Enrique Alvarez-Lacalle, Sara Teller, and Jaume Casademunt. Noise focusing and the emergence of coherent activity in neuronal cultures. Nature Physics, 9(9):582-590, 2013. Google Scholar
  44. Fragkiskos Papadopoulos, Maksim Kitsak, Ángeles Serrano, Marián Boguñá, and Dmitri Krioukov. Popularity versus similarity in growing networks. Nature, 489(7417):537-540, 2012. Google Scholar
  45. Marlon Ramos, Jia Shao, Saulo Reis, Celia Anteneodo, José Andrade, Shlomo Havlin, and Hernán Makse. How does public opinion become extreme? Scientific reports, 5:10032, 2015. Google Scholar
  46. Christian Schmeltzer, Jordi Soriano, Igor Sokolov, and Sten Rüdiger. Percolation of spatially constrained Erdős-Rényi networks with degree correlations. Physical Review E, 89(1):012116, 2014. Google Scholar
  47. Friedhelm Schwenker, Friedrich Sommer, and Günther Palm. Iterative retrieval of sparsely coded associative memory patterns. Neural Networks, 9(3):445-455, 1996. Google Scholar
  48. Munik Shrestha and Cristopher Moore. Message-passing approach for threshold models of behavior in networks. Physical Review E, 89(2):022805, 2014. Google Scholar
  49. Tsvi Tlusty and Jean-Pierre Eckmann. Remarks on bootstrap percolation in metric networks. Journal of Physics A: Mathematical and Theoretical, 42(20):205004, 2009. Google Scholar
  50. Tatyana Turova. The emergence of connectivity in neuronal networks: from bootstrap percolation to auto-associative memory. Brain research, 1434:277-284, 2012. Google Scholar
  51. Christopher Warren, Leonard Sander, and Igor Sokolov. Geography in a scale-free network model. Physical Review E, 66(5):056105, 2002. Google Scholar
  52. Duncan Watts. A simple model of global cascades on random networks. Proceedings of the National Academy of Sciences, 99(9):5766-5771, 2002. Google Scholar
  53. Xin-Jian Xu, Xun Zhang, and José Mendes. Impacts of preference and geography on epidemic spreading. Physical Review E, 76(5):056109, 2007. Google Scholar
  54. Zhi-Dan Zhao, Ying Liu, and Ming Tang. Epidemic variability in hierarchical geographical networks with human activity patterns. Chaos: An Interdisciplinary Journal of Nonlinear Science, 22(2):023150, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact