KIAM Main page Web Library  •  Publication Searh  Русский 

KIAM Preprint № 85, Moscow, 2021
Authors: Kislitsyn A.A., Orlov Y.N.
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.
nearest neighbors graph, connectivity, power vertex distribution, sample graph, distance distribution
Publication language: russian,  pages: 23
Research direction:
Mathematical modelling in actual problems of science and technics
Russian source text:
Export link to publication in format:   RIS    BibTeX
View statistics (updated once a day)
over the last 30 days — 3 (+2), total hit from 06.12.2021 — 166
About authors:
  • Kislitsyn Alexey Alexeevich, RAS
  • Orlov Yurii Nikolaevich, RAS