Pagerank computation with maaor and lumping methods

• Type: Article in International Conference Proceedings Book
• Date: 2017

Authors

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

Conference proceedings International

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

Pages: 49-64

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

6 April 2017 through 7 April 2017

Indexing

Scopus - 0 Citations

Other information

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

Language: English

Type (Professor's evaluation): Scientific