Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-15T00:53:24.854Z Has data issue: false hasContentIssue false
  • English
  • Français

Connectivity of random k-nearest-neighbour graphs

Part of:Equilibrium statistical mechanicsGraph theory

Published online by Cambridge University Press:  01 July 2016

Paul Balister,
Béla Bollobás,
Amites Sarkar and
Mark Walters
Paul Balister
Affiliation:
University of Memphis
Béla Bollobás*
Affiliation:
University of Memphis and University of Cambridge
Amites Sarkar*
Affiliation:
University of Memphis
Mark Walters*
Affiliation:
University of Cambridge
*
∗ Postal address: Department of Mathematics, University of Memphis, Dunn Hall, 3725 Norriswood, Memphis, TN 38152, USA.
∗∗∗∗ Email address: asarkar@memphis.edu
∗∗∗∗∗∗ Postal address: Peterhouse, University of Cambridge, Cambridge CB2 1RD. UK.
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.

Let 𝓅 be a Poisson process of intensity one in a square S n of area n. We construct a random geometric graph G n,k by joining each point of 𝓅 to its k ≡ k(n) nearest neighbours. Recently, Xue and Kumar proved that if k ≤ 0.074 log n then the probability that G n, k is connected tends to 0 as n → ∞ while, if k ≥ 5.1774 log n, then the probability that G n, k is connected tends to 1 as n → ∞. They conjectured that the threshold for connectivity is k = (1 + o(1)) log n. In this paper we improve these lower and upper bounds to 0.3043 log n and 0.5139 log n, respectively, disproving this conjecture. We also establish lower and upper bounds of 0.7209 log n and 0.9967 log n for the directed version of this problem. A related question concerns coverage. With G n, k as above, we surround each vertex by the smallest (closed) disc containing its k nearest neighbours. We prove that if k ≤ 0.7209 log n then the probability that these discs cover S n tends to 0 as n → ∞ while, if k ≥ 0.9967 log n, then the probability that the discs cover S n tends to 1 as n → ∞.

Keywords

Random geometric graphconnectivityPoisson process

MSC classification

Primary:05C80: Random graphs
Secondary:82B43: Percolation

Information

Type
Stochastic Geometry and Statistical Applications
Information
Advances in Applied Probability , Volume 37 , Issue 1 , March 2005, pp. 1 - 24
Copyright
Copyright © Applied Probability Trust 2005 

Footnotes

∗∗

Supported by NSF grant EIA-0130352.

∗∗∗

Supported by NSF grant DMS-9970404 and EIA-0130352 and DARPA grant F33615-01-C1900.

∗∗∗∗∗

Supported by NSF grant ITR-0225610.

References

Balister, P., Bollobás, B. and Walters, M. (2004). Continuum percolation with steps in the square or the disc. To appear in Random Structures Algorithms.Google Scholar
Bollobás, B. (2001). Random Graphs, 2nd edn. Cambridge University Press.Google Scholar
Bollobás, B. and Leader, I. (1991). Edge-isoperimetric inequalities in the grid. Combinatorica 11, 299–314.CrossRefGoogle Scholar
Gilbert, E. N. (1961). Random plane networks. J. Soc. Industrial Appl. Math. 9, 533–543.CrossRefGoogle Scholar
Gonzáles-Barrios, J. M. and Quiroz, A. J. (2003). A clustering procedure based on the comparison between the k nearest neighbors graph and the minimal spanning tree. Statist. Prob. Lett. 62, 23–34.Google Scholar
Hajek, B. (1983). Adaptive transmission strategies and routing in mobile radio networks. Proc. Conf. Inf. Sci. Systems 1983, 373–378.Google Scholar
Hou, T. and Li, V. (1986). Transmission range control in multihop packet radio networks. IEEE Trans. Commun. 34, 38–44.Google Scholar
Kleinrock, L. and Silvester, J. A. (1978). Optimum transmission radii for packet radio networks or why six is a magic number. In Proc. IEEE Nat. Telecommun. Conf. (Birmingham, AL, December 1978), pp. 4.3.1–4.3.5.Google Scholar
Mathar, R. and Mattfeldt, R. (1995). Analyzing routing strategy NFP in multihop packet radio network on a line. IEEE Trans. Commun. 43, 977–988.Google Scholar
Maudlin, R. D. (ed.) (1979). The Scottish Book. Birkhäuser, Boston, MA.Google Scholar
Meester, R. and Roy, R. (1996). Continuum Percolation. Cambridge University Press.CrossRefGoogle Scholar
Ni, J. and Chandler, S. A. G. (1994). Connectivity properties of a random radio network. In Proc. IEE Commun. 141, 289–296.CrossRefGoogle Scholar
Penrose, M. D. (1997). The longest edge of the random minimal spanning tree. Ann. Appl. Prob. 7, 340–361.CrossRefGoogle Scholar
Penrose, M. D. (2003). Random Geometric Graphs. Oxford University Press.CrossRefGoogle Scholar
Quintanilla, J., Torquato, J. and Ziff, R. M. (2000). Efficient measurement of the percolation threshold for fully penetrable discs. J. Phys. A 33, 399–407.CrossRefGoogle Scholar
Silvester, J. A. (1980). On the spatial capacity of packet radio networks, Res. Rep. UCLA-ENG-8021, Department of Computer Science, University of California, Los Angeles.Google Scholar
Takagi, H. and Kleinrock, L. (1984). Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Trans. Commun. 32, 246–257.Google Scholar
Xue, F. and Kumar, P. R. (2004). The number of neighbors needed for connectivity of wireless networks. Wireless Networks 10, 169–181.CrossRefGoogle Scholar