PDF Publication Title:
Text from PDF Page: 099
One problem with this theorem is that it does not handle a = 0, b = 0—the case when A is uniformly distributed. Computing this expectation exactly 1 −1 is impossible in this case because the indefinite integral ∫0 log (τ) d τ does not converge. To handle this case, we would need to quantify the convergence of the power method when α is bigger than the second largest magnitude eigenvalue of P. More precisely, P has many eigenvalues on the unit circle. Let λ2 be the magnitude of the first eigenvalue inside the unit circle. We need the convergence of the power method when α > λ2 and that will depend more strongly on λ2 than on α. 4.7.2 Path damping When A ∼ Beta(a, b, [0, r]), r ≤ 1, we can explicitly bound the conver- gence of the path damping algorithm for E [x(A)]. Recall the path damping approximation from (4.22): NN E[x(A)]≈x(N) =∑E[Al −Al+1]Plv+(1−∑E[Al −Al+1])PN+1v. Note that Thus we have N (1−∑E[Al −Al+1])=E[AN+1]. l=0 (4.39) For r ≤ 1, (4.29) gives E[AN+2] = rN+2 Γ(b + N + 3)Γ(a + b + 2) Γ(b+1)Γ(a+b+N +4) l=0 l=0 ∞ ∥x(N)−x⋆∥=∥E[AN+2]PN+1v− ∑ E[Al−Al+1]Plv∥ l=N+2 ∞ ≤E[AN+2]+eT ∑ E[Al −Al+1]Plv l=N+2 ≤ 2E[AN+2]. We could have removed the final normalization term E[AN+1]PN+1v in the summation and bounded the result by E[AN+1] instead. However, the iter- ation we outlined in the algorithms section gives us better performance in practice.22 22 Give it a try yourself; maybe you will have a different experience. 4.7 ⋅ algorithm analysis 79 = rN+2 Γ(a + b + 2) Γ(b+1) 1 (b+N +3)(b+N +4)⋯(a+b+N +3) (4.40) ≤ rN+2 Γ(a + b + 2) 1 , Γ(b+1) (b+N+3)a+1 from which we conclude that the path damping algorithm for computing N+2 E [x(A)] converges like N a+1 . rPDF 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)