PDF Publication Title:
Text from PDF Page: 067
To be explicit, in the strongly-preferential case the PageRank vector satisfies (I − αP ̄ − αvdT)x(α) = (1 − α)x(α) and its derivative satisfies14 (I − αP ̄ − αvdT )x′(α) = 1 (x(α) − v). α Simply using strongly preferential solves does not work because the PageRank system for z(α) from (3.6) is ( I − α P ̄ − α v d T ) z ( α ) = ( 1 − α ) x ( α ) , which is a weakly preferential PageRank system. At this point, Boldi et al. [2007] provide a solution for a related problem They formalize that the strongly and weakly preferential PageRank systems are related by a rank-one change. Applying the Sherman-Morrison-Woodbury formula and an extra PageRank solve transitions between these formulations. For the derivative, applying this technique, however, then requires three Page- Rank solves. The extra solve is not necessary because a bit of algebra fixes the situation entirely, and there is no need for an explicit application of the Sherman-Morrison-Woodbury formula. Notice that (I−αP ̄)x′(α)= 1x(α)+(αdTx′(α)−1/α)v, α (I−αP ̄)x(α)=(1−α+αdTx(α))v, and (I − αP ̄)z(α) = (1 − α + αdT z(α))x(α). Consequently, x′(α) is still a linear combination of z(α) and x(α) where each is a strongly preferential PageRank vector. The coefficient for z(α) is available, so x′(α) = 1 z(α) + ηx(α). α(1 − α + αdT z(α)) We now exploit eT x′(α) = 0 to compute η and present algorithm 1 to compute the derivative. Algorithm 1 – Compute the derivative of PageRank. 1. Computex(α)asthesolutiontotheoriginalstronglypreferential PageRank problem, (I − αP ̄ − αvdT )x(α) = (1 − α)v. 2. Computez(α)asthesolutiontothestronglypreferentialPage- Rank problem with teleportation distribution x(α), (I − αP ̄ − αx(α)dT )x(α) = (1 − α)x(α). 3. Setz ̃= 1 z(α). α(1−α+αdT z(α)) − e T z ̃ 4. Computeη=eTx(α). 5. Returnx′(α)=z ̃+ηx(α). 14 This derivative is just the same as (I − αP)x′(α) with P = P ̄ + vdT , which supports working with P for PageRank theory. δ 3.2 ⋅ algorithms 47PDF 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)