Hostname: page-component-7c8c6479df-24hb2 Total loading time: 0 Render date: 2024-03-28T20:41:19.676Z Has data issue: false hasContentIssue false

The Random Connection Model on the Torus

Published online by Cambridge University Press:  09 July 2014

LUC DEVROYE
Affiliation:
School of Computer Science, McGill University, Montreal, CanadaH3A 2K6 (e-mail: luc@cs.mcgill.ca)
NICOLAS FRAIMAN
Affiliation:
Department of Mathematics and Statistics, McGill University, Montreal, CanadaH3A 2K6 (e-mail: fraiman@math.mcgill.ca)

Abstract

We study the diameter of a family of random graphs on the torus that can be used to model wireless networks. In the random connection model two points x and y are connected with probability g(y−x), where g is a given function. We prove that the diameter of the graph is bounded by a constant, which depends only on ‖g1, with high probability as the number of vertices in the graph tends to infinity.

Type
Paper
Copyright
Copyright © Cambridge University Press 2014 

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]Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.CrossRefGoogle Scholar
[2]Flajolet, P., Hatzis, K. P., Nikoletseas, S. E. and Spirakis, P. G. (2002) On the robustness of interconnections in random graphs: A symbolic approach. Theoret. Comput. Sci. 287 515534.CrossRefGoogle Scholar
[3]Flajolet, P., Salvy, B. and Schaffer, G. (2004) Airy phenomena and analytic combinatorics of connected graphs. Electron. J. Combin. 11 R34.Google Scholar
[4]Franceschetti, M. and Meester, R. (2008) Random Networks for Communication: From Statistical Physics to Information Systems, Vol. 24 of Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press.Google Scholar
[5]Gilbert, E. (1961) Random plane networks. J. Soc. Ind. Appl. Math. 9 533543.Google Scholar
[6]Grafakos, L. (2008) Classical Fourier Analysis, Graduate Texts in Mathematics, Springer.Google Scholar
[7]Lagarias, J. C., Odlyzko, A. M. and Zagier, D. B. (1985) On the capacity of disjointly shared networks. Computer Networks and ISDN Systems 10 275285.Google Scholar
[8]Louchard, G. (1987) Random walks, Gaussian processes and list structures. Theoret. Comput. Sci. 53 99124.CrossRefGoogle Scholar
[9]Meester, R. and Roy, R. (1996) Continuum Percolation, Vol. 119 of Cambridge Tracts in Mathematics, Cambridge University Press.Google Scholar
[10]Penrose, M. (1991) On a continuum percolation model. Adv. Appl. Probab. 23 536556.Google Scholar