PDF Publication Title:
Text from PDF Page: 078
56 3 ⋅ the pagerank derivative 3.3.1 Taylor steps A key property of the PageRank vector is that it is a probability distribution. Thus, eTx(α) = 1 and x(α) ≥ 0. Consider approximations of PageRank i vectors using the derivative y(γ) = x(α) + γx′(α). (3.7) This equation is just a first order Taylor approximation of the function x(α+γ) around α. When is y(γ) also a probability distribution? The answer to this question reveals when y(γ) should not be used as an approximate PageRank vector. Figure 3.1 shows that γ ≈ 1 − α is the largest positive step until any com- ponent of y(γ) dips below 0 or exceeds 1. The minimum values of γ until y(γ) is no longer a probability distribution are always less than 0 but are not nearly as structured as the permissible positive set. This experiment inspired the following theorem. Theorem 7. Fix P, v, and α and let x(α) and x′(α) be the PageRank vector and derivative with respect to α. Then y(γ) = x(α) + γx′(α) is a PageRank Graph ubc-cs Graph cnr-2000 Figure 3.1 – Valid Taylor steps. The maximum values of γ until y(γ) loses positivity are nearly linear at 1 − α. This figure inspired theo- rem 7. vector for 0 ≤ γ < 1 − α with teleportation distribution vector w(γ) = α − γ)v + γPx(α)). Proof. The proof is straightforward and follows by computing (I − αP)y(γ) = (I − αP)x(α) + γ(I − αP)x′(α) = (1 − α)v + γ(Px(α) − v) 1 ((1 − 1−α (3.8) = (1 − α)w(γ). First,noticethateTw(γ)=1.Toverifyw(γ) ≥0itsufficestoshow(1−α− i γ)vi + γ[Px(α)]i ≥ 0. From vi ≥ 0, we have x(α)i ≥ 0 and then γ[Px(α)]i ≥ follows.From0≤γ<1−α,wehave(1−α−γ)vi ≥0andthenw(γ)i isthe sum of two positive quantities. Showing non-negativity, and thus confirming figure 3.1, was the point of this theorem. It accomplishes this goal. For any γ < 1 − α, y(γ) is a non-negative probability distribution vector. It is, however, more than just any positive vector, it’s a PageRank vector with the same α, just a different teleportation distribution. To confirm theorem 7, we examine the difference between the approxi- mation y(γ) and the PageRank vector with teleportation distribution w(γ), 1 0.8 0.6 0.4 0.2 0 0 0.5 1 α γ = max > 0 γ = min < 0 1 0.8 0.6 0.4 0.2 0 0 0.5 1 α γ = max > 0 γ = min < 0 |γ| |γ|PDF 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 (Standard Web Page)