Skip to main content
Article
Connectivity of Random k-Nearest-Neighbor Graphs
Advances in Applied Probability
  • Paul Balister, University of Memphis
  • Béla Bollobás, University of Memphis
  • Amites Sarkar, Western Washington University
  • Mark Walters, Trinity College
Document Type
Article
Publication Date
1-1-2005
Keywords
  • Random geometric graph,
  • connectivity,
  • Poisson process
Disciplines
Abstract

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

DOI
http://dx.doi.org/10.1239/aap/1113402397
Required Publisher's Statement

This is the authors' post refereed version of the article. Here is a link to the publisher's version: http://projecteuclid.org/euclid.aap/1113402397

Comments

This is the authors' post refereed version of the article. Here is a link to the publisher's version: http://projecteuclid.org/euclid.aap/1113402397

Subjects - Topical (LCSH)
Random graphs; Graph connectivity; Poisson processes
Genre/Form
articles
Type
Text
Rights
Copying of this document in whole or in part is allowable only for scholarly purposes. It is understood, however, that any copying or publication of this document for commercial purposes, or for financial gain, shall not be allowed without the author’s written permission.
Language
English
Format
application/pdf
Citation Information
Paul Balister, Béla Bollobás, Amites Sarkar and Mark Walters. "Connectivity of Random k-Nearest-Neighbor Graphs" Advances in Applied Probability Vol. 37 Iss. 1 (2005) p. 1 - 24
Available at: http://works.bepress.com/amites_sarkar/10/