PDF Publication Title:
Text from PDF Page: 103
4.7.4 Implementation correctness and convergence In this section, we present empirical results pertaining to the accuracy and convergence of our implementations. This type of analysis is important because numerical experimentation allows us to explore broader ranges of parameter values than may be feasible in the theoretical analysis. Addition- ally, it provides strong evidence that we have correctly implemented all the algorithms in this chapter. To begin, we use three experiments to verify that our algorithms are convergent when implemented with and without approxi- mate solutions of the linear algebra problems. Each of our algorithms has a 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. Our discussion continues with the figure on the next page. 25 The symbolic expressions for even a single component of the PageRank vector as a function of α are incredible. See figure 2.5. 4.7 ⋅ algorithm analysis 83PDF 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 | RSS | AMP |