Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-14T07:54:10.252Z Has data issue: false hasContentIssue false
  • English
  • Français

Phase transition in random distance graphs on the torus

Part of:Graph theoryMarkov processes

Published online by Cambridge University Press:  30 November 2017

Fioralba Ajazi,
George M. Napolitano and
Tatyana Turova
Fioralba Ajazi*
Affiliation:
Lund University and University of Lausanne
George M. Napolitano*
Affiliation:
Lund University
Tatyana Turova*
Affiliation:
Lund University
*
* Postal address: Department of Mathematical Statistics, Faculty of Science, Lund University, Sölvegatan 18, 22100 Lund, Sweden.
** Current address: Centre for Epidemiology and Screening, Department of Public Health, University of Copenhagen, Øster Farimagsgade 5, 1014 Copenhagen, Denmark.
* Postal address: Department of Mathematical Statistics, Faculty of Science, Lund University, Sölvegatan 18, 22100 Lund, Sweden.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this paper we consider random distance graphs motivated by applications in neurobiology. These models can be viewed as examples of inhomogeneous random graphs, notably outside of the so-called rank-1 case. Treating these models in the context of the general theory of inhomogeneous graphs helps us to derive the asymptotics for the size of the largest connected component. In particular, we show that certain random distance graphs behave exactly as the classical Erdős–Rényi model, not only in the supercritical phase (as already known) but in the subcritical case as well.

Keywords

Inhomogeneous random graphrandom distance graphlargest connected component

MSC classification

Primary:05C80: Random graphs60J85: Applications of branching processes

Information

Type
Research Papers
Information
Journal of Applied Probability , Volume 54 , Issue 4 , December 2017, pp. 1278 - 1294
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Aizenman, M. and Newman, C. M. (1986). Discontinuity of the percolation density in one dimensional 1 / |x - y|2 percolation models. Commun. Math. Phys. 107, 611–647. CrossRefGoogle Scholar
[2] Alon, N. and Spencer, J. H. (1992). The Probabilistic Method. With an Appendix by Paul Erdős. John Wiley, New York. Google Scholar
[3] Avin, C. (2008). Distance graphs: from random geometric graphs to Bernoulli graphs and between. In DialM-POMC '08, pp. 71–77. CrossRefGoogle Scholar
[4] Bhamidi, S., van der Hofstad, R. and van Leeuwaarden, J. S. H. (2010). Scaling limits for critical inhomogeneous random graphs with finite third moments. Electron. J. Prob. 15, 1682–1702. CrossRefGoogle Scholar
[5] Bhamidi, S., van der Hofstad, R. and van Leeuwaarden, J. S. H. (2012). Novel scaling limits for critical inhomogeneous random graphs. Ann. Prob. 40, 2299–2361. CrossRefGoogle Scholar
[6] Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31, 3–122. CrossRefGoogle Scholar
[7] Bollobás, B., Janson, S. and Riordan, O. (2007). Spread-out percolation in ℝ d . Random Structures Algorithms 31, 239–246. CrossRefGoogle Scholar
[8] Deijfen, M., van der Hofstad, R. and Hooghiemstra, G. (2013). Scale-free percolation. Ann. Inst. H. Poincaré Prob. Statist. 49, 817–838. CrossRefGoogle Scholar
[9] Janson, S. (2008). The largest component in a subcritical random graph with a power law degree distribution. Ann. Appl. Prob. 18, 1651–1668. CrossRefGoogle Scholar
[10] Janson, S., Kozma, R., Ruszinkó, M. and Sokolov, Y. (2015). Bootstrap percolation on a random graph coupled with a lattice. Preprint. Available at https://arxiv.org/abs/1507.07997v2. Google Scholar
[11] Lindvall, T. (1992). Lectures on the Coupling Method. John Wiley, New York. Google Scholar
[12] Markram, H. et al. (2015). Reconstruction and simulation of neocortical microcircuitry. Cell 163, 456–492. CrossRefGoogle ScholarPubMed
[13] Otter, R. (1949). The multiplicative process. Ann. Math. Statist. 20, 206–224. CrossRefGoogle Scholar
[14] Penrose, M. D. (1993). On the spread-out limit for bond and continuum percolation. Ann. Appl. Prob. 3, 253–276. CrossRefGoogle Scholar
[15] Penrose, M. (2003). Random Geometric Graphs. Oxford University Press. CrossRefGoogle Scholar
[16] Reimann, M. W. et al. (2017). Cliques of neurons bound into cavities provide a missing link between structure and function. Front. Comput. Neurosci. 11, 48pp. CrossRefGoogle ScholarPubMed
[17] Turova, T. S. (2011). The largest component in subcritical inhomogeneous random graphs. Combin. Prob. Comput. 20, 131–154. CrossRefGoogle Scholar
[18] Turova, T. S. (2012). The emergence of connectivity in neuronal networks: from bootstrap percolation to auto-associative memory. Brain Res. 1434, 277–284. CrossRefGoogle ScholarPubMed
[19] Turova, T. S. (2013). Asymptotics for the size of the largest component scaled to 'log n' in inhomogeneous random graphs. Ark. Mat. 51, 371–403. CrossRefGoogle Scholar
[20] Turova, T. S. (2013). Diffusion approximation for the components in critical inhomogeneous random graphs of rank-1. Random Structures Algorithms 43, 486–539. CrossRefGoogle Scholar
[21] Van der Hofstad, R. (2016). Random Graphs and Complex Networks Vol. 1. Cambridge University Press. CrossRefGoogle Scholar