About the power law of the PageRank vector distribution. Part 2. Backley-Osthus model, power law verification for this model and setup of real search engines
A. Gasnikov1,2, P. Dvurechensky2,3, M. Zhukovskii1,4, S. Kim5, S. Plaunov5, D. Smirnov5, F. Noskov6
1Moscow Institute of Physics and Technology, 9 Institutskiy per., Dolgoprudny, Moscow Region, 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, 10117 Berlin, Germany
4OOO В«Yandex», Leo Tolstoy st. 16, Moscow, Russia, 119034
5State Budget Educational Institution Physics and Mathematical School 2007, 9-1 Gorchakova str., Moscow, Russia 117042
6National Research University Higher School of Economics, 20 Myasnitskaya str., Moscow 101000
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 the second part of this paper, we consider the Buckley-Osthus model for the formation of a web-graph. For the networks generated according to this model, we numerically calculate the PageRank vector. We show that the components of this vector are distributed according to the power law. We also discuss the computational aspects of this model with respect to different numerical methods for the calculation of the PageRank vector, presented in the first part of the paper. Finally, we describe a general model for the web-page ranking and some approaches to solve the optimization problem arising when learning this model.
|
