PDF Publication Title:
Text from PDF Page: 115
4.7 ⋅ algorithm analysis 93 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 Gaussian quadrature 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 0 1 2 3012345 10 10 10 10 10 10 10 10 10 10 0 5 10 15 20 25 30 35 40 Monte Carlo Path damping Gaussian quadrature (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. parameter N that controls the degree of approximation. Theoretically, all the algorithms are convergent as N → ∞. We first test this convergence by comparing with a semi-analytical solution. Using the symbolic toolbox inside Matlab, we compute the PageRank vec- tor as a rational function of α on the har500cc graph, a 335 node connected component.25 Using Mathematica, we then numerically integrate (4.32) for the expectation and standard deviation in 32-digit arithmetic. This process resolves the “exact” solution when converted to a double precision number. Finally, we track convergence of each algorithm to these semi-analytical solu- tions in figure 4.11a. As the respective N increases, all methods demonstrate convergence to the exact solution. For the same graph, we also analyze step- wise convergence by tracking the 1-norm change when incrementing N to N + 1 (figure 4.11b). These results use a direct method to solve any linear system that arises. Finally, we replace har500cc with cnr-2000, a 325,557 node graph, and use the inner-outer iteration to solve the PageRank systems with a tolerance of 10−8. In both of these cases, the algorithms are convergent. 25 The symbolic expressions for even a single component of the PageRank vector as a function of α are incredible. See figure 2.5.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 |