About the power law of the PageRank vector distribution. Part 1. Numerical methods for finding the PageRank vector
A. Gasnikov1,2, E. Gasnikova1, P. Dvurechensky2,3, A. Mohammed1, E. Chernousova1
1Moscow Institute of Physics and Technology, 9 Institutskiy per., Dolgoprudny, Russia, 141700
2Institute for Information Transmission Problems RAS, Bolshoy Karetny per. 19, build. 1, Moscow, Russia, 127051
3Weierstrass Institute for Applied Analysis and Stochastics, Mohrenstr. 39, Berlin, Germany, 10117
Keywords: марковская цепь, эргодическая теорема, мультиномиальное распределение, концентрация меры, оценка максимального правдоподобия, Google problem, градиентный спуск, автоматическое дифференцирование, степенной закон распределения, Markov chain, ergodic theorem, multinomial distribution, measure concentration, maximum likelihood estimate, Google problem, gradient descent, automatic differentiation, power law distribution
Abstract
In Part 1 of this paper, we consider the web-pages ranking problem also known as the problem of finding the PageRank vector or Google problem. We discuss the connection of this problem with the ergodic theorem and describe different numerical methods to solve this problem together with their theoretical background, such as Markov Chain Monte Carlo and equilibrium in a macrosystem.
|
