PDF Publication Title:
Text from PDF Page: 069
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 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−α = (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(γ), denoted x(w(γ), α). Note that x(w(γ), α) is not a strongly preferential Page- Rank vector. The norm of the differences are listed in table 3.1 for a few graphs and values of γ. These norms are quite small, demonstrating experimental evidence for the theorem. 3.3 ⋅ analysis 49 Graph = 0.001 aa-stan 1.72 × 10−10 ee-stan 5.62 × 10−11 cs-stan 5.31 × 10−11 cnr-2000 1.79 × 10−10 = 0.01 1.72 × 10−9 5.62 × 10−10 5.31 × 10−10 1.79 × 10−9 = 0.1 4.30 × 10−8 5.62 × 10−9 2.90 × 10−10 5.35 × 10−9 Table 3.1 – Experimental validation of theorem 7. The table entries show the value of ∥y(γ) − x(w(γ), α)∥2 using the notation from section 3.3.1 with α = 0.85. 3.3.2 Bounds An immediate implication of the previous theorem is that ′ . workstoshowthatx′(α)i >− 1 ,becauseotherwisey(1−α−ε)<0for 1−α x (α)i < Otherwise y(1 − α − ε)i > 1 for some small but positive ε.15 The same idea 15 In a less succinct statement, the idea istoassumethatx(α)i = 0anduse γ = 1−αtoboundthemaximumof x′(α)i so that y(γ)i < 1. some small ε. Thus ′1 ∣x (α)∣ ≤ . 1−α Using rather different techniques, Langville and Meyer [2006a, p.66] establish this same fact. As α → 1, these bounds become meaningless. What actually happens with the derivative at α = 1 is discussed next. 1 1−α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 |