Geodesic
Investigation of statistics of nearest neighbor graphs
Matematičeskoe modelirovanie, Tome 34 (2022) no. 8, pp. 110-126.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper describes some statistical properties of the nearest neighbor graphs. We study the sample distributions of graphs by the number of disconnected fragments, fragments by the number of nodes, and nodes by the degrees of incoming edges. The statements about the asymptotic properties of these distributions for graphs of large dimension are proved, also is noted connection with classical Young diagrams and Wigner semicircle distribution. The problem of determining the probability of realization of a certain structure of the nearest neighbors depending on the distribution of distances between the elements of the studied set is considered. It is shown that, the nearest neighbor graph does not depend on of distribution of distances up to isomorphism. This fact makes it possible to construct basic statistics using a uniform distribution, and to obtain tabulated data for statistics of nearest neighbor graphs as a result of numerical modeling. A study has been conducted on the conditional extremum of the probability of realizing the distribution of graph nodes by degrees, which allows us to estimate the proportion of randomness for a particular structure, which appears from clustering elements of a certain set by the nearest neighbor method. An algorithm for collecting sample statistics of nearest neighbor graphs using the specific features of such graphs is described.
Keywords: nearest neighbor graph, degree distribution, clustering, asymptotic distributions, stochastic matrix. 
@article{MM_2022_34_8_a6,
     author = {A. A. Kislitsyn},
     title = {Investigation of statistics of nearest neighbor graphs},
     journal = {Matemati\v{c}eskoe modelirovanie},
     pages = {110--126},
     publisher = {mathdoc},
     volume = {34},
     number = {8},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MM_2022_34_8_a6/}
}
TY  - JOUR
AU  - A. A. Kislitsyn
TI  - Investigation of statistics of nearest neighbor graphs
JO  - Matematičeskoe modelirovanie
PY  - 2022
SP  - 110
EP  - 126
VL  - 34
IS  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MM_2022_34_8_a6/
LA  - ru
ID  - MM_2022_34_8_a6
ER  - 
%0 Journal Article
%A A. A. Kislitsyn
%T Investigation of statistics of nearest neighbor graphs
%J Matematičeskoe modelirovanie
%D 2022
%P 110-126
%V 34
%N 8
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MM_2022_34_8_a6/
%G ru
%F MM_2022_34_8_a6
A. A. Kislitsyn. Investigation of statistics of nearest neighbor graphs. Matematičeskoe modelirovanie, Tome 34 (2022) no. 8, pp. 110-126. http://geodesic.mathdoc.fr/item/MM_2022_34_8_a6/

[1] T. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, Springer, 2001, 764 pp. | MR | Zbl

[2] P. Erdos, A. Renyi, “On random graphs I”, Publ. Math. Debrecen, 6 (1959), 290–297 | MR | Zbl

[3] V. F. Kolchin, Sluchainye grafy, Fizmatlit, M., 2004, 256 pp.

[4] B. Bollobas, Random Graphs, Cambridge University Press, London, 2001, 520 pp. | MR | Zbl

[5] S. Janson, T. Luczak, A. Rucinski, Random graphs, Wiley, New York, 2000, 333 pp. | MR | Zbl

[6] A. M. Raigorodskii, “Modeli sluchainykh grafov i ikh primeneniia”, Trudy MFTI, 2:4 (2010), 130–140 | MR

[7] A. M. Raigorodskii, Modeli Interneta, Izdatelskii Dom «Intellekt», Dolgoprudnyi, 2013, 64 pp.

[8] L. A. Barabasi, R. Albert, “Emergence of scaling in random networks”, Science, 286 (1999), 509–512 | DOI | MR | Zbl

[9] J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, Z. Gharamani, “Kronecker graphs: an approach to modeling networks”, J. Machine Learning Research, 11 (2010), 985–1042 | MR | Zbl

[10] V. S. Koroliuk, N. I. Portenko, A. V. Skorokhod, A. F. Turbin, Spravochnik po teorii veroiatnostei i matematicheskoi statistike, Nauka, M., 1985, 640 pp. | MR

[11] G. H. Hardy, S. Ramanujan, “Asymptotic Formulae in Combinatory Analysis”, Proc. London Math. Soc., 17 (1918), 75–115 | DOI | MR | Zbl

[12] A. M. Vershik, S. V. Kerov, “Asimptotika mery Plansherelia simmetricheskoi gruppy i predel'naia forma tablits Iunga”, Doklady Akademii Nauk SSSR, 223:6 (1977), 1024–1027

[13] Dzh. Anderson, Diskretnaia matematika i kombinatorika, Viliams, M., 2004, 960 pp.

[14] A. A. Kislitsyn, Iu. N. Orlov, “Issledovanie statistik grafov blizhaishikh sosedei”, Preprinty IPM im. M.V. Keldysha, 2021, 085, 23 pp.