Efficient numerical methods to solve sparse linear equations with application to PageRank
Anton S. Anikin, Alexander Vladimirovich Gasnikov, Alexander Yu. Gornov, Dmitry Kamzolov, Yury Maximov, Yurii E. Nesterov · Optimization methods & software · 2020
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.