Random Nearest Neighbor Graphs: Benchmarking and Statistical Analysis

The article presents the main theoretical results concerning the statistical properties of random nearest neighbor graphs. Under the assumption of uniqueness of the nearest neighbor for each point in a finite set, distributions of graphs by connectivity components and vertices by degrees are studied. It is shown that these distributions do not depend on the distribution function of distances between points in the set or whether they satisfy the triangle inequality. As a result, it became possible to construct graph structure distributions both for random distance matrices in low-dimensional spaces and for arbitrary random matrices. These distributions allow formulating new independence criteria for random variables depending on how likely different graph structures occur. In some practical cases, these criteria turn out to be more productive than traditional homogeneity tests used in statistics. Importantly, the constructed nonparametric criteria enable analysis of non-stationarity when sample sizes are too small to analyze them through comparison of empirical distribution functions. At the same time, the benchmark of nearest neighbor graph structure statistics allows analyzing large samples, treating them as outputs from pseudorandom number generators. This makes comparative analysis of such generators feasible. The paper provides an example comparing Mersenne Twister, Xoshiro512, and a generator using the decimal representation of pi.