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: 121

5.5 extensions In this section, we derive a few improvements to algorithm 2. 5.5.1 An inner-outer accelerated power method After a few outer iterations, the inner iterations of algorithm 2 converge rapidly. As previously mentioned, a single inner iteration is equivalent to a single step of the power method. Thus we can incorporate the following improvement to the power method: apply the inner-outer scheme, and once the inner iterations start converging quickly, switch back to the power method. After the switch, we eliminate the need to check the stopping criterion of the inner iteration and save touching one vector of memory. The change to algorithm 2 is simple. Add a line between 8-9 to check if the inner-iteration converged in less than im iterations, and if so, switch to the power method using the current iterate as the starting vector. The modified scheme is presented in algorithm 3. The value of im is small and determines the point, in terms of inner iteration count, where we switch to the power method. If im = 1 then switching to the power method saves the need to compute f and check the stopping criterion in line 8 of algorithm 2. This optimization saves touching an extra vector in memory and a 1-norm computation. In our numerical experiments we adopt this version of the accelerated algorithm, i.e. we take im = 1. The “power(αy + (1 − α)v)” clause in line 9 means apply the power method with αy + (1 − α)v as an initial guess, until convergence. Algorithm 3 – Inner-Outer power iterations. Input: P, α, β, τ, η, v, im Output: x 1: x ← v 2: y ← Px 3:while ∥αy+(1−α)v−x∥1 ≥τ x ← f + βy y ← Px until∥f+βy−x∥1 <η ifi≤im, x=power(αy+(1−α)v);return 5.5 ⋅ extensions 101 f ←(α−β)y+(1−α)v for i = 1, . . . repeat 4: 5: 6: 7: 8: 9: 10: end while 11: x ← αy + (1 − α)v 1 function [x,flag,reshist]=inoutpr(P,a,v,tol,maxit) 2 b=0.5*(a≥0.6); itol=1e-2; n=size(P,1); 3 x=zeros(n,1)+v; y=P’*x;y=y+(sum(x)-sum(y))*v; nm=1; f=a*y;f=f+(1-a)*v;f=f-x; 4 dlta=norm(f,1);x=x-b*y;reshist=[dlta;zeros(maxit-1,1)]; 5 while nmtol 6 f=(a-b)*y; f=f+(1-a)*v; x=x-f; % f=(a-b)*y+vt;x=x-b*y-f; 7 d = norm(x,1); ii=0; 8 while nm+iiitol, 9 x=b*y; x=x+f; y=P’*x; y=y+(sum(x)-sum(y))*v;ii=ii+1; % x=b*y+f;y=Pd’*x 10 x=x-b*y; x=x-f; d=norm(x,1); end % x=x-b*y-f; 11 if ii<2, x=a*y; x=x+(1-a)*v; y=y-x; break; end % no mult => no hist updte 12 x=x+f; f=a*y; f=f+(1-a)*v; f=f-x; f=f-b*y; dlta=norm(f,1); % ||a*y+(1-a)*v-x||_1 13 reshist(nm+1:nm+ii)=dlta; nm=nm+ii; end 14 while nmtol % run the power method until convergence 15 y=x./norm(x,1); x=a*(P’*y); w=1-sum(x); x=x+w*v; 16 y=y-x; dlta=norm(y,1); nm=nm+1; reshist(nm)=dlta; end 17 x=x./norm(x,1); flag=dlta>tol; reshist=reshist(1:nm); Program 8 – The inner-outer iteration for PageRank. The input to the inner-outer codeisa = α,v = v,P = PT,tol = ε, and maxit, an upper bound on the number of iterations. Our PageRank solvers are quite compact but work with PT for performance reasons. On Matlab R2007a and R2007b, the code uses only three vectors of storage.

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 (Standard Web Page)