PDF Publication Title:
Text from PDF Page: 024
4.2.1 PerformanceImprovements In their 2007 paper, Wills explored the use of the power method to compute the PageRank vector. The convergence rate for the power method depends only on the damping factor, d. While the power method is easily used in smaller systems, the Google matrix for the entire Internet network contains more than 25 billion rows and columns. Therefore, it is not feasible to compute an exact solution, but to approximate the PageRank. As shown in equation III.13, the PageRank r can be calculated with the power method. However, with the large size of the Google matrix G, it becomes com- putationally expensive to calculate it this way. Wills shows that the equation can be broken down in a way that is cheaper to calculate. By taking III.12 and III.9, and replacing it into III.13, we obtain: [rk]T = [rk−1]T (d(H + Dw) + (1 − d)ev) = d[rk−1]T H + d([rk−1]T D)w + (1 − d)([rk−1]T e)v = d[rk−1]T H + d([rk−1]T D)w + (1 − d)v (IV.1) Where [rk−1]T ∗ e = 1, because [rk−1]T is a probability vector, which sums to 1. The formula is the sum of three vectors, with the only vector-matrix multiplication being with H. Since the H matrix has more zero elements than G, it is cheaper to calculate. Wills also looked at the termination criteria of the power method. The method we have shown so far is to use the power method until ||rk −rk−1|| < e. While this is effective for finding the PageRanks, if the only interest is in providing a ranking to the webpages, it may be easier to solve only until a useful ranking can be ob- tained. For this, instead of a termination criteria being when ||rk −rk−1|| < e, they instead measure the correlation between the rankings in successive iteration, measured as the Kendall’s τ coefficient. 19PDF Image | MATHEMATICS BEHIND GOOGLE PAGERANK ALGORITHM
PDF Search Title:
MATHEMATICS BEHIND GOOGLE PAGERANK ALGORITHMOriginal File Name Searched:
MOOR-THESIS-2018.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 |