Connectivity of random k-nearest-neighbour graphs
- 1 March 2005
- journal article
- stochastic geometry-and-statistical-applications
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 37 (01), 1-24
- https://doi.org/10.1017/s000186780000001x
Abstract
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
This publication has 10 references indexed in Scilit:
- The Number of Neighbors Needed for Connectivity of Wireless NetworksWireless Networks, 2004
- A clustering procedure based on the comparison between the k nearest neighbors graph and the minimal spanning treeStatistics & Probability Letters, 2003
- Efficient measurement of the percolation threshold for fully penetrable discsJournal of Physics A: General Physics, 2000
- The longest edge of the random minimal spanning treeThe Annals of Applied Probability, 1997
- Analyzing routing strategy NFP in multihop packet radio networks on a lineIEEE Transactions on Communications, 1995
- Connectivity properties of a random radio networkIEE Proceedings - Communications, 1994
- Edge-isoperimetric inequalities in the gridCombinatorica, 1991
- Transmission Range Control in Multihop Packet Radio NetworksIEEE Transactions on Communications, 1986
- Optimal Transmission Ranges for Randomly Distributed Packet Radio TerminalsIEEE Transactions on Communications, 1984
- Random Plane NetworksJournal of the Society for Industrial and Applied Mathematics, 1961