PDF Publication Title:
Text from PDF Page: 042
22 2 ⋅ pagerank background Consider the power method on the PageRank eigensystem Mx = x. The largest eigenvalue is unique and equal to 1. Normalization at each step is not required because the largest eigenvalue of M is 1. Eliminating that step and expanding M (with (2.2)) yields the iteration x(k+1) = αPx(k) + (1 − α)veT x(k). (2.18) Recall that eT x = 1. A quick computation shows that when eT x(0) = 1, then eT x(k) = 1 for all iterations and thus x(k+1) = αPx(k) + (1 − α)v. 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.19) (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, the power method for the 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 Richardson method are likely wondering if ω = 1 is error analysis Allerroranalysisbelowusesthe1-normandexamines the difference ∥x(k) − x∥ for the exact solution x and the current approxima- tion 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∥ . optimal. Good question. We cannot say and believe it to be an open problem.PDF Image | ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATION
PDF Search Title:
ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATIONOriginal File Name Searched:
gleich.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)