Investigation of the Properties of First Nearest Neighbors’ Graphs

Kislitsyn, A. A.; Orlov, Yu. N.; Goguev, M. V.

Publication:
Investigation of the Properties of First Nearest Neighbors’ Graphs

creativeworkseries.issn	2079-3537
dc.contributor.author	Kislitsyn, A. A.
dc.contributor.author	Orlov, Yu. N.
dc.contributor.author	Goguev, M. V.
dc.date.accessioned	2023-09-28T13:44:35Z
dc.date.available	2023-09-28T13:44:35Z
dc.date.issued	2023
dc.description.abstract	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.
dc.identifier.citation	A.A. Kislitsyn, Yu.N. Orlov, M.V. Goguev. Investigation of the Properties of First Nearest Neighbors’ Graphs (2023). Научная визуализация 15.1: 17 - 28, DOI: 10.26583/sv.15.1.02
dc.identifier.doi	10.26583/sv.15.1.02
dc.identifier.doi	10.26583/sv.15.1.02
dc.identifier.issn	2079-3537
dc.identifier.uri	https://openrepository.mephi.ru/handle/123456789/338
dc.identifier.uri	http://sv-journal.org/2023-1/02/
dc.relation.ispartof	Scientific Visualization
dc.subject	asymptotical distribution
dc.subject	istribution of nodes degree
dc.subject	graph statistical structure
dc.subject	Nearest neighbors graph
dc.title	Investigation of the Properties of First Nearest Neighbors’ Graphs
dc.type	journal-article
dspace.entity.type	Publication
oaire.citation.issue	1
oaire.citation.volume	15
relation.isJournalIssueOfPublication	8787e8db-c279-4dde-b63a-154e9f449a2f
relation.isJournalIssueOfPublication.latestForDiscovery	8787e8db-c279-4dde-b63a-154e9f449a2f
relation.isJournalOfPublication	95b5bb8c-faac-4680-a70f-5adf56268bdc