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

[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:

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.