PDF Publication Title:
Text from PDF Page: 122
102 5 ⋅ an inner-outer iteration for pagerank When im = 1, then algorithm 3 and algorithm 2 produce exactly the same iterates. Once the inner iteration of algorithm 2 converges in a single iteration, then it will always converge in a single iteration. We hope we aren’t belaboring the point by reiterating that a single iteration of the inner iteration is precisely the power method. 5.5.2 Inner-Outer Gauss-Seidel iterations The performance of Gauss-Seidel applied to the PageRank linear system (I − αP)x = (1 − α)v is considered excellent, given its modest memory requirements. It often converges in roughly half the number of power method iterations. However, from a practical point of view, two pitfalls of the method are that it requires the matrix P by rows (i.e. the graph by in-edges) and it does not parallelize well. We can accelerate Gauss-Seidel using inner-outer iterations, as follows. Our Gauss-Seidel codes implement the dangling correction to the matrix P ̄ implicitly and match those in the law toolkit [Vigna et al., 2008]. To convert the inner-outer method to use Gauss-Seidel, we replace the inner Richardson iteration (5.6) with a Gauss-Seidel iteration. In our pseudo- code, presented in algorithm 4, the gssweep(x, A, b) function implements x(k+1) = M−1 (N x(k) + b) in-place for a Gauss-Seidel splitting of the ma- GS GS trix A.6 The gauss-seidel-pr function in line 7 of the algorithm refers to the standard “Gauss-Seidel for PageRank” scheme described in section 2.4.3 starting with the current x. This algorithm only requires two vectors of stor- age because x is always updated in-place. Details on the performance of this algorithm are provided in section 5.6. Algorithm 4 – The inner-outer/Gauss-Seidel iteration. Input: P, α, β, τ, η, v Output: x 1: x ← v 2: y ← Px 3:while ∥αy+(1−α)v−x∥1 ≥τ 4: f ←(α−β)y+(1−α)v 5: for i = 1, 2, . . . 6: x,δ←gssweep(x,I−βP,f){δ=∥x(i+1)−x(i)∥ } 1 6 This function is explicitly described in section 2.4.3. 7: until δ < η 8: if i=1, gauss-seidel-pr(x, I − αP, (1 − α)v); break 9: y ← Px 10: end repeatPDF 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)