MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY

PDF Publication Title:

MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY ( models-and-algorithms-for-pagerank-sensitivity )

Previous Page View | Next Page View | Return to Search List

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 quadrature

PDF Image | MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY

PDF Search Title:

MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY

Original File Name Searched:

gleich-pagerank-thesis.pdf

DIY 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