Efficient numerical methods to solve sparse linear equations with application to PageRank

Anton Anikin, Alexander Gasnikov, Alexander Gornov, Dmitry Kamzolov, Yury Maximov, Yurii Nesterov

Результат исследований: Вклад в журналСтатьярецензирование

1 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаАнглийский
ЖурналOptimization Methods and Software
DOI
СостояниеОпубликовано - 2020
Опубликовано для внешнего пользованияДа

Fingerprint

Подробные сведения о темах исследования «Efficient numerical methods to solve sparse linear equations with application to PageRank». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать