PDF Publication Title:
Text from PDF Page: 168
148 7 ⋅ conclusion 7.2 future work We are almost done. There are some small loose ends (dangling nodes?) to address (connect?). Each is an idea to improve a piece of the results. 7.2.1 RAPr speed Although Gauss quadrature is the fastest method to compute the expecta- tion and standard deviation in the RAPr model, it is slow. We need to solve many PageRank problems at values of α that are close to 1. These vectors take considerable computation time. Gauss-Turán quadrature [Gautschi, 2004] uses derivatives in a quadrature rule. If we use 2s derivatives, then we get a rule with degree of exactness (2s+2)n−1. The error estimates extend to O(ρ−(2s+1)n) accuracy for certain weight functions [Milovanović and Spalević, 2003]. In other words, it satisfies all the properties of the Gauss quadrature rule, but uses derivatives instead of extra nodes. Computing PageRank derivatives can be done at the same value of α. Switching to this new quadrature rule seems a promising idea to speed the RAPr computations. One concern is that computing the nodes and weights for the Gauss-Turán quadrature rule involves solving a set of nonlinear equations. Algorithms exist to compute the weights. A brief test using the turan.m function from Gautschi [2002] showed convergence problems for all but the most trivial rules. For example, the Newton iteration did not converge for more than three quadrature points. This suggests that high-precision numerical codes using Mathematica may be required. One possible implementation is in the “OrthogonalPolynomials” Mathematica package [Cvetković and Milovanović, 2004] but it does not appear to be publicly available. It seems that using these rules first requires improving their computation. 7.2.2 Random modifications to other methods PageRank has a beautiful interpretation with a random parameter, but there are many other numerical methods to rank web pages. HITS [Kleinberg, 1999] and SALSA [Lempel and Moran, 2000] are two examples. Both of these methods are parameter free, and there is no analog of α to convert to a random value. We did not conduct an exhaustive survey to locate methods that would benefit from such a treatment, but there are many variations of PageRank—e.g. TrustRank [Gyöngyi et al., 2004], N-step PageRank [Zhang et al., 2007]—and some should benefit. At least one algorithm for learning a function on a graph includes a regular- ization parameter that is similar to PageRank [Zhou et al., 2005]. Computing a function with error bounds seems an exciting possibility for our methods. Finally, there are many mathematical models that describe a process on a network (e.g. [Atkinson, 2009]). Using random parameters should provide new insights into analyses from these models.PDF 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 | RSS | AMP |