Аннотация:
Рассматривается задача оценивания собственного вектора, соответствующего наибольшему собственному значению стохастической матрицы. Известны многочисленные ее приложения, возникающие при ранжировании результатов поиска, согласованности действий мультиагентных систем, при управлении в сетях и анализе данных. Стандартная техника решения этой задачи сводится к степенному методу, но при дополнительной регуляризации исходной матрицы. Предлагается новый рандомизированный алгоритм и обосновывается равномерная (во всем классе стохастических матриц данной размерности) верхняя граница скорости сходимости вида $C\sqrt{\ln(N)/n}$, где $C$ – абсолютная постоянная, $N$ – размерность, а $n$ – число итераций. Эта граница представляется обнадеживающей, поскольку величина $\ln(N)$ совсем не велика для очень большой размерности. Алгоритм основан на методе зеркального спуска для задач выпуклой стохастической оптимизации. Обсуждается возможность применения метода к задаче PageRank о ранжировании страниц в Интернете.
Статья представлена к публикации членом редколлегии:А. И. Кибзун
Образец цитирования:
А. В. Назин, Б. Т. Поляк, “Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче PageRank”, Автомат. и телемех., 2011, № 2, 131–141; Autom. Remote Control, 72:2 (2011), 342–352
Natalia Markovich, Marijus Vaičiulis, “Extreme Value Statistics for Evolving Random Networks”, Mathematics, 11:9 (2023), 2171
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
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
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
Hideaki Ishii, Atsushi Suzuki, Systems & Control: Foundations & Applications, Uncertainty in Complex Networked Systems, 2018, 419
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
Markovich N.M., “Analysis of Clusters in Network Graphs For Personalized Web Search”, IFAC PAPERSONLINE, 50:1 (2017), 5178–5183
Alexander Nazin, Lecture Notes in Computer Science, 10684, Analytical and Computational Methods in Probability Theory, 2017, 376
А. В. Назин, А. А. Тремба, “Игровой алгоритм зеркального спуска в задаче робастного PageRank”, Автомат. и телемех., 2016, № 8, 105–124; A. V. Nazin, A. A. Tremba, “Saddle point mirror descent algorithm for the robust PageRank problem”, Autom. Remote Control, 77:8 (2016), 1403–1418
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
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
А. В. Гасников, Д. Ю. Дмитриев, “Об эффективных рандомизированных алгоритмах поиска вектора PageRank”, Ж. вычисл. матем. и матем. физ., 55:3 (2015), 355–371; A. V. Gasnikov, D. Yu. Dmitriev, “On efficient randomized algorithms for finding the PageRank vector”, Comput. Math. Math. Phys., 55:3 (2015), 349–365
А. В. Гасников, Ю. Е. Нестеров, В. Г. Спокойный, “Об эффективности одного метода рандомизации зеркального спуска в задачах онлайн оптимизации”, Ж. вычисл. матем. и матем. физ., 55:4 (2015), 582–598; 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
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
А. В. Назин, С. В. Анулова, А. А. Тремба, “Алгоритм зеркального спуска для минимизации средних потерь, поступающих пуассоновским потоком”, Автомат. и телемех., 2014, № 6, 30–38; 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
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
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
Roberto Tempo, Giuseppe Calafiore, Fabrizio Dabbene, Communications and Control Engineering, Randomized Algorithms for Analysis and Control of Uncertain Systems, 2013, 283
Гасников А.В., Гасникова Е.В., Федько О.С., “О возможной динамике в моде- ли ранжирования web-страниц pagerank и модернизированной модели расчета матрицы корреспонденций”, Труды Московского физико-технического института, 4:2-14 (2012), 101–120
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