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

Program 5 – Computing RAPr with Monte Carlo. A Monte Carlo code in Matlab to estimate the expectation and standard deviation of the RAPr model. 4.6.3 Path damping As discussed in sections 4.3.3 and 4.4.3, path damping algorithms for Page- Rank are not novel. RAPr simply provides a large set of functions that gener- ate the path damping coefficients. In this section, we will discuss using these ideas to compute E [x(A)] and Std [x(A)]. Recall the Neumann series from theorem 9, ∞ E[x(A)]=∑E[Al −Al+1]Plv. (4.21) l=0 If we truncate this series to a finite value N, then an algorithm for E[x(A)] immediately follows: NN E[x(A)]≈x(N) =∑E[Al −Al+1]Plv+(1−∑E[Al −Al+1])PN+1. l=0 l=0 (4.22) The final term in this summation ensures that eT x(N) = 1 for the path damp- ing approximation. To compute Std [x(A)] using the path damping equations we compute E [x(A) ● x(A)] and then compute √ 4.6 ⋅ algorithms 73 1 2 3 4 5 6 7 8 9 10 11 function [ex,stdx] = mcrapr(P,N,ba,bb,bl,br) tol=1e-9; maxterms=500; n=size(P,1); v=1/n; alphas = betarnd(bb+1,ba+1,N,1)*(br-bl) + bl; ex=zeros(n,1); stdx=zeros(n,1); for i=1:N % solve the PageRank system x = inoutpr(P,alphas(i),v,tol,2*ceil(log(tol)/log(alphas(i)))); % update the running solution sum and variance sum formulas ex = ex+x; if i>1, stdx = stdx + (1./(i*(i-1))).*(i*x-ex).^2; end end ex = ex./N; stdx=sqrt(stdx./(N-1)); % compute the mean and std Std [x(A)] = Based on the Neumann expansion, E [x(A) ● x(A)] − (E [x(A)] ● E [x(A)]). ∞∞ E[x(A)●x(A)]=∑∑E[Ai+j −2Ai+j+1 +Ai+j+2](Piv)●(Pjv). (4.23) i=0 j=0 And again, we truncate this series to a common term in both i and j: N E[x(A)2]≈s(N) =∑E[Ai+j −2Ai+j+1 +Ai+j+2](Piv)●(Pjv). (4.24) i,j Note that we do not apply any correction to the sum to ensure a summation property of the solution as in the case for E [x(A)].

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