Publishing House SB RAS:

Publishing House SB RAS:

Address of the Publishing House SB RAS:
Morskoy pr. 2, 630090 Novosibirsk, Russia



Advanced Search

Numerical Analysis and Applications

2017 year, number 4

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.