Investigation of statistics of nearest neighbor graphs

A. A. Kislitsyn

Matematičeskoe modelirovanie, Tome 34 (2022) no. 8, pp. 110-126

Résumé

The paper describes some statistical properties of the nearest neighbor graphs. 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 large dimension are proved, also is noted connection with classical Young diagrams and Wigner semicircle distribution. The problem of determining the probability of realization of 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 nearest neighbor graph does not depend on of distribution of distances up to isomorphism. This fact makes it possible to construct basic statistics using a uniform distribution, and to obtain tabulated data for statistics of nearest neighbor graphs 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 sample statistics of nearest neighbor graphs using the specific features of such graphs is described.

Détail

Keywords: nearest neighbor graph, degree distribution, clustering, asymptotic distributions, stochastic matrix.