PDF Publication Title:
Text from PDF Page: 137
Consider an approximation of (I − βP ̄)−1 as a preconditioner for the PageRank linear system (I − αP ̄). Gleich et al. [2004] and Del Corso et al. [2007] examined the behavior of Krylov subspace methods on the system (I − αP ̄)y = (1 − α)v, (5.23) and concluded that, as expected in general, preconditioning is essential for the linear system formulation of the PageRank problem. Their preconditioners were incomplete factorizations or factorizations of diagonal blocks of the matrix, both of which modify the matrix data structure. System (5.23) is different from system (5.1) because we use P ̄ instead of P. It corresponds to using PseudoRank instead of PageRank, but the solutions of the two systems are proportional: x = y/∥y∥ .7 1 We switch to the alternate formulation with P ̄ for two primary reasons: it converged more often in our experience (we have no insight into why this occurs); and the behavior of Krylov methods has been empirically studied more often on this formulation of the system. For β near α, the preconditioned system is as difficult to solve as the original linear system. We thus consider a Neumann series approximation, which is practically equivalent to a Richardson approach as in the basic inner- outer iteration: (I−βP ̄)−1 ≈I+βP ̄+(βP ̄)2 +⋯+(βP ̄)m. Since β < 1 and ∥P ̄∥1 ≤ 1, this approximation converges as m → ∞, and it gives rise to an implementation that only uses matrix-vector multiplies with P ̄ and avoids costly (or even impossible) modification of the matrix structure. Details on the performance of this approach are provided in section 5.6. 7 See section 2.2.1 for the definition and equivalence between Pseudo- Rank and PageRank. Langville and Meyer [2006a, Theorem 7.2.1] also include a proof. The gist is that P = P ̄ +vdT andso(I−αP)x = ( I − α P ̄ ) x + γ v = ( 1 − α ) v . W e c a n move γv to the right-hand side and compute y with an unknown scale. 5.5 ⋅ extensions 115PDF Image | Instagram Cheat Sheet
PDF Search Title:
Instagram Cheat SheetOriginal File Name Searched:
pagerank-sensitivity-thesis-online.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 |