Experimental comparison of PageRank vector calculation algorithms

Skachkov D.A., Gladyshev S.I., Raigorodsky A.M.
 pdf (354K)

Finding PageRank vector is of great scientific and practical interest due to its applicability to modern search engines. Despite the fact that this problem is reduced to finding the eigenvector of the stochastic matrix $P$, the need for new algorithms is justified by a large size of the input data. To achieve no more than linear execution time, various randomized methods have been proposed, returning the expected result only with some probability close enough to one. We will consider two of them by reducing the problem of calculating the PageRank vector to the problem of finding equilibrium in an antagonistic matrix game, which is then solved using the Grigoriadis – Khachiyan algorithm. This implementation works effectively under the assumption of sparsity of the input matrix. As far as we know, there are no successful implementations of neither the Grigoriadis – Khachiyan algorithm nor its application to the task of calculating the PageRank vector. The purpose of this paper is to fill this gap. The article describes an algorithm giving pseudocode and some details of the implementation. In addition, it discusses another randomized method of calculating the PageRank vector, namely, Markov chain Monte Carlo (MCMC), in order to compare the results of these algorithms on matrices with different values of the spectral gap. The latter is of particular interest, since the magnitude of the spectral gap strongly affects the convergence rate of MCMC and does not affect the other two approaches at all. The comparison was carried out on two types of generated graphs: chains and $d$-dimensional cubes. The experiments, as predicted by the theory, demonstrated the effectiveness of the Grigoriadis – Khachiyan algorithm in comparison with MCMC for sparse graphs with a small spectral gap value. The written code is publicly available, so everyone can reproduce the results themselves or use this implementation for their own needs. The work has a purely practical orientation, no theoretical results were obtained.

Keywords: Grigoriadis – Khachiyan, Markov chain Monte Carlo, PageRank
Citation in English: Skachkov D.A., Gladyshev S.I., Raigorodsky A.M. Experimental comparison of PageRank vector calculation algorithms // Computer Research and Modeling, 2023, vol. 15, no. 2, pp. 369-379
Citation in English: Skachkov D.A., Gladyshev S.I., Raigorodsky A.M. Experimental comparison of PageRank vector calculation algorithms // Computer Research and Modeling, 2023, vol. 15, no. 2, pp. 369-379
DOI: 10.20537/2076-7633-2023-15-2-369-379
URL: http://crm-en.ics.org.ru/journal/article/3321/
Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Copyright © 2009–2024 Institute of Computer Science