PDF Publication Title:
Text from PDF Page: 044
24 2 ⋅ pagerank background on a graph Further optimizations of the power method are possible on standard graph data structures in other languages. First, constructing the sub-stochastic matrix explicitly is not required on most graph structures. Implicitly using the degree normalization saves memory. Second, in pro- gram 2, the quantity delta is computed after y is completely updated. In- stead, the program could accumulate this quantity while updating the vector y. Section 6.5.2 provides an optimized iteration on a compressed web graph structure. 2.4.3 Gauss-Seidel For the PageRank linear system (I − αP)v = (1 − α)v, an extremely simple linear solver is the Jacobi method. It is nearly the same as the Richardson iteration, but a few subtle differences confuse the two. (Looking at these differences is a fun exercise that won’t be covered here.) A close cousin of the Jacobi method is the Gauss-Seidel iteration, which is asymptotically faster [Varga, 1962]. See [Arasu et al., 2002; Del Corso et al., 2005] for comprehen- sive evaluations of the performance of Gauss-Seidel. It is fast and often takes only half the iterations of the power method with exactly the same work per iteration (or nearly so). The easiest way to understand the Gauss-Seidel iteration is to imagine a particular programming error in the Jacobi iteration. Thus there is no avoiding the Jacobi iteration, and we begin by describing it. For Ax = b, split A = DA − NA into its diagonal and negated off-diagonal components and then iterate: x(k+1) = DA−1(b + NAx(k)). If A is stored by rows, then a simple implementation is ⎛n⎞ (k+1) (k) xi = bi −∑Aijxj /Aii i=1,...,n. ⎝⎠ j =/ i Under well studied conditions, this iteration converges. Implementing this iteration requires allocating both x(k) and x(k+1). Gauss-Seidel follows by “forgetting” to allocate x(k+1) and updating x(k) in place, that is ⎛n⎞ (k) (k) xi ← bi −∑Aijxj /Aii i=1,...,n. (2.22) ⎝⎠ This change is reasonable and corresponds to using the most recent values of all the variables while solving the equations. To solve the PageRank linear system, do not compute A = (I − αP) and apply the iteration. Instead, proceed implicitly, just like for the power method. With just P ̄, working implicitly is easy; with P, it is hard. The law codes for PageRank [Vigna et al., 2008] describe the implicit implementation in some detail. In is implemented in the not-quite-complete program 3. Arguably the key step is separately accumulating dT x on the current iterate (dsum) j =/ iPDF Image | ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATION
PDF Search Title:
ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATIONOriginal File Name Searched:
gleich.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)