MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY

PDF Publication Title:

MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY ( models-and-algorithms-for-pagerank-sensitivity )

Previous Page View | Next Page View | Return to Search List

Text from PDF Page: 095

Program 6 – Computing RAPr with path-damping. The first subfigure presents a compact algo- rithm to compute the moments of a Beta distribution. Next, we present our implementation of the path damping algorithms using the moments. Just as for the PageRank case, we perform our computations with P = PT for efficiency. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (a) Moment computation function m=beta_moments(N,a,b,l,r) c = l; s = (r-l); m=zeros(N+1,1); % c is the offset, s is the scale uk=1; k=0; sk=1; m(1) = uk; % uk are the Beta(a,b,0,1) moments for i=1:N, k = k+1; uk=s*uk*((b+k)/(a+b+k+1)); m(i+1) = uk; end % form the shifted and scaled moments % m are the Beta(a,b,l,r) moments if c ≠ 0, for i=1:N, m(i+1:end) = c*m(i:(end-1)) + m((i+1):end); end, end (b) Path damping computation function [ex,stdx] = pdrapr(P,N,a,b,l,r) tol=1e-9; maxterms=500; n=size(P,1); v=1/n; ms = beta_moments(2*(maxterms+1),a,b,l,r); i=0; delta=2; ex=zeros(n,1); y = zeros(n,1) + v; s=0; while itol Ptiv=y; ex = ex + (ms(i+1)-ms(i+2))*Ptiv; % setup the moments % setup vectors y = P’*(Ptiv); y = y + (1-norm(y,1)).*v; i=i+1; end % update P^i v ex = ex + ms(i+2)*y; % adjust with the last term % compute stdx with same number of terms of sequence nterms=i; ex2=zeros(n,1); Ptiv = zeros(n,1); Ptiv=Ptiv+v; Ptjv=Ptiv; for i=0:nterms, for j=0:nterms ex2 = ex2 + (ms(i+j+1)-2*ms(i+j+2)+ms(i+j+3))*(Ptiv.*Ptjv); y end y= = P’*(Ptjv); Ptjv = y + (1-norm(y,1)).*v; P’*(Ptiv); Ptiv = y + (1-norm(y,1)).*v; Ptjv(:)=0; Ptjv=Ptjv+v; 16 end 17 stdx = sqrt(ex2-ex.^2); 4.6.4 Gaussian quadrature Integration and interpolation are the fundamental concepts behind the class of uncertainty quantification techniques known as stochastic colloca- tion [Xiu and Hesthaven, 2005], which were originally developed in the con- text of partial differential equation models with stochastic inputs. Much of the work in this context has focused on the problem of high-dimensional pa- rameter spaces [Nobile et al., 2008], where multi-dimensional interpolation and integration can have a computational cost that increases exponentially with the dimension of the parameter space; one aspect of the so-called curse of dimensionality. RAPr has only one random parameter A ∼ Beta(a, b, [l , r]), so we can employ the one-dimensional interpolation and integration formulas to pro- duce highly accurate statistics. In this section we discuss their application to RAPr. % now update Ptiv and reset Ptjv % finish by update ex2 to be stdx 4.6 ⋅ algorithms 75

PDF Image | MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY

PDF Search Title:

MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY

Original File Name Searched:

gleich-pagerank-thesis.pdf

DIY 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