13299

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче PageRank

Наименование источника: 

  • Автоматика и телемеханика

Обозначение и номер тома: 

№ 2

Город: 

  • Москва

Издательство: 

  • Наука

Год издания: 

2011

Страницы: 

131-141
Аннотация
Рассматривается задача оценивания собственного вектора, соответствующе- го наибольшему собственному значению стохастической матрицы. Известны многочисленные ее приложения, возникающие при ранжировании результатов поиска, согласованности действий мультиагентных систем, при управлении в сетях и анализе данных. Стандартная техника решения этой задачи сводится к степенному методу, но при дополнительной регуляризации исходной матри- цы. Предлагается новый рандомизированный алгоритм и обосновывается рав- номерная (во всем классе стохастических матриц данной размерности) верхняя граница скорости сходимости вида Cpln(N)/n, где C – абсолютная постоянная, N – размерность, а n – число итераций. Эта граница представляется обнадежи- вающей, поскольку величина ln(N) совсем не велика для очень большой раз- мерности. Алгоритм основан на методе зеркального спуска для задач выпуклой стохастической оптимизации. Обсуждается возможность применения метода к задаче PageRank о ранжировании страниц в Интернете.

Библиографическая ссылка: 

Поляк Б.Т., Назин А.В. Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче PageRank // Автоматика и телемеханика. 2011. № 2. С. 131-141.