PDF Publication Title:
Text from PDF Page: 097
4.7 algorithm analysis In this section, we compare and analyze the algorithms using theoretical and numerical techniques. As with many such comparisons, the theoretical analysis does not treat every case, and the numerical comparisons are always limited to the chosen experiments. Nevertheless, the combined examination yields strong suggestions for the choice of algorithm and implementation when applied to RAPr. For a compact summary of the properties of the methods, see table 4.2. The twin objectives of the analysis are work and accuracy. Both are typically proportional to N, the number of terms used in the approximate statistics. A description of N for the methods is in the table. Table 4.2 – Summary of convergence results for the RAPr model. A brief summary of our results about each method. A non-intrusive method only uses an existing PageRank solver. The Monte Carlo and Path Damping algorithms can be updated from N to N + 1 with no more work than another iteration, whereas the Gaussian Quadrature routines produce different instances when N is incremented. For storage, prsolve is the storage required to solve a PageRank problem, and P multiply is the storage required for the matrix P. The convergence results show how the norm of the error decays as a function of N, the intrinsic parameter of the method, and both a and r, the parameters from the Beta distribution. (a) Algorithm Properties 4.7 ⋅ algorithm analysis 77 Method Monte Carlo Path Damping Gaussian Quadrature Method Monte Carlo Path Damping (without Std [x(A)]) Gaussian Quadrature 4.7.1 Monte Carlo Non-Intrusive + - + Update + + - Storage prsolve + 2 n-vectors P multiply + 5 n-vectors prsolve + 2 n-vectors Conv. √1 N (b) Convergence Analysis Work Required N PageRank systems N + 1 matrix-vector products N PageRank systems What is N? number of samples from A terms of Neumann series number of quadrature points N+2 N 1+a r2N r Monte Carlo is not a deterministic technique. In it, we have to solve N PageRank systems at random values of α. The question we address here regards the work that this procedure requires. Each PageRank problem is solved iteratively and matrix-vector multiples with P dominate the work. We cannot find a precise number of matrix-vector multiplies because the work varies between runs. Instead, we compute the expected (or average) number.PDF 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)