Please use this identifier to cite or link to this item: http://hdl.handle.net/11144/3875
Title: A PageRank Algorithm based on Asynchronous Gauss-Seidel Iterations
Authors: Silvestre, Daniel
Hespanha, João
Silvestre, Carlos
Keywords: eigenvalues and eigenfunctions
graph theory
Internet
iterative methods
matrix algebra
search engines
topology
asynchronous version
Gauss-Seidel method
traditional power method
sparse link matrix
linear equations
page ranks
asynchronous algorithm
PageRank algorithm
asynchronous Gauss-Seidel iterations
PageRank problem
relative importance value
web pages
search engine
topology graph
sequential update
link matrix eigenvalue
Program processors
Convergence
Mathematical model
Eigenvalues and eigenfunctions
Web pages
Search engines
Tools
Issue Date: 27-Jun-2018
Publisher: IEEE
Citation: D. Silvestre, J. Hespanha and C. Silvestre, "A PageRank Algorithm based on Asynchronous Gauss-Seidel Iterations," 2018 Annual American Control Conference (ACC), Milwaukee, WI, 2018, pp. 484-489. doi: 10.23919/ACC.2018.8431212 keywords: {eigenvalues and eigenfunctions;graph theory;Internet;iterative methods;matrix algebra;search engines;topology;asynchronous version;Gauss-Seidel method;traditional power method;sparse link matrix;linear equations;page ranks;asynchronous algorithm;PageRank algorithm;asynchronous Gauss-Seidel iterations;PageRank problem;relative importance value;web pages;search engine;topology graph;sequential update;link matrix eigenvalue;Program processors;Convergence;Mathematical model;Eigenvalues and eigenfunctions;Web pages;Search engines;Tools}, URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8431212&isnumber=8430677
Abstract: We address the PageRank problem of associating a relative importance value to all web pages in the Internet so that a search engine can use them to sort which pages to show to the user. This precludes finding the eigenvector associated with a particular eigenvalue of the link matrix constructed from the topology graph of the web. In this paper, we investigate the potential benefits of addressing the problem as a solution of a set of linear equations. Initial results suggest that using an asynchronous version of the Gauss-Seidel method can yield a faster convergence than using the traditional power method while maintaining the communications according to the sparse link matrix of the web and avoiding the strict sequential update of the Gauss-Seidel method. Such an alternative poses an interesting path for future research given the benefits of using other more advanced methods to solve systems of linear equations. Additionally, it is investigated the benefits of having a projection after all page ranks have been updated as to maintain all its entries summing to one and positive. In simulations, it is provided evidence to support future research on approximation rules that can be used to avoid the need for the projection to the $n$-simplex (the projection represents in some cases a threefold increase in the convergence rate over the power method) and on the loss in performance by using an asynchronous algorithm.
Peer reviewed: yes
URI: http://hdl.handle.net/11144/3875
metadata.dc.identifier.doi: 10.23919/ACC.2018.8431212
ISBN: 978-1-5386-5428-6
ISSN: 2378-5861
Publisher version: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8431212&isnumber=8430677
Appears in Collections:DCT - Artigos/Papers

Files in This Item:
File Description SizeFormat 
pagerank.pdf264.86 kBAdobe PDFView/Open


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Currículo DeGóis 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.