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

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

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



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






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


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

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

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

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

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

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

Поступила в редакцию: 15.06.2010
Англоязычная версия:
Automation and Remote Control, 2011, Volume 72, Issue 2, Pages 342–352
DOI: https://doi.org/10.1134/S0005117911020111
Реферативные базы данных:
Тип публикации: Статья
Образец цитирования: А. В. Назин, Б. Т. Поляк, “Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче 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://mathscinet.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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000287660400011}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-79954495351}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/at1290
  • https://www.mathnet.ru/rus/at/y2011/i2/p131
  • Эта публикация цитируется в следующих 20 статьяx:
    1. Natalia Markovich, Marijus Vaičiulis, “Extreme Value Statistics for Evolving Random Networks”, Mathematics, 11:9 (2023), 2171  crossref
    2. Anikin A., Gasnikov A., Gornov A., Kamzolov D., Maximov Yu., Nesterov Yu., “Efficient Numerical Methods to Solve Sparse Linear Equations With Application to Pagerank”, Optim. Method Softw., 2020  crossref  mathscinet  isi
    3. 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
    4. 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
    5. Hideaki Ishii, Atsushi Suzuki, Systems & Control: Foundations & Applications, Uncertainty in Complex Networked Systems, 2018, 419  crossref
    6. 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
    7. Markovich N.M., “Analysis of Clusters in Network Graphs For Personalized Web Search”, IFAC PAPERSONLINE, 50:1 (2017), 5178–5183  crossref  isi  scopus
    8. Alexander Nazin, Lecture Notes in Computer Science, 10684, Analytical and Computational Methods in Probability Theory, 2017, 376  crossref
    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. А. В. Гасников, Д. Ю. Дмитриев, “Об эффективных рандомизированных алгоритмах поиска вектора 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
    13. А. В. Гасников, Ю. Е. Нестеров, В. Г. Спокойный, “Об эффективности одного метода рандомизации зеркального спуска в задачах онлайн оптимизации”, Ж. вычисл. матем. и матем. физ., 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
    14. 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
    15. А. В. Назин, С. В. Анулова, А. А. Тремба, “Алгоритм зеркального спуска для минимизации средних потерь, поступающих пуассоновским потоком”, Автомат. и телемех., 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
    16. 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
    17. 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
    18. Roberto Tempo, Giuseppe Calafiore, Fabrizio Dabbene, Communications and Control Engineering, Randomized Algorithms for Analysis and Control of Uncertain Systems, 2013, 283  crossref
    19. Гасников А.В., Гасникова Е.В., Федько О.С., “О возможной динамике в моде- ли ранжирования web-страниц pagerank и модернизированной модели расчета матрицы корреспонденций”, Труды Московского физико-технического института, 4:2-14 (2012), 101–120  elib
    20. 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
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Автоматика и телемеханика
    Статистика просмотров:
    Страница аннотации:1026
    PDF полного текста:285
    Список литературы:107
    Первая страница:33
     
      Обратная связь:
    math-net2025_01@mi-ras.ru
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025