RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Автомат. и телемех.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Автомат. и телемех., 2011, выпуск 2, страницы 131–141 (Mi at1290)  

Эта публикация цитируется в 15 научных статьях (всего в 15 статьях)

Тематический выпуск

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

А. В. Назин, Б. Т. Поляк

Институт проблем управления им. В. А. Трапезникова РАН, Москва

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

Полный текст: PDF файл (234 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Automation and Remote Control, 2011, 72:2, 342–352

Реферативные базы данных:

Тип публикации: Статья
Статья представлена к публикации членом редколлегии: А. И. Кибзун

Поступила в редакцию: 15.06.2010

Образец цитирования: А. В. Назин, Б. Т. Поляк, “Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче PageRank”, Автомат. и телемех., 2011, № 2, 131–141; Autom. Remote Control, 72:2 (2011), 342–352

Цитирование в формате AMSBIB
\RBibitem{NazPol11}
\by А.~В.~Назин, Б.~Т.~Поляк
\paper Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с~применением к~задаче PageRank
\jour Автомат. и телемех.
\yr 2011
\issue 2
\pages 131--141
\mathnet{http://mi.mathnet.ru/at1290}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2814107}
\zmath{https://zbmath.org/?q=an:1233.65032}
\transl
\jour Autom. Remote Control
\yr 2011
\vol 72
\issue 2
\pages 342--352
\crossref{https://doi.org/10.1134/S0005117911020111}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000287660400011}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-79954495351}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/at1290
  • http://mi.mathnet.ru/rus/at/y2011/i2/p131

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Гасников А.В., Гасникова Е.В., Федько О.С., “О возможной динамике в моде- ли ранжирования web-страниц pagerank и модернизированной модели расчета матрицы корреспонденций”, Труды Московского физико-технического института, 4:2-14 (2012), 101–120  elib
    2. Ishii H., Tempo R., Bai E.-W., “A Web Aggregation Approach for Distributed Randomized Pagerank Algorithms”, IEEE Trans. Autom. Control, 57:11 (2012), 2703–2717  crossref  mathscinet  zmath  isi  elib  scopus
    3. А. В. Назин, С. В. Анулова, А. А. Тремба, “Алгоритм зеркального спуска для минимизации средних потерь, поступающих пуассоновским потоком”, Автомат. и телемех., 2014, № 6, 30–38  mathnet; A. V. Nazin, S. V. Anulova, A. A. Tremba, “A mirror descent algorithm for minimization of mean Poisson flow driven losses”, Autom. Remote Control, 75:6 (2014), 1010–1016  crossref  isi
    4. Ishii H., Tempo R., “The Pagerank Problem, Multiagent Consensus, and Web Aggregation a Systems and Control Viewpoint”, IEEE Control Syst. Mag., 34:3 (2014), 34–53  crossref  mathscinet  isi  scopus
    5. Nazin A., Anulova S., Tremba A., “Application of the Mirror Descent Method To Minimize Average Losses Coming By a Poisson Flow”, 2014 European Control Conference (Ecc), IEEE, 2014, 2194–2197  crossref  isi  scopus
    6. А. В. Гасников, Д. Ю. Дмитриев, “Об эффективных рандомизированных алгоритмах поиска вектора PageRank”, Ж. вычисл. матем. и матем. физ., 55:3 (2015), 355–371  mathnet  crossref  mathscinet  zmath  elib; A. V. Gasnikov, D. Yu. Dmitriev, “On efficient randomized algorithms for finding the PageRank vector”, Comput. Math. Math. Phys., 55:3 (2015), 349–365  crossref  isi  elib
    7. А. В. Гасников, Ю. Е. Нестеров, В. Г. Спокойный, “Об эффективности одного метода рандомизации зеркального спуска в задачах онлайн оптимизации”, Ж. вычисл. матем. и матем. физ., 55:4 (2015), 582–598  mathnet  crossref  mathscinet  zmath  elib; A. V. Gasnikov, Yu. E. Nesterov, V. G. Spokoiny, “On the efficiency of a randomized mirror descent algorithm in online optimization problems”, Comput. Math. Math. Phys., 55:4 (2015), 580–596  crossref  isi  elib
    8. Ravazzi Ch., Frasca P., Tempo R., Ishii H., “Ergodic Randomized Algorithms and Dynamics Over Networks”, IEEE Trans. Control Netw. Syst., 2:1 (2015), 78–87  crossref  mathscinet  zmath  isi  scopus
    9. А. В. Назин, А. А. Тремба, “Игровой алгоритм зеркального спуска в задаче робастного PageRank”, Автомат. и телемех., 2016, № 8, 105–124  mathnet  elib; A. V. Nazin, A. A. Tremba, “Saddle point mirror descent algorithm for the robust PageRank problem”, Autom. Remote Control, 77:8 (2016), 1403–1418  crossref  isi  elib
    10. Zhao Zh., Jin X.-Q., Bai Zh.-J., “A Geometric Nonlinear Conjugate Gradient Method For Stochastic Inverse Eigenvalue Problems”, SIAM J. Numer. Anal., 54:4 (2016), 2015–2035  crossref  mathscinet  zmath  isi  elib  scopus
    11. Yao T.-T., Bai Zh.-J., Zhao Zh., Ching W.-K., “A Riemannian Fletcher-Reeves Conjugate Gradient Method For Doubly Stochastic Inverse Eigenvalue Problems”, SIAM J. Matrix Anal. Appl., 37:1 (2016), 215–234  crossref  mathscinet  zmath  isi  elib  scopus
    12. Lagoa C.M., Zaccarian L., Dabbene F., “A Distributed Algorithm With Consistency For Pagerank-Like Linear Algebraic Systems”, IFAC PAPERSONLINE, 50:1 (2017), 5172–5177  crossref  isi  scopus
    13. Markovich N.M., “Analysis of Clusters in Network Graphs For Personalized Web Search”, IFAC PAPERSONLINE, 50:1 (2017), 5178–5183  crossref  isi  scopus
    14. Hadjicostis Ch.N., Dominguez-Garcia A.D., Charalambous T., “Distributed Averaging and Balancing in Network Systems”, Found. Trends Syst. Control, 5:2-3 (2018), 99–292  crossref  isi  scopus
    15. Markovich N.M., Ryzhov M.S., Krieger U.R., “Statistical Clustering of a Random Network By Extremal Properties”, Distributed Computer and Communication Networks (Dccn 2018), Communications in Computer and Information Science, 919, eds. Vishnevskiy V., Kozyrev D., Springer-Verlag Berlin, 2018, 71–82  crossref  isi  scopus
  • Автоматика и телемеханика
    Просмотров:
    Эта страница:797
    Полный текст:183
    Литература:71
    Первая стр.:33
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020