PDF Publication Title:
Text from PDF Page: 124
104 5 ⋅ an inner-outer iteration for pagerank 5.6 numerical results Using the data enumerated in table 2.2, we evaluated these implementa- tions in a wide range of experimental situations. The initial guess and telepor- tation distribution for every method is the uniform distribution, x(0) = v = (1/n)e, where e is a vector of all ones. We use this specific choice because it is commonly used. When we state a speedup, we use relative percentage gain vr −vt ⋅ 100% , (5.24) vr where vr is a reference performance and vt is a test performance. The refer- ence performance is either the power method or the Gauss-Seidel method. All solution vectors satisfy the residual tolerance ∥αPx(k) + (1 − α)v − x(k)∥ < τ, where τ is specified in the experiment description. Thus we are able to com- pare all methods directly in terms of total work and time. Parallel, large-scale (arabic-2005, sk-2005, and uk-2007), and C++ tests were run on an 8-core (4 dual-core chips) 2.8 GHz Opteron 8220 computer with 128 GB of RAM. Matlab mex tests were run on a 4-core (2 dual-core chips) 3.0 GHz Intel Xeon 5160 computer with 16 GB of RAM. Our codes are implemented in Matlab and C++. We implement both single-core and multi-core algorithms in C++ using the BVGraph data struc- ture for compressed web graphs [Boldi and Vigna, 2005]. 5.6.1 Inner-Outer parameters We first show the behavior of the inner-outer method for a range of graphs and parameters in figure 5.1. For β between 0 and 0.85 and η = 10−5 , 10−4 , 10−3 , 10−2 , 10−1 , we plot the number of matrix-vector multiplica- tions (equivalent to the number of iterations) until the inner-outer iteration converged. First, note that all instances converged and thus there is no numer- ical violation of the convergence theory for inner-outer iteration (theorem 17). Next, when α = 0.85, the inner-outer iteration with β = 0.5 and η = 10−2 uses fewer multiplications (than the power method) on the in-2004 graph, but not on the www graph. When α = 0.99, with these same β and η parameters, the inner-outer iteration uses roughly 30% fewer multiplications. Thus, the plots demonstrate that β = 0.5 and η = 10−2 are effective choices. Based on these same plots, picking η = 10−1 and β = 0.5 also seems a good choice. The results from in-2004 with α = 0.99 show that using η = 10−1 may be sensitive to the value of β, whereas using η = 10−2 reduces this sensitivity for a slight decrease in performance on the other graphs. Because our goal is robustness, we prefer the latter.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 |