Efficient numerical methods to solve sparse linear equations with application to PageRank
(2022) Optimization Methods and Software — Vol. 37, n° 3, p. 907-935 (2022)
Files
CORE_RP_3232.pdf
Open Access - Adobe PDF
- 2.41 MB
Details
- Authors
Anikin, Anton 
Gasnikov, Alexander Gornov, Alexander Kamzolov, Dmitry Nesterov, Yurii
- Abstract
- Over the last two decades, the PageRank problem has received increased interest from the academic community as an efficient tool to estimate web-page importance in information retrieval. Despite numerous developments, the design of efficient optimization algorithms for the PageRank problem is still a challenge. This paper proposes three new algorithms with a linear time complexity for solving the problem over a bounded-degree graph. The idea behind them is to set up the PageRank as a convex minimization problem over a unit simplex, and then solve it using iterative methods with small iteration complexity. Our theoretical results are supported by an extensive empirical justification using real-world and simulated data.
- Affiliations
Citations
Anikin, A., Gasnikov, A., Gornov, A., Kamzolov, D., Maximov, Y., & Nesterov, Y. (2022). Efficient numerical methods to solve sparse linear equations with application to PageRank. Optimization Methods and Software, 37(3), 907-935. https://doi.org/10.1080/10556788.2020.1858297 (Original work published 2022)