Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-27T20:25:03.575Z Has data issue: false hasContentIssue false
  • English
  • Français

Phase transition in random distance graphs on the torus

Part of: Graph theory Markov 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.
Get access Rights & Permissions [Opens in a new window]

Abstract

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 graphs 60J85: Applications of branching processes
Type
Research Papers
Information
Journal of Applied Probability , Volume 54 , Issue 4 , December 2017 , pp. 1278 - 1294
Copyright
Copyright © Applied Probability Trust 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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