Научная визуализация

Scientific Visualization

Электронный журнал открытого доступа

Национальный Исследовательский Ядерный Университет "МИФИ"

      ISSN 2079-3537      

 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                                                                                             

Научная визуализация, 2023, том 15, номер 1, страницы 17 - 28, DOI: 10.26583/sv.15.1.02

Investigation of the Properties of First Nearest Neighbors’ Graphs

Авторы: A.A. Kislitsyn1, Yu.N. Orlov2, M.V.  Goguev3

Keldysh Institute of Applied Mathematics of RAS, Miusskaya sq., 4, Moscow, 125047, Russia

1 ORCID: 0000-0003-2388-0496, alexey.kislitsyn@gmail.com

2 ORCID: 0000-0002-1356-5137, ov3159f@yandex.ru

3 ORCID: 0000-0001-5365-070X, goguev.mv14@physics.msu.ru

 

Аннотация

In this study we present a benchmark of statistical distributions of the first nearest neighbors in random graphs. We consider distribution of such graphs by the number of disconnected fragments, fragments by the number of involved nodes, and nodes by their degrees. The statements about the asymptotic properties of these distributions for graphs of large dimension are proved. The problem under investigation is to estimate the probability of realization of a certain structure of the first nearest neighbors graph depending on the distribution function of distances between the elements of the studied set. It is shown that, up to isomorphism, the graph of the first nearest neighbors does not depend on the distance distribution. This fact makes it possible to conduct numerical experiments on the construction of basic statistics based on a uniform distribution of distances and obtain tabulated data as a result of numerical modeling. We also discuss the approximation of the distribution of graph vertices by degrees, which allows us to estimate the proportion of randomness for a particular structure resulting from clustering elements of a certain set by the nearest neighbor method. The asymptotic analysis of the fragment distribution is discussed.

 

Ключевые слова: Nearest neighbors graph, graph statistical structure, distribution of nodes degree, asymptotical distribution.