PageRank Computation with MAAOR and Lumping Methods

• Tipo: Artigo em Revista Científica Internacional
• Data: 2018

Autores

Mendes, IR (Autor) Outra; vasconcelos, pb (Autor) FEP

Revista

Título: Mathematics in Computer Science

Páginas: 1-13

ISSN: 1661-8270

Editora: Springer Nature

Indexação

ISI Web of Knowledge - 3 Citações

Scopus - 2 Citações

Outras Informações

ID Authenticus: 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

Idioma: Inglês

Tipo (Avaliação Docente): Científica