Email this article 
ON SPECTRAL PORTRAITS OF NEAREST NEIGHBOR GRAPH INCIDENCE MATRICES
- Authors: Kislitsyn A.A1
-
Affiliations:
- Keldysh Institute of Applied Mathematics of the Russian Academy of Sciences
- Issue: Vol 64, No 8 (2024)
- Pages: 1561-1570
- Section: Computer science
- URL: https://journal-vniispk.ru/0044-4669/article/view/275004
- DOI: https://doi.org/10.31857/S0044466924080189
- EDN: https://elibrary.ru/XZTUET
- ID: 275004
Cite item
Open Access
Access granted
Subscription Access
Abstract
This paper explores the possibility of applying S.K. Godunov’s method of constructing spectral portraits of matrices to estimate the rank of special types of matrices that appear in various applications, such as nearest neighbor graph structure analysis, finite automata theory, and sparse matrix spectrum estimation. A computational algorithm for generating an ensemble of random distance matrices and the associated nearest neighbor graphs is described. Based on computational experiments, parameters of the vertex degree distribution of random nearest neighbor graphs are evaluated. These estimates are feasible because the distribution is independent of the random distance function and follows a multivariate normal distribution. It is proven that the rank of the incidence matrix of a nearest neighbor graph equals the total number of vertices with in-degree 0 and 1, and the rank distribution of such a matrix is derived. It is also shown that, in this context, a method based on analyzing the vertex degree distribution is highly effective for determining the matrix rank.
About the authors
A. A Kislitsyn
Keldysh Institute of Applied Mathematics of the Russian Academy of Sciences
Email: alexey.kislitsyn@gmail.com
Moscow, Russia
References
- Уилкинсон Дж.Х. Алгебраическая проблема собственных значений. М.: Наука, 1970. 564 с.
- Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999. 546 с.
- Орлов Ю.Н., Осминин К.П. Методы статистического анализа литературных текстов. М.: Эдиториал УРСС/Книжный дом “ЛИБРОКОМ”, 2012. 312 с.
- Годунов С.К. Современные аспекты линейной алгебры. Новосибирск: Научн. книга, 1997. 388 с.
- Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. Springer, 2001. 764 р.
- Erdos P., Renyi A. On random graphs I // Publ. Math. Debrecen, 1959. Vol. 6. P. 290—297.
- Колчин В.Ф. Случайные графы. М.: Физматлит, 2004. 256 с.
- Bollobas B. Random Graphs.London: Cambridge University Press, 2001. 520 р.
- Janson S., Luczak T., Rucinski A. Random graphs. New York: Wiley, 2000. 333 p.
- Райгородский А.М. Модели случайных графов и их применения // Тр. МФТИ, 2010. Т. 2. № 4. С. 130—140.
- Райгородский А.М. Модели Интернета. Долгопрудный: Издательский Дом Интеллект, 2013. 64 с.
- Barabasi L.-A., Albert R. Emergence of scaling in random networks // Science. 1999. V 286. P. 509—512.
- Leskovec J., Chakrabarti D., Kleinberg J., Faloutsos C., Gharamani Z. Kronecker graphs: an approach to modeling networks //J. Machine Learning Research. 2010. V 11. P. 985-1042.
- Кислицын А.А. Исследование статистик графов ближайших соседей // Матем. моделирование. 2022. Т. 34. № 8. С. 110-126.
- Kislitsyn A.A., Orlov Yu.N. Discussion about Properties of First Neighbor Graphs // Lobachevskii Journal of Mathematics 2022. V 43. № 12. P 109-118.
- Кислицын А.А. Анализ каталога землетрясений // Матем. моделирование 2023. Т. 35. № 7. С. 63-82.
- Мельников С.Ю. Идентификация конечных автоматов на основе метода многогранников. М. — Ижевск: Институт компьютерных технологий, 2013. 136 с.
Supplementary files
