PDF Publication Title:
Text from PDF Page: 116
96 5 ⋅ an inner-outer iteration for pagerank for PageRank with the BiCG-STAB solver [van der Vorst, 1992]. These addi- tions are reported in Gleich et al. [to appear]. The goal of our inner-outer idea is a low-memory, matrix-free,3 and para- meter-free scheme to compute PageRank faster than the power method. Al- though we introduce the parameter β in the definition of the method, we show analytically and experimentally that β = 0.5 is an effective choice. The result is a PageRank scheme that takes merely three vectors of memory and consistently outperforms the power method by a substantial margin in time and matrix-vector products (see table 5.2, figure 1.4). Because the method is matrix-free, it is easy to parallelize, provided a parallel matrix-vector product exists. We present experiments demonstrating the parallel performance of the inner-outer algorithm on matrices with over 100,000,000 rows and 3.7 bil- lion non-zeros. Similar ideas give both an inner-outer Gauss-Seidel method and a matrix-free preconditioner for the BiCG-STAB iteration. These contri- butions are discussed below, as well as a non-web application of PageRank with the IsoRank algorithm [Singh et al., 2007]. 5.1 existing pagerank algorithms Improving the computation of PageRank is not a new problem, though we are not aware of any other PageRank specific method that simultane- ously satisfies all three criteria of our inner-outer algorithm: low-memory, matrix-free, and parameter-free. Our algorithm converges much faster than the power method, which is the only previous algorithm that has these three properties. We briefly summarize the existing literature. When looking at the linear system from (5.1), Arasu et al. [2002] investigated the Gauss-Seidel method, which is not matrix-free. Later, McSherry [2005] suggested a modi- fication of the Richardson iteration that exploits matrix structure. Some of the first improvements on the eigenvector problem were acceleration and extrapolation techniques [Kamvar et al., 2003, 2004], which are sensitive to the choice of parameter and often take considerable memory—approximately 6 vectors. Langville and Meyer [2006b] describe a method to update the sta- tionary distribution of a Markov chain that depends on having the matrix structure in-hand. Both Gleich et al. [2004] and Del Corso et al. [2007] look at Krylov subspace methods for the linear system. While these methods can be matrix-free, both studies find preconditioners are often required for con- vergence. Golub and Greif [2006] propose a specialized Arnoldi method that is matrix-free, but not low-memory. Another class of methods exploit properties of the graph structure to reduce the work involved in the computation [Eiron et al., 2004; Ipsen and Selee, 2007; Del Corso et al., 2005; Boldi and Vigna, 2004, 2005; Karande et al., 2009; Lin et al., 2009]. Because our method is matrix-free, for some of these methods we can integrate our inner-outer scheme with them to increase their effectiveness even further. 3 A matrix-free method relies only on the availability of a matrix-vector product, and not the matrix itself.PDF Image | MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY
PDF Search Title:
MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITYOriginal File Name Searched:
gleich-pagerank-thesis.pdfDIY PDF Search: Google It | Yahoo | Bing
Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info
Cruising Review Topics and Articles More Info
Software based on Filemaker for the travel industry More Info
The Burgenstock Resort: Reviews on CruisingReview website... More Info
Resort Reviews: World Class resorts... More Info
The Riffelalp Resort: Reviews on CruisingReview website... More Info
CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com (Standard Web Page)