Survey/references on random geometric $K$-NN – $K$-nearest-neighbour graphs?

Question

[Edit:] Some related info on number of connected components of NN-graphs can be found here: https://cstheory.stackexchange.com/a/47037/2408

---

Sample $N$ points in $\mathbb{R}^d$ from some distribution $f$, e.g. uniform $[0,1]^d$, or Gaussian $\mathcal{N}(0,1)^d$, or whatever...

Question 1: What is known/survey/references on $K$-nearest-neighbor graphs for such data clouds ? (that means we connect each point with $K$ its nearest neighbors). At least for some distributions $f$ like uniform or Gaussian ?

Question 2: For example what is known about degrees distribution ? Simulations suggest it is power-law, what is the exponent depending on $d$ and $f$?

There is good survey on Wikipedia - Geometric random graphs, but a little bit different class of graphs is considered there. I.e. points are connected if the distance is shorter than threshold $r$ (and, well, distribution is only uniform). It is more common in practical applications to consider $K$-NN graphs, rather than GRG, by the clear reason - the size of graph is $K\times N$, while for GRG you might get $N^2$ (in the worst case).

Question 3 Is there a way looking on $K$-NN graph to estimate dimension $d$ of the space, at least for uniform/Gaussian distributions ? Somewhat similar as "cluster coefficient" of GRG depends only on the dimension $d$:

Question 4: Is there an estimate of clustering coefficient for $K$-NN graph ?

Question 5: If one considers minimal spanning tree for $K$-NN graph, what is known about it ? Degree distribution ?

I am aware about the following beautiful result on the length estimate for Euclidean MST:

Answer 1

The wikipedia article on random geometric graphs only scratches the surface. A much deeper treatment is provided in Mathew Penrose's amazing text Random Geometric Graphs. Chapter 4 contains a treatment of what you are asking about, namely the "empirical distribution of nearest-neighbour distances amongst the points." Also, the underlying distribution of the points does not need to be uniform. You can feed in any underlying distribution and run a $\chi^2$-test to see if that distribution is a good fit, based on a $k$-NN statistic. Penrose says this was considered by Bickel and Breiman. Penrose cites a book by Silverman for more on this kind of thing.

Penrose also cites a monograph by Yukich that I have not read. About this monograph, Penrose writes (emphasis mine)

Related graph constructions include those where the decision on whether to connect two nearby points depends not only on the distance between them, but also on the positions of other points. Such constructions include the minimal spanning tree, and also graphs such as the nearest-neighbour graph and the Delaunay graph; in the latter, points lying in neighbouring Voronoi cells are connected. For many of these related graph constructions, some of the asymptotic theory is described in Yukich (1998). For further results see Penrose and Yukich (2001, 2003).