PDF Publication Title:
Text from PDF Page: 126
106 5 ⋅ an inner-outer iteration for pagerank In the next investigation, we show the convergence of the iterates for the wb-edu graph in figure 5.2. For both values of α shown in the plots (α = 0.85 and α = 0.99), the inner-outer iteration uses fewer multiplications. The advantage is derived from accelerated convergence in all of the iterations. Recall that the inner-outer iteration switches back to running iterations of the power method after the inner-outer iterations converge instantly. For these cases, that occurred after roughly 10 and 20 outer iterations, respectively. Thus, this observation indicates that the convergence rate of the power method changes when used after the inner-outer iteration. We return to this point in section 5.6.6. wb−edu, α = 0.85 10 0 10 wb−edu, α = 0.99 Figure 5.2 – Performance of the PageRank algorithm. Theinner-outermethod clearly outperforms the power method on wb-edu with α = 0.85 on the left and α = 0.99 on the right. The small inner figure shows the convergence in the first few iterations. 0 −1 0 10 10 −1 0 10−2 −3 10 −4 10 −5 10 −6 10 −7 10 10−2 10−2 −2 10 10 10 Residual Residual power inout −3 10 −4 10 −5 10 −6 10 −7 10 power inout 10 20 30 40 50 60 70 80 Multiplication 200 400 600 800 1000 1200 Multiplication 5 101520 20 40 Table 5.1 shows that the inner iteration counts per outer iteration decrease monotonically down to a single iteration quite quickly. From the table we can see that it takes 24 inner iterations overall (within 9 outer iterations) until the inner iterates start converging immediately, at which point we switch to the power method. inner iterations for outer iteration Table 5.1 – Inner iteration counts. Shown are the number of inner iterations for each outer iteration when α = 0.99, β = 0.5, and η = 10−2. Total iteration counts and CPU times for this example can be found in table 5.2. graph wb-edu 4 3 3 3 2 2 2 2 2 1 eu-2005 4 4 3 3 2 2 2 2 2 1 Finally, we evaluate work and time for the inner-outer iteration on many graphs in table 5.2. The inner-outer scheme with β = 0.5 and η = 10−2 is almost always faster in these experiments. From the wall-clock times reported, we can see that there is not any significant overhead. For loose outer tolerances (10−3), the inner-outer iteration uses 45% fewer iterations than the power method and for tight outer tolerances (10−7), it almost 30% fewer iterations. The results are consistently faster and involve no parameter search. 1 2 3 4 5 6 7 8 9 10PDF 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 |