PDF Publication Title:
Text from PDF Page: 045
and the updated entries (dsumn). Beyond that detail, the implementation is straightforwardly an implicit version of (2.22). But let’s outline the update at each iteration anyway! For Gauss-Seidel, there is no large benefit to working with strongly vs. weakly preferential PageRank and so the following iteration actually computes the update for the weakly preferential PageRank formulation. That is, A = (I − αP ̄ − αudT ). Suppose that θ = dT x before any changes to x, and that θ ̄ = dT x after we change an element of x. Let x ̄i be a temporary update value and di = 1 if page i is dangling. To update xi , the steps follow. 1. Computeτ=∑j=/i P ̄ijxj. 2. Add (θ + θ ̄)ui to τ but subtract ui if page i is a dangling page. 3. Finalize the value of x ̄ = ατ+(1−α)vi . i 1 − α P ̄ i i − α u i d i 4. If page i is dangling, subtract xi from θ and add x ̄i to θ ̄. 5. Accumulate the difference between xi and x ̄i . 6. Setxi =x ̄i. These steps correspond to the labeled steps in the Gauss-Seidel sweep func- tion. Gauss-Seidel has a few subtleties. Suppose P has no diagonal entries, then the power method, Richardson, and Jacobi iterations all coincide. Although the asymptotic performance of Gauss-Seidel is better than that of the Jacobi method, a simple test shows that this need not hold for the average perfor- mance. n = 10000; rand(’state’,0); % setup a 10000x10000 graph with adjacency matrix A A = sprand(n,n,10/n); A = spones(A); A = A - diag(diag(A)); P = normout(A); % normalize the out-degrees alpha = 0.99; % exacerbate the issue. [xp,flag,histp] = powerpr(P,alpha); [xp,flag,histgs] = gspr(P,alpha); fprintf(’power method takes %i iterations\n’, length(hist)); fprintf(’gauss seidel takes %i iterations\n’, length(histgs)); The results are startling: power method takes 25 iterations gauss seidel takes 304 iterations Such results, however, are not common. Figure 2.3 shows typical behavior on web graphs. the problem Gauss-Seidel is a fast algorithm for PageRank. Its fatal flaw is that it requires access to P ̄ by rows, but standard data structures provide access to P ̄ by columns. While transposing a matrix in Matlab is as easy as Pt = P’, for a gigantic matrix it is not as easy. So Gauss-Seidel imposes some restrictions on the data structures. Another problem with Gauss-Seidel is that it cannot be parallelized effectively. Parallel variants of Gauss-Seidel exist [Saad, 2003] but they require a good multicoloring of the graph structure Figure 2.3 – Gauss-Seidel vs. the power method. On the ubc-cs graph with α = 0.85, the Gauss-Seidel method handily beats the power method. 2.4 ⋅ algorithms 25 0 10 −3 10 −7 10 0 20 40 60 80 100 Iteration 0 Power 10 Gauss−Seidel −2 10 0 10 20 ResidualPDF Image | ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATION
PDF Search Title:
ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATIONOriginal File Name Searched:
gleich.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 (Standard Web Page)