ON SPECTRAL PORTRAITS OF NEAREST NEIGHBOR GRAPH INCIDENCE MATRICES

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access 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

  1. Уилкинсон Дж.Х. Алгебраическая проблема собственных значений. М.: Наука, 1970. 564 с.
  2. Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999. 546 с.
  3. Орлов Ю.Н., Осминин К.П. Методы статистического анализа литературных текстов. М.: Эдиториал УРСС/Книжный дом “ЛИБРОКОМ”, 2012. 312 с.
  4. Годунов С.К. Современные аспекты линейной алгебры. Новосибирск: Научн. книга, 1997. 388 с.
  5. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. Springer, 2001. 764 р.
  6. Erdos P., Renyi A. On random graphs I // Publ. Math. Debrecen, 1959. Vol. 6. P. 290—297.
  7. Колчин В.Ф. Случайные графы. М.: Физматлит, 2004. 256 с.
  8. Bollobas B. Random Graphs.London: Cambridge University Press, 2001. 520 р.
  9. Janson S., Luczak T., Rucinski A. Random graphs. New York: Wiley, 2000. 333 p.
  10. Райгородский А.М. Модели случайных графов и их применения // Тр. МФТИ, 2010. Т. 2. № 4. С. 130—140.
  11. Райгородский А.М. Модели Интернета. Долгопрудный: Издательский Дом Интеллект, 2013. 64 с.
  12. Barabasi L.-A., Albert R. Emergence of scaling in random networks // Science. 1999. V 286. P. 509—512.
  13. 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.
  14. Кислицын А.А. Исследование статистик графов ближайших соседей // Матем. моделирование. 2022. Т. 34. № 8. С. 110-126.
  15. Kislitsyn A.A., Orlov Yu.N. Discussion about Properties of First Neighbor Graphs // Lobachevskii Journal of Mathematics 2022. V 43. № 12. P 109-118.
  16. Кислицын А.А. Анализ каталога землетрясений // Матем. моделирование 2023. Т. 35. № 7. С. 63-82.
  17. Мельников С.Ю. Идентификация конечных автоматов на основе метода многогранников. М. — Ижевск: Институт компьютерных технологий, 2013. 136 с.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2024 Russian Academy of Sciences