PDF Publication Title:
Text from PDF Page: 049
A few groups started studying the effect of α around the same time. One of the first was Boldi et al. [2005]. Among other observations, they noted that x(α) is a rational vector function of α. Rational functions are ratios of poly- nomials. In figure 2.5 the caption notes that x1(α) = (−23/6030)f(α)/д(α). Carefully examining the functions f (α) and д(α) shows that they are indeed polynomials. It is not difficult to see why PageRank is a rational function. Consider Cramer’s rule [Meyer, 2000, page 476] for the solution of Ax = b: i det(Ai ) x=, 2.6 ⋅ the pagerank function of the damping parameter 29 det(A) where Ai = A with the ith column replaced by b. So each component of the solution of a linear system is a ratio of determinants. It so happens that the determinant is a polynomial in the matrix entries. When each entry in the matrix depends on a single parameter, say α as in (I − αP), then the determinant is going to be a polynomial in α. Replacing a column with b = (1 − α)v does not change the story for Ai and hence, each entry in the PageRank vector is a rational function of α. The second property that results from studying the function is that as α gets closer to 1, the PageRank vector becomes useless [Boldi et al., 2005]. Precisely, the web graph has a single large connected component and many terminal components. If any terminal components have size larger than 1— an example is nodes 5 and 6 in the graph above—then the PageRank values in the largest strong component are 0 when α = 1. The largest strong component is roughly 25% of the web and includes most of the interesting pages. These pages include important things like yahoo.com, microsoft.com, and many popular blogs. As α gets closer to 1, then, the PageRank vector degrades the PageRank value of these important pages, which renders it useless. Later, Avrachenkov et al. [2007] explored what α should be in light of this behavior. Using a theoretical model, they argue that α should be 1/2, and no larger. A cartoon version of the argument is that α = 0 produces the trivial ranking v and α = 1 produces a useless ranking. A good ranking should be far from both of these locations, and hence α = 1/2. To illustrate their point, they plot the PageRank mass, the sum of PageRank values at a subset of states, in the largest strong component as a function of α. In their theory, the mass in the largest strong component ought to begin decreasing around α = 1/2. These plots disagree and show that α can be larger than 1/2 before this happens. The plots themselves show interesting phenomena. In figure 2.4, we see that the strongly preferential PageRank model admits a larger α before significantly shedding mass in the largest strong component. Separately, Langville and Meyer included ideas in their book about the sensitivity with respect to α. A key tool in their analysis is x′(α), the derivative of the PageRank function. We return to a discussion of the derivative in chapter 3. Based on the derivative, their summary was that as α gets closer to 1, the PageRank vector becomes sensitive to small changes. Golub and Greif [2006] looked at computing the derivative to get a cheap sensitivity result about PageRank but found that it was just as expensive as computing Figure 2.4 – Strong component PageRank mass. For values of α between 0 and 1, this plots the sum of PageRank values inside the largest strong component of wb.cs-stan. The results differ for the strongly preferential model and show that it allows a larger value of α before the strong component starts losing mass. 0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.05 0 0 0.2 0.4 0.6 0.8 1 α Strongly preferential Sink preferential PageRank mass in largest componentPDF 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 |