PDF Publication Title:
Text from PDF Page: 048
26 2 ⋅ pagerank background For strongly preferential PageRank on P ̄, a further optimization is y(k+1) = αP ̄x(k) x(k+1) = y(k) + (1 − eT y(k+1))v. (2.20) This optimization follows from P = P ̄ + vdT and dT = eT − eT P ̄ and is the iteration given in many PageRank papers [Page et al., 1999; Kamvar et al., 2003]. We regard (2.20) as the standard iteration, but prefer (2.19) for analysis purposes. As an algorithm, the power method continues this iteration until ∥x(k+1) − x(k)∥ ≤ τ for a user-provided tolerance τ. Deciding how to begin the power method is easy: follow the advice below. nota bene The power method always starts with x(0) = v. No one has suggested a better starting vector for the power method for PageRank than the vector v. the richardson iteration Surprisingly,thepowermethodforthe PageRank eigensystem is completely equivalent to the Richardson iteration [Varga, 1962] on the linear system (I − αP)v = (1 − α)v. The Richardson iteration for Ax = b is x(k+1) = x(k) + ω(b − Ax(k)), (2.21) and equivalence with (2.19) follows after substituting A = (I − αP), b = (1 − α)v, and ω = 1.3 3 Those familiar with the Richard- son method are likely wondering if ω = 1 is optimal. Good question. error analysis All error analysis below uses the 1-norm and exam- We cannot say and believe it to be ines the difference ∥x(k) − x∥ for the exact solution x and the current approx- imation x(k). Lemma3. LetxbetheexactPageRankvectorsatisfying(I−αP)x=(1−α)v. When computing PageRank, the power method ((2.19) or (2.20)) satisfies ∥x(k+1) − x∥ ≤ α ∥x(k) − x∥ . Proof. If we expand both x = αPx+(1−α)v and x(k+1) = αPx(k+1) +(1−α)v and then take the difference: ∥x(k+1) − x∥ = ∥αP(x(k) − x)∥ ≤ α ∥x(k) − x∥ . an open problem.PDF 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 |