PDF Publication Title:
Text from PDF Page: 096
76 4 ⋅ random alpha pagerank For a modern reference on Gaussian quadrature, see Gautschi [2002]. In an N-point quadrature rule, we approximate rN f (x) dw(x) ≈ ∑ f (zG )wG , ii (4.30) E[x(A)]≈∑x wG, ii i=1 Cov[x(A)]≈∑x xTwG−(∑x wG)(∑x wG) . iii ii ii i=1 i=1 i=1 l i=1 where zGi corresponding weights on those points. These nodes and weights are chosen to make the integration exact if f is a polynomial of degree less than 2N, and there are efficient algorithms to compute these rules [Golub and Welsch, 1969]. Note that the quadrature rule changes if the integration endpoints change, or if the weight function w changes. With the points and weights of the Gauss quadrature formula, we first solve N deterministic PageRank problems (I−zGP)x =(1−zG)v (4.31) iii using methods described in section 4.6.1. Then we can compute statistics of RAPr with the quadrature formulas are the N nodes or points of a quadrature rule and wiG are the NNNN T (4.32) For the quadrature rule (4.30), the nodes zGi are known to lie on the interior of the integration region, l < zGi < r. Furthermore, the weights wiG are strictly positive. The first property is essential to using quadrature with PageRank when r = 1. It states that we do not have to compute a PageRank vector at α = 1. Many other quadrature rules, such as Clenshaw-Curtis,19 Gauss- Radau, or Gauss-Lobatto, all utilize a function value at one or both of the endpoints. For PageRank, computing the limit vector x(1) efficiently is still an open problem, and hence these alternatives are not appropriate. As program 7 shows, implementing the Gaussian quadrature algorithm is easy using the OPQ routines [Gautschi, 2002]. In the code, we adjust the solution tolerance of the linear system based on the weights of the final quadrature summation. We call this a weighted tolerance τ. Program 7 – Matlab code for computing RAPr using Gaussian quadrature. Using Gautschi’s OPQ codes, r_jacobi01.m and gauss.m, a Matlab quadrature implementation is quite easy. 19 Fejér quadrature is a variant of Clenshaw-Curtis quadrature without the endpoints. It is less accurate than Gauss quadrature, but has nested point sets, which make it an attractive option in other settings. 1 function [ex,stdx] = gqrapr(P,N,a,b,l,r) 2 % first run these commands to get the OPQ codes 3 % urlwrite(’http://www.cs.purdue.edu/archives/2002/wxg/codes/gauss.m’,’gauss.m’) 4 % urlwrite(’http://www.cs.purdue.edu/archives/2002/wxg/codes/r_jacobi.m’,’r_jacobi.m’) 5 % urlwrite(’http://www.cs.purdue.edu/archives/2002/wxg/codes/r_jacobi01.m’,’r_jacobi01.m’) 6 tol=1e-9; maxit=1000; n=size(P,1); v=1/n; 7 ab=r_jacobi01(N,a,b); xw=gauss(N,ab); xw(:,2) = (1./beta(b+1,a+1))*xw(:,2); 8 xw(:,1) = (r-l).*xw(:,1)+l; % generate the quadrature rule by scale and shift 9 ex = zeros(n,1); stdx = zeros(n,1); % initialize running sums 10 for i=1:N 11 % solve the PageRank system 12 x = inoutpr(P,xw(i,1),v,min(tol./xw(i,2),1e-2), ... % adjust tol and maxit 13 2*ceil(log(min(tol./xw(i,2),1e-2))/log(xw(i,1))));% for mult by xw(i,2) 14 ex = ex+xw(i,2).*x; stdx = stdx+xw(i,2).*(x.^2); 15 end 16 stdx = sqrt(stdx - ex.^2); % convert to stdxPDF Image | MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY
PDF Search Title:
MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITYOriginal File Name Searched:
gleich-pagerank-thesis.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)