PDF Publication Title:
Text from PDF Page: 068
48 3 ⋅ the pagerank derivative No algorithm in this thesis is missing Matlab code, and program 4 shows a simple implementation of this algorithm. Program 4 – Strongly-preferential PageRank derivatives. Our PageRank codes for Matlab use row sub-stochastic matrices P. 1 function xp = derivpr(P,alpha,x,z) 2 % 3 % 4 % 5 % 6 % 7 % 8 d 9 zt = z./(alpha*(1-alpha+alpha*d’*z)); DERIVPR Compute the derivative of PageRank Given a PageRank vector x(alpha) and a PageRank vector y(alpha) that satisfy (I - alpha P’)x = (1-alpha)v (I - alpha P’)z = (1-alpha)x we produce the derivative of PageRank at alpha. = 1 - full(sum(P,2)); d = round(d); % compute the dangling vector 10 g = -csum(zt)/csum(x); 11 xp = zt + g*x; A full investigation of algorithms for PageRank derivatives ought to in- clude a discussion about the stability of the algorithms. Such a discussion is a glaring omission of this chapter as the vectors x and z in algorithm 1 will not be accurately computed. As an ode to the missing analysis, let us note that algorithm 1 produces a derivative vector that satisfies eT x′(α) = 0 to machine precision. This property should be useful for a backward stability analysis. Such analyses are usually difficult to conduct and we do not expect this case to be an exception. It is now time to address other properties of the derivative. 3.3 analysis Studying algorithm 1 from the previous section to investigate the deriva- tives reveals a few interesting properties. The investigation begins with taking a Taylor step along the 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. Graph ubc-cs 1 0.8 0.6 0.4 0.2 0 0 0.5 1 α Graph cnr-2000 Figure 3.1 – Valid Taylor steps. The maxi- mum values of γ until y(γ) loses positiv- ity are nearly linear at 1 − α. This figure inspired theorem 7. γ = max > 0 γ = min < 0 1 0.8 0.6 0.4 0.2 0 0 0.5 1 α γ = max > 0 γ = min < 0 |γ| |γ|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 (Standard Web Page)