Distribution of components in the k-nearest neighbour random geometric graph for k below the connectivity threshold

Victor Falgas-Ravry (Umeå Universitet)


Let $S_{n,k}$ denote the random geometric graph obtained by placing points inside a square of area $n$ according to a Poisson point process of intensity $1$ and joining each such point to the $k=k(n)$ points of the process nearest to it.

In this paper we show that if $\mathbb{P}(S_{n,k} \textrm{ connected})>n^{-\gamma_1}$ then the probability that $S_{n,k}$ contains a pair of `small' components `close' to each other is $o(n^{-c_1})$ (in a precise sense of `small' and 'close'), for some absolute constants $\gamma_1>0$ and $c_1 >0$. This answers a question of Walters. (A similar result was independently obtained by Balister.)

As an application of our result, we show that the distribution of the connected components of $S_{n,k}$ below the connectivity threshold is asymptotically Poisson.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-22

Publication Date: September 18, 2013

DOI: 10.1214/EJP.v18-2465


  • Arratia, R.; Goldstein, L.; Gordon, L. Two moments suffice for Poisson approximations: the Chen-Stein method. Ann. Probab. 17 (1989), no. 1, 9--25. MR0972770
  • P. Balister and B. Bollobás. Percolation in the k-nearest neighbor graph, 2009.
  • Balister, Paul; Bollobás, Béla; Sarkar, Amites; Walters, Mark. Connectivity of random $k$-nearest-neighbour graphs. Adv. in Appl. Probab. 37 (2005), no. 1, 1--24. MR2135151
  • Balister, Paul; Bollobás, Béla; Sarkar, Amites; Walters, Mark. A critical constant for the $k$-nearest-neighbour model. Adv. in Appl. Probab. 41 (2009), no. 1, 1--12. MR2514943
  • Balister, Paul; Bollobás, Béla; Sarkar, Amites; Walters, Mark. Highly connected random geometric graphs. Discrete Appl. Math. 157 (2009), no. 2, 309--320. MR2479805
  • Chen, Louis H. Y. Poisson approximation for dependent trials. Ann. Probability 3 (1975), no. 3, 534--545. MR0428387
  • V. Falgas-Ravry and M. Walters. Sharpness in the k-nearest neighbour random geometric graph model. Advances in Applied Probability 44 (2012), 617--634.
  • Gilbert, E. N. Random plane networks. J. Soc. Indust. Appl. Math. 9 (1961), 533--543. MR0132566
  • J.M. González-Barrios and A.J. Quiroz. A clustering procedure based on the comparison between the k-nearest neighbors graph and the minimal spanning tree. Statistics and probability letters 62 (2003), no. 1, 23--34.
  • Penrose, Mathew D. The longest edge of the random minimal spanning tree. Ann. Appl. Probab. 7 (1997), no. 2, 340--361. MR1442317
  • Stein, Charles. A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), Vol. II: Probability theory, pp. 583--602. Univ. California Press, Berkeley, Calif., 1972. MR0402873
  • Walters, Mark. Random geometric graphs. Surveys in combinatorics 2011, 365--401, London Math. Soc. Lecture Note Ser., 392, Cambridge Univ. Press, Cambridge, 2011. MR2866737
  • Walters, Mark. Small components in $k$-nearest neighbour graphs. Discrete Appl. Math. 160 (2012), no. 13-14, 2037--2047. MR2927533
  • F. Xue and P.R. Kumar. The number of neighbors needed for connectivity of wireless networks. Wireless networks 10 (2004), no. 2, 169--181.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.