PDF Publication Title:
Text from PDF Page: 115
5AN INNER-OUTER ITERATION FOR PAGERANK with 0 < β < α. This expression defines the outer iteration in our new scheme and corresponds to a PageRank problem with β instead of α and a different right-hand side.2 To apply these iterations in practice, we use a Richardson iteration to solve the inner system (I − βP)x(k+1) = f(k) y(0)≡x(k); y(j+1)=βPy(j)+f(k) j=1,...,l; (5.5) (5.6) yielding the inner iteration, We discuss how to terminate this iteration below, and show that keeping l small will accelerate convergence. The above scheme was initially proposed by Gray et al. [2007] in a tech- nical report. Subsequently, we have developed a new convergence analysis showing that the iteration always converges, a large-scale multi-core parallel implementation, a Gauss-Seidel variant, and an “inner-outer” preconditioner 95 Every block of stone has a statue inside it and it is the task of the sculptor to discover it. Michelangelo In the previous two chapters, we saw that computing both derivative of PageRank and the statistics of the RAPr model involve only solving PageRank problems. In this chapter, we develop an inner-outer iteration that solves PageRank as a series of PageRank problems with smaller values of α. Recall that PageRank as a linear system is the vector x that satisfies (I − αP)x = (1 − α)v, (5.1) or equivalently x = αPx + (1 − α)v. (5.2) In the Richardson iteration for PageRank, we convert this equation into a stationary iterative method by taking the previous left-hand side as the new iterate, that is x(k+1) = αPx(k) + (1 − α)v. (5.3) Well known spectral and convergence properties of the PageRank problem show that it is easier1 when α is closer to 0. Inspired by these results, we consider a stationary iteration given by the splitting 1 Easier in the sense that the condition number is smaller and the scheme in (5.3) converges linearly with rate α. 2 Formally, it is the PageRank problem (I−βP)x(k+1) = (1−β)zforz = α−β Px(k) + 1−α v. Because eTz = 1 and 1−β 1−β vi ≥ 0, it is a genuine PageRank problem. (I − βP)x(k+1) = (α − β)Px(k) + (1 − α)v ≡f(k) (5.4) x(k+1)≡y(l).PDF 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)