PDF Publication Title:
Text from PDF Page: 117
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). Algorithm 2 – The basic inner-outer iteration. Input: P, v, α, τ, (β = 0.5, η = 10−2) Output: x 1: x ← v 2: y ← Px 3:while ∥αy+(1−α)v−x∥≥τ 4 This quantity is both the residual of the linear system for PageRank and the change after a single power iteration. end while x ← f + βy y ← Px until ∥f + βy − x∥ < η 5.2 ⋅ algorithms 97 f ←(α−β)y+(1−α)v repeat 4: 5: 6: 7: 8: 9: 10: x ← αy + (1 − α)v 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. 5.3 algorithm discussion Algorithm 2 has a number of properties worth noting. Consider the al- gorithm with β = 0. The inner loop will always exit after a single iteration because x is set to f. In this case, f = αy + (1 − α)v, but y = Px from the previous iteration. Thus, the inner-outer iteration with β = 0 is just the power method!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 | RSS | AMP |