PageRank Computation with MAAOR and Lumping Methods

• Type: Article in International Scientific Journal
• Date: 2018

Authors

Mendes, IR (Author) Other; vasconcelos, pb (Author) FEP

Journal

Title: Mathematics in Computer Science

Pages: 1-13

ISSN: 1661-8270

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 3 Citations

Scopus - 3 Citations

Other information

Authenticus ID: P-00N-QCJ

DOI: 10.1007/s11786-018-0335-7

Abstract (EN): PageRank is a numerical method that Google uses to compute a page¿s importance, by assigning a score to every web page. PageRank is thus at the basis of Google¿s search engine success and can be mathematically explored either as an eigenvalue problem or as the solution of a homogeneous linear system. In both cases the Google matrix involved is large and sparse, so tuned algorithms must be developed to tackle it with the lowest computational cost and minimum memory requirements. One of such tunings is the Lumping method approach. Furthermore, the accuracy of the ranking vector needs not to be very precise, so inexpensive iterative methods are preferred. In this work the recent Matrix Analogue of the Accelerated Overrelaxation (MAAOR) iterative method is explored for the PageRank computation. Additionally Lumping methods have been applied to the eigenproblem formulation and we propose a novel approach combining the Lumping and MAAOR methods for the solution of the linear system. Numerical experiments illustrating the MAAOR method and the MAAOR method combined with Lumping techniques applied to PageRank computations are presented. © 2018 Springer International Publishing AG, part of Springer Nature

Language: English

Type (Professor's evaluation): Scientific