PDF Publication Title:
Text from PDF Page: 098
78 4 ⋅ random alpha pagerank We begin our formal analysis by noting that the kth iterate from the power method on the PageRank system satisfies ∥x(k) − x⋆∥ ≤ 2ε (4.33) when k > log(ε)/ log(α) and x⋆ is the exact solution; that is, it takes at most k iterations (matrix multiplications) for the power method to get 2ε accuracy.20 Using the bound (4.33), we can estimate the expected number of iterations in the Monte Carlo method given that we are taking N samples: N r log(ε) E[M]=∑E[Mi]≤N ρ(τ)dτ, (4.34) 20 This result follows directly from lemma 3 with the initial error 2. Any two stochastic vectors have a 1-norm difference of at most 2, and so 2 is an upper bound on the initial error. Empiri- cally, the inner-outer method uses fewer iterations than the power method, so we use the upper bound from the latter. 1 τb(1−τ)a 1 τb(1−τ)a −(1−τ0)a dτ = dτ i=1 l log(τ) expected iterations for one sample where M is the total number of matrix-vector multiplies and Mi is the number of iterations in the ith random sample. In the case when ρ(τ) corresponds to a Beta distribution over (0, 1) with integer a > 0, b > 0, we can solve the integral analytically. From Zwillinger et al. [1996, p. 401], (4.35) both (1−τ)a and (1−τ0)−1 using binomial coefficients. Then we apply (4.35) with p or q = 0. Formally, 1 xp−xq 0 logx = log(p + 1) − log(q + 1), p > −1, q > −1. Now, recall and substitute the density function from (4.8) log(ε) 1 τb(1−τ)a E[M] = N dτ. (4.36) To compute the integral, we subtract 0 = (1 − 1) = (1 − τ0)a,21 then expand Beta(a+1,b+1) 0 logτ 21 For this problem, 1 − τ0 is the right value of 0 to subtract for an easy compu- tation. 0 logτ 0 logτ a a 1τk+b−τ0 = ∑(−1)k( ) (4.37) k=0 k 0 logτ aa =∑(−1)k[( )log(k+b+1)−log1]. k k=0 All of the previous work can be summarized in the following theorem. Theorem13. IfA∼Beta(a,b,[0,1])withintegersa>0andb>0,then approximating E [x(A)] with an N -sample Monte Carlo method takes logε a a N ∑(−1)k( )log(b+i+1) (4.38) Beta(a+1,b+1) k=0 k matrix multiplications.PDF 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 | RSS | AMP |