PDF Publication Title:
Text from PDF Page: 129
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. 5.2 algorithms We always start our algorithms with x(0) = v, although other starting conditions are possible. To terminate the iterations, we use the 1-norm of the residuals of the outer system (5.1) and the inner system (5.5) as stopping criteria. For the outer iteration (5.4) we require4 ∥(1 − α)v − (I − αP)x(k+1)∥ < τ, and for the inner iteration (5.6) we require ∥f − (I − βP)y( j+1)∥ < η. The resulting inner-outer iteration, based on the iterative formulas given in (5.4) and (5.6), is presented in algorithm 2. Lines 1 and 2 of algorithm 2 ini- tialize x = v and y = Px. For the purpose of illustrating how the computation can be efficiently done, the roles of x and y are altered from the notation used in the text. Later, we show that β = 0.5 and η = 10−2 are effective choices of these parameters for all graphs (assuming α ≥ 0.85). The damping parameter α is assumed to be given as part of the model, and τ is a value typically provided by the user. Thus, the challenge is to determine values of β and η that will accelerate the computation. 4 This quantity is both the residual of the linear system for PageRank and the change after a single power iteration. 5.2 ⋅ algorithms 107PDF Image | Instagram Cheat Sheet
PDF Search Title:
Instagram Cheat SheetOriginal File Name Searched:
pagerank-sensitivity-thesis-online.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 | RSS | AMP |