PDF Publication Title:
Text from PDF Page: 107
RAPr has only one random parameter A ∼ Beta(a, b, [l , r]), so we can employ the one-dimensional interpolation and integration formulas to pro- duce highly accurate statistics. In this section we discuss their application to RAPr. For a modern reference on Gaussian quadrature, see Gautschi [2002]. In an N-point quadrature rule, we approximate rN f (x) dw(x) ≈ ∑ f (zG )wG , l (4.30) where zGi corresponding weights on those points. These nodes and weights are chosen to make the integration exact if f is a polynomial of degree less than 2N, and there are efficient algorithms to compute these rules [Golub and Welsch, 1969]. Note that the quadrature rule changes if the integration endpoints change, or if the weight function w changes. With the points and weights of the Gauss quadrature formula, we first solve N deterministic PageRank problems (I−zGP)x =(1−zG)v (4.31) iii using methods described in section 4.6.1. Then we can compute statistics of RAPr with the quadrature formulas E[x(A)]≈∑x wG, ii i=1 Cov[x(A)]≈∑x xTwG−(∑x wG)(∑x wG) . iii ii ii i=1 i=1 i=1 ii i=1 are the N nodes or points of a quadrature rule and wiG are the NNNN T (4.32) For the quadrature rule (4.30), the nodes zGi are known to lie on the interior of the integration region, l < zGi < r. Furthermore, the weights wiG are strictly positive. The first property is essential to using quadrature with PageRank when r = 1. It states that we do not have to compute a PageRank vector at α = 1. Many other quadrature rules, such as Clenshaw-Curtis,19 Gauss- Radau, or Gauss-Lobatto, all utilize a function value at one or both of the endpoints. For PageRank, computing the limit vector x(1) efficiently is still an open problem, and hence these alternatives are not appropriate. As program 7 shows, implementing the Gaussian quadrature algorithm is easy using the OPQ routines [Gautschi, 2002]. In the code, we adjust the solution tolerance of the linear system based on the weights of the final quadrature summation. We call this a weighted tolerance τ. 19 Fejér quadrature is a variant of Clenshaw-Curtis quadrature without the endpoints. It is less accurate than Gauss quadrature, but has nested point sets, which make it an attractive option in other settings. 4.6 ⋅ algorithms 85PDF Image | Instagram Cheat Sheet
PDF Search Title:
Instagram Cheat SheetOriginal File Name Searched:
pagerank-sensitivity-thesis-online.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 |