Setup Sample random points from say standard Gaussian (or uniform) distribution in $R^{d}$ for some "d" and consider a KNN (K-nearest neigbour) graph for some K. Look at the degree distribution (say "IN"-degree, cause "OUT"-degree = K ).
Question 0 What is known about the degree distribution of such graphs ?
It is distribution on integers (>=0 ) it might be well-known for experts (see some info on median, std, percentiles here: cross validated 500250 : )
For high dimensions the distributions seems to follow power law for large "d" - see figure C (power law - sloped line in loglog plot) - which is typical for many graphs in nature - "scale free network", (although it is not always happen CSTHEORY14633).
Question 1 Is the exponent of power law known (how it depends on "d" and "K") ? (Does power law strictly hold true (when number of points tends to infinity) or it is kind of approximation or even illusion ) ?
Question 2 The distribution of degrees of KNN graph based on data cloud on the sphere and torus (uniform) is drastically different - the "tail" is much less "fatter" (see plot below) , is there any explanation for that ?
Remarks: The difference between sphere vs uniform/Gauss has been noted in similar context in The Hubness Phenomenon: Fact or Artifact? 2013. It also manifests itself in number of connected components analysis - see https://cstheory.stackexchange.com/a/47181/2408 . The simulation can be found in https://www.kaggle.com/alexandervc/knn-graphs-study-degree-distribution?scriptVersionId=48919017 .
======================
Background and motivation: KNN graphs and related KNN-predictors (classifier/regressor) are often used in machine learning. It was noticed that in higher dimensions the degree distribution becomes extremely skewed - see figures A, B (that means nodes with very high degree begin to appear - they are called "hubs" sometimes). It seems that is somewhat unexpected, because naively one might expect degree should not go far from "K", but actually it can go very far if dimension "d" is high. It is claimed that "hubs" cause problems for machine learning algorithms, certain techniques to fight with them appeared.
=======
Some other question about NN graphs is discussed here: Number of connected components of a random nearest neighbor graph?
============================
Code: Plots A,B from my notebook version 4: https://www.kaggle.com/alexandervc/knn-graphs-study-degree-distribution?scriptVersionId=48224880 Plot C from same notebook but version 6: https://www.kaggle.com/alexandervc/knn-graphs-study-degree-distribution?scriptVersionId=48230153 Uniform distribution can be found there also.
