The investigation of the k-NN graph statistics

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.