Отправить статью по E-mail 
О СПЕКТРАЛЬНЫХ ПОРТРЕТАХ МАТРИЦ ИНЦИДЕНТНОСТИ ГРАФОВ БЛИЖАЙШИХ СОСЕДЕЙ
- Авторы: Кислицын A.A1
-
Учреждения:
- ИПМ им. Келдыша РАН
- Выпуск: Том 64, № 8 (2024)
- Страницы: 1561-1570
- Раздел: ИНФОРМАТИКА
- URL: https://bakhtiniada.ru/0044-4669/article/view/275004
- DOI: https://doi.org/10.31857/S0044466924080189
- EDN: https://elibrary.ru/XZTUET
- ID: 275004
Цитировать
Полный текст
Аннотация
В работе исследуется возможность применения метода С.К. Годунова построения спектрального портрета матрицы для оценки ранга матриц специального вида, которые появляются в ряде приложений, таких, как анализ структур графов ближайших соседей, теория конечных автоматов и оценка спектра разреженных матриц. Описан вычислительный алгоритм генерации ансамбля матриц случайных расстояний и связанных с ним графов ближайших соседей. На основе вычислительного эксперимента оценены параметры распределения степеней вершин случайных графов ближайших соседей. Оценки удается получить вследствие того, что указанное распределение не зависит от функции распределения случайных расстояний и является многомерным нормальным распределением. Доказано, что ранг матрицы инцидентности графа ближайших соседей равен суммарному числу вершин со степенями 0 и 1 по входящим ребрам, и получено распределение ранга такой матрицы. Показано, что в данной задаче определения ранга матрицы весьма эффективным является также метод, основанный на анализе распределения степеней вершин. Библ. 17. Фиг. 4.
Список литературы
- Уилкинсон Дж.Х. Алгебраическая проблема собственных значений. М.: Наука, 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 с.
Дополнительные файлы
