PDF Publication Title:
Text from PDF Page: 064
44 3 ⋅ the pagerank derivative 3.1.2 The eigensystem Golub and Greif [2006] originally derived a formula for the derivative vector from the eigensystem formulation (2.3) of PageRank, namely Mx(α) = x(α), where M = αP + (1 − α)veT . Differentiating with respect to α yields the singular linear system (I − M)x′(α) = Px(α) − v. (3.2) We ought to be alarmed. Does this mean the eigensystem formulation admits multiple PageRank derivatives? In particular, given any solution x′(α) to (3.2), then x′(α) + θx(α) is also a solution.6 Lemma 6 saves the day. The problem with the eigensystem formulation is that the algebraic eigenvector x(α) has no imposed norm. In the above anal- ysis, we differentiated the problem independently of the imposed norm and thus we need to use it somehow. Remember that the proof of lemma 6 used the normalization of x(α) extensively. Thus, not all solutions x′(α) + θx(α) are derivatives. Only the vector with θ∗ such that eT x′(α) + θ∗eT x(α) = 0 is a PageRank derivative. Finally, then, impose the property eT x′(α) = 0 and the right-hand sides of both (3.2) and (3.1) become identical: (I − M)x′(α) = (I − αP − (1 − α)veT )x′(α) = (I − αP)x′(α). And thus, as we have seen a few times now,7 it does not matter whether we work with the eigensystem or the linear system. Though the linear system often tends to be less complicated. 3.1.3 PseudoRank In the previous chapter, we introduced PseudoRank and mentioned that it is loosely equivalent to PageRank.8 PageRank and PseudoRank are different— and importantly so with regard to the derivative. The PseudoRank system ((2.10)) is ( I − α P ̄ ) y = σ v , where σ may or may not depend on α. Most often, it does not [Gleich and Zhukov, 2005; McSherry, 2005; Langville and Meyer, 2006a]. When Pseudo- Rank is constructed with σ independent of α, then its derivative satisfies (I − αP ̄)y′(α) = P ̄y(α). This system has two important properties. First, while the PageRank deriva- tive satisfies eT x′(α) = 0, this PseudoRank derivative has y′(α) ≥ 0, 6 Remember that Mx(α) = x(α) and so x(α) is exactly the nullspace of (I − M)— which is of dimension 1 because the PageRank vector is unique. 7 The first example was the limiting vector in section 2.7. 8 A normalized PseudoRank and Page- Rank vector are identical for the strongly preferential PageRank problem.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 |