Investigation of Statistics of Nearest Neighbor Graphs

This paper describes some statistical properties of the nearest neighbor graphs (NNGs). We study the sample distributions of graphs by the number of disconnected fragments, fragments by the number of nodes, and nodes by the degrees of incoming edges. The statements about the asymptotic properties of these distributions for graphs of a large dimension are proved and their relationship with Young’s classical diagrams and Wigner’s semicircle distribution is noted. The problem of determining the probability of realizing a certain structure of the nearest neighbors depending on the distribution of distances between the elements of the studied set is considered. It is shown that, the NNG does not depend on the distribution of distances up to an isomorphism. This fact makes it possible to construct basic statistics using a uniform distribution, and to obtain tabulated data for the statistics of the NNGs as a result of numerical modeling. A study has been conducted on the conditional extremum of the probability of realizing the distribution of graph nodes by degrees, which allows us to estimate the proportion of randomness for a particular structure, which appears from clustering elements of a certain set by the nearest neighbor method. An algorithm for collecting the sample statistics of the NNGs using the specific features of such graphs is described.