ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATION

PDF Publication Title:

ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATION ( algorithms-for-pagerank-sensitivity-dissertation )

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

Text from PDF Page: 043

Proof. If we expand both x = αPx+(1−α)v and x(k+1) = αPx(k+1) +(1−α)v and then take the difference: ∥x(k+1) − x∥ = ∥αP(x(k) − x)∥ ≤ α ∥x(k) − x∥ . Thus, using the power method (or Richardson iteration) on PageRank con- verges linearly (or geometrically) with rate α. matlab Often, program code is the best way of understanding an algo- rithm and program 2 shows a complete Matlab implementation of the power method for the strongly preferential PageRank model. In this program, P = P ̄ T for efficiency. (Matlab stores sparse matrices by columns, and so P’*x is faster than P*x.) Following Wills and Ipsen [2009], this implementation includes the additional normalization step in the power method that we said was not required. Program 2 – The PageRank Power Method. PageRank (with the strongly preferential correction section 2.2.1) on a sub-stochastic matrix P is just a few lines of Matlab, even with optimiza- tions for a constant v. The function csum computes a compensated sum of a vector with the algorithm from section 2.4.1, and the normdiff function computes ∥x − y∥1 without comput- ing the difference as a separate vector. 1 function [x flag reshist]=powerpr(P,a,v,tol,maxit,verbose) 2 % 3% 4 % 5 % 6 % 7% 8 % 9 % 10 % 11 % 12 % 13 % 14 % 15 % 16 % 17 % 18 % 19 % 20 % 21 POWERPR Solve a PageRank system using the power method x=powerpr(P) solve a PageRank system with the row (sub-)stochastic matrix P with alpha=0.85 and uniform teleportation (in a strongly preferential sense) to an accuracy of 1e-12. If d = ones(n,1) - P*ones(n,1), then the output x satisifes ||x - alpha*(P + dv’)’*x + (1-alpha)*v||_1 ≤ 2*tol or (for small tol) x = alpha*(P + dv’)*x + (1-alpha)*v. [x flag reshist]=powerpr(P,a,v,tol,maxit) provides extra output and options for the value of alpha, the teleportation distribution vector v, the tolerance, and the maximum number of iterations. The output flag is 0 if the system converged and 1 otherwise. reshist is the vector of residuals from each iteration. Example: x=powerpr(P); 22 n=size(P,1); 23 if ~exist(’a’,’var’) || isempty(a), a=0.85; end 24 if ~exist(’v’,’var’) || isempty(v), v=1./n; end 25 if ~exist(’tol’,’var’) || isempty(tol), tol=1e-12; end 26 if ~exist(’maxit’,’var’) || isempty(maxit), maxit=10000; end 27 if ~exist(’verbose’,’var’) || isempty(verbose), verbose=0; end 28 x=zeros(n,1)+v; flag=0; delta=2; iter=0; reshist=zeros(maxit,1); 29 if verbose, dp=delta; end 30 while itertol 31 y=a*(P’*x); w = 1-csum(y); y = y + w*v; 32 delta=normdiff(x,y); reshist(iter+1)=delta; iter=iter+1; x=y./csum(y); 33 if verbose, fprintf(’power: m=%7i d=%8e r=%8e\n’,iter,delta,delta/dp); dp=delta; 34 end 35 end 36 flag=delta>tol; reshist=reshist(1:iter); 37 if flag, s=’finished’; else s=’solved’; end 38 fprintf(’%8s %10s(a=%6.4f) in %5i multiplies to %8e tolerance\n’, ... 39 s, mfilename, a, iter, delta); 2.4 ⋅ algorithms 23

PDF Image | ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATION

PDF Search Title:

ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATION

Original File Name Searched:

gleich.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