Pagerank computation with maaor and lumping methods

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2017

Autores

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

Ata de Conferência Internacional

Título: SYMCOMP 2017 - 3rd International Conference on Numerical and Symbolic Computation: Developments and Applications, Proceedings

Páginas: 49-64

3rd International Conference on Numerical and Symbolic Computation: Developments and Applications, SYMCOMP 2017

6 April 2017 through 7 April 2017

Indexação

Scopus - 0 Citações

Outras Informações

ID Authenticus: P-00N-HZK

Abstract (EN): How does the search engine Google determine the order in which to display web pages? The major ingredient in determining this order is the PageRank vector, which assigns a score to every web page. The PageRank vector is the left principal eigenvector of a web matrix that is related to the hyperlink structure of the web, the Google matrix. PageRank is one of the numerical methods Google uses to compute a page's importance and it is at the base of the success of the search engine. This numerical method 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. One of such tunings is the Lumping method approach [19, 13, 18]. 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 AOR (MAAOR) iterative method [10], which contains as particular cases the Accelerated Overrelaxation (AOR) [11] and the Generalized AOR (GAOR) [14] stationary family of methods, 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 the Lumping methods applied to PageRank computations are presented. © ECCOMAS, Portugal.

Idioma: Inglês

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