PDF Publication Title:
Text from PDF Page: 118
98 5 ⋅ an inner-outer iteration for pagerank Now, consider the case β = α. We intuitively expect that this method reproduces the power method because the inner iteration with β = α is solved with a Richardson iteration, which is the same as the power method.5 Here f = (1 − α)v for every inner iteration and thus every inner iteration corresponds to a step of the power method. When ∥f − βy − x∥ < η, we will do only one inner iteration for each outer iteration, but again, each step is just a step of the power method. Thus, we expect no acceleration with β = 0 or β = α. We make one final observation about the basic inner-outer method. For each outer iteration, the first inner iteration is always a step of the power method. We use this fact repeatedly in the remainder of the chapter. 5.4 convergence In the previous section, we showed that the algorithm corresponds to the power method when β = 0 or β = α. Convergence of the power method implies that the inner-outer iteration also converges with these parameters. In this section, we analyze the convergence for general 0 < β < α. We present the convergence analysis in two parts. First, we show that the outer iteration is a convergent scheme for the PageRank problem. Then we show that the outer scheme with an inner Richardson scheme will always converge on the PageRank problem. Lemma 15. Given 0 < α < 1, if the inner iterations are solved exactly, the scheme converges for any 0 < β < α. Furthermore, ∥x(k+1)−x∥≤α−β ∥x(k)−x∥, 1−β α−β where 1−β indicates that the closer β is to α, the faster the outer iterations converge. Proof. Let x be the PageRank vector and x(k) be the current iterate. The next 5 Check section 2.4.2 for the formal equivalence. iterate is x(k+1) = (I − βP)−1((α − β)Px(k) + (1 − α)v), and the solution is x = (I − βP)−1((α − β)Px + (1 − α)v). Subtracting these two expressions gives x − x(k+1) = (α − β)(I − βP)−1P(x − x(k)). The result now follows from applying 1-norms to both sides and using (5.7) (5.8) (5.9) (5.10) ∥(I−βP)−1P∥≤ 1 , 1−β which comes from ∥(I − βP)−1P∥ ≤ ∥∑∞ (βP)l∥ ≤ l=0 1 . 1−β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)