A. Gasnikov, E. Gasnikova, P. Dvurechensky, A. Mohammed, E. Chernousova, “About the power law of the PageRank vector distribution. Part 1. Numerical methods for finding the PageRank vector”, Sib. Zh. Vychisl. Mat., 2017, Volume 20, Number 4,Pages <nobr>359

This article is cited in 6 papers

About the power law of the PageRank vector distribution. Part 1. Numerical methods for finding the PageRank vector

A. Gasnikov^ab, E. Gasnikova^a, P. Dvurechensky^bc, A. Mohammed^a, E. Chernousova^a

^a Moscow Institute of Physics and Technology, 9 Institutskiy per., Dolgoprudny, 141700, Russia
^b Institute for Information Transmission Problems RAS, 19, build. 1, Bolshoy Karetny per., Moscow, 127051, Russia
^c Weierstrass Institute for Applied Analysis and Stochastics, 39 Mohrenstr., Berlin, 10117, Germany

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.

Key words: Markov chain, ergodic theorem, multinomial distribution, measure concentration, maximum likelihood estimate, Google problem, gradient descent, automatic differentiation, power law distribution.

UDC: 519.217.2+519.614.2

Received: 07.03.2017
Revised: 15.05.2017

DOI: 10.15372/SJNM20170402