In this paper the investigation of the structure of k-NN graph is presented. The purpose of this analysis is to match the probability of implementation particular graph under assumption of a certain distribution of distances between vertices and depending on the number of vertices. Sample distributions of the graph by the number of disconnected fragments, fragments by the number of vertices, and vertices by the degrees of incoming edges are used as the main statistics. As an example, the problem of identifying the author of a text by the n-gram method is considered.

nearest neighbors graph, connectivity, power vertex distribution, sample graph, distance distribution

Mathematical modelling in actual problems of science and technics

Kislitsyn Alexey Alexeevich,  ,  orcid.org/0000-0003-2388-0496,  KIAM RAS

Orlov Yurii Nikolaevich,  ,  orcid.org/0000-0002-1356-5137,  KIAM RAS