PDF Publication Title:
Text from PDF Page: 066
46 3 ⋅ the pagerank derivative a big linear system From equation (3.1) we can express both the PageRank vector and its derivative vector in the solution to a single linear system. By solving: I − αP 0 x(α) (1 − α)v [ ][]=[] (3.3) −P I − αP x′(α) −v we simultaneously compute the solution vector for both PageRank and its derivative. Boldi et al. [2005] proposed computing the derivative in this manner by solving this linear system with a hybrid-Jacobi/block Gauss-Seidel procedure. One issue with this approach is that it requires solving a linear system twice the size of the PageRank system. Additionally, the linear system does not correspond to a PageRank problem, and it requires a general linear system solver. two smaller systems We could also, of course, solve the block-tri- angular linear system (3.3) by first solving (I − αP)x(α) = (1 − α)v and then solving (I − αP)x′(α) = Px(α) − v. But that algorithm is just solving the derivative linear system (3.1) directly.11 Instead of using these approaches, we devise a method to compute the PageRank vector analytically by solving two PageRank problems. The key to this result is an observation by Golub and Greif [2006]: 11 Techniques for multiple right-hand sides do not help in this case. The sys- tems are generally too big for any factor- izations, and other approaches are also inappropriate. Px(α)−v = 1(x(α)−v). α We use this result to rewrite equation (3.1) as (I − αP)x′(α) = 1 (x(α) − v). (3.4) (3.5) α The vector x′(α) then decomposes into a linear combination of two PageRank vectors: x′(α) = βz(α) − βx(α), (3.6) where(I−αP)z(α)=(1−α)x(α)andβ= 1 . Thisideayieldsan α(1−α) algorithm for computing the PageRank derivative as the solution of two PageRank systems with different teleportation distribution vectors but the same value of α. Berkhin [2005] also made this observation. This reduction is progress. It takes advantage of the structure of the deriva- tive to express it as a combination of PageRank solutions. Recall, however, that efficient algorithms for PageRank operate at the level of PageRank vari- ants. One concern with the previous approach is that it requires computing PageRank for a column stochastic matrix P. As discussed in section 2.2.2, many codes for PageRank choose to work with the column sub-stochastic ma- trix P ̄ and use the strongly preferential PageRank model with P = P ̄ + vdT .12 To maximize our computational advantage, we want to solve only strongly- preferential PageRank problems when starting with a strongly-preferential PageRank problem.13 Virtually all PageRank solvers work with P ̄ and implic- itly use the strongly preferential framework, whereas relatively few work with P or the weakly preferential framework. 12 A column sub-stochastic matrix satis- fies (eTP ̄)=⎧⎪⎨1 Pi,j>0foranyi i ⎪⎩0 Pi,j=0foralli. 13 For general problems, it will be hard to do better than using the reduction to problems with P.PDF 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 | RSS | AMP |