PDF Publication Title:
Text from PDF Page: 061
3THE PAGERANK DERIVATIVE Winston Churchhill There is nothing wrong with change, if it is in the right direction. The aim of this thesis is to study the sensitivity of PageRank with respect to the damping parameter α. Sensitivity, though more general, is often examined via perturbation. And perturbation theory, applied to PageRank, attacks the question: will a small change in α produce a large change in the PageRank vector? For a sufficiently small change, it is the derivative that determines the behavior of any smooth function,1 and the examination begins there. Using the derivative is a fine starting point, provided it exists. Does it? As discussed in the previous chapter (sections 2.6 and 2.7), PageRank is a rational function of α for all 0 ≤ α ≤ 1. Thus, the derivative exists. It even exists for complex α where ∣α∣ < 1, though that is not an important fact for this thesis. Existence sets the stage for the exploration in this chapter. Because the derivative exists, section 3.1 evaluates different algebraic formulations for the derivative vector. With an algebraic expression in hand, section 3.2 next demonstrates a few ways to compute the derivative. PageRank derivatives are remarkably close problems to PageRank and the best algorithm involves only computing PageRank, using any algorithm, and computing a second strongly personalized PageRank vector, again using any algorithm. Algorithms, especially efficient ones, enable experiments. Sometimes, ex- periments even expose theory. The experiments with the PageRank derivative in section 3.3 follow this trajectory and expose a nice property of a Taylor step along the PageRank derivative. Theory, of course, is not everything and the final section investigates the predictive power of the PageRank derivative. Studying the derivative began independently around 2004 in three papers. First, Golub and Greif [2006] mentioned it in a 2004 preprint. Second, Boldi et al. [2005] included the derivative for an extrapolation technique. Third, and finally, Berkhin [2005] includes methods to compute the derivative of PageRank.2 Throughout the chapter, we freely inject discussions of related background material, though the algorithm to compute the derivative is novel, as are pieces of the theoretical discussion. A lackluster conclusion is that the derivative seems too correlated with PageRank, and does not appear to provide any suf- ficient guidance with regard to appropriate value of α; although, experiments with web spam in the next chapter (section 4.8.4) show that the derivative does have some useful properties. 41 1 This follows from the Taylor series f(x)= f(x0)+(x−x0)f′(x)+ (1/2)(x − x0)2 f ′′(x) + . . . when x − x0 is small. In such a case (x − x0)2 is minuscule and f ′(x) determines the behavior. 2 Although two of these are 2005 publica- tions, most would have been submitted in 2004.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 |