PDF Publication Title:
Text from PDF Page: 104
84 4 ⋅ random alpha pagerank 000 10 10 10 −5 −5 −5 10 10 10 −10 −10 −10 10 10 10 −15 −15 −15 10 10 10 012345012345 10 10 10 10 10 10 10 10 10 10 10 10 0 10 20 30 40 50 60 70 80 90 100 Monte Carlo Path damping (a) Convergence to analytical solutions (N vs. ∥y(N) − y⋆∥) on har500cc 000 10 10 10 −5 −5 −5 10 10 10 −10 −10 −10 10 10 10 −15 −15 −15 10 10 10 0123450123 10 10 10 10 10 10 10 10 10 10 0 10 20 30 40 50 60 70 80 90 100 Monte Carlo Path damping Gaussian quadrature (b) Stepwise convergence (N vs. ∥y(N+1) − y(N)∥) with direct methods on har500cc 000 10 10 10 −5 −5 −5 10 10 10 −10 −10 −10 10 10 10 −15 −15 −15 10 10 10 0123012345 10 10 10 10 10 10 10 10 10 10 0 5 10 15 20 25 30 35 40 Monte Carlo Path damping (c) Stepwise convergence (N vs. ∥y(N+1) − y(N)∥) with iterative methods on cnr-2000 Figure 4.11 – Convergence of algorithms for RAPr. All of our implementations converge with iterative methods and direct methods in a stepwise sense for y(N) ≈ E [x(A)] (dotted points) and y(N) ≈ Std [x(A)] (“+” points). Computing the standard deviation with path damping was too inefficient to include. The colors correspond to distributions from figure 4.4a. We now make a few additional observations: • the Monte Carlo method has similar convergence behavior for all dis- tributions and does not achieve better than typical accuracy for all tests; • theBeta(2,16,[0,1])problem(solidlightblueline)requiresthelargest N for all methods except Monte Carlo; • theaccuracyofthestandarddeviationislessthantheaccuracyofthe expectation; and • using stepwise convergence as a proxy for analytical convergence in path damping can produce significant errors. The last statement merits further comment. A simple calculation shows that stepwise convergence of the path damping expression is ∥x(N) − x(N+1)∥ = E[AN+2]∥PN+2v − PN+1v∥ , (4.43) PD PD which is how we compute the values for the figures. The theoretical bound is much weaker with ∥PN+2 − PN+1∥ replaced by the trivial value 2. When the vectors PN v reach a small value, stepwise convergence is no longer a good Gaussian quadrature Gaussian quadraturePDF 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)