PDF Publication Title:
Text from PDF Page: 092
72 4 ⋅ random alpha pagerank 4.6 algorithms In this section we describe and compare three methods for computing the approximate statistics, E [x(A)] and Std [x(A)], of the RAPr model. 4.6.1 PageRank One key component of these algorithms is a robust solver for a determin- istic PageRank problem with α < 1. For this task, we use two solvers: a direct method and an inner-outer method (chapter 5). The direct method uses the “backslash” solve in Matlab. In versions R2007a and R2007b, this command calls the umfpack 5.0 library [Davis, 2004]. For a row sub-stochastic matrix,16 we solve (I − αPT)y = v, x(α) = y/∥y∥ . (4.20) The inner-outer iteration requires only sub-stochastic matrix-vector prod- ucts, which makes it a natural choice for data structure-free algorithms.17 Program 8 is our implementation of the inner-outer method. Using the same code, the inoutpr function works with a native Matlab sparse matrix struc- ture as well as a Matlab wrapper around a BVGraph data structure [Boldi and Vigna, 2004] through a custom version of bvgraph or libbvg software (section 6.5). 4.6.2 Monte Carlo An enticingly straightforward method to compute the expectations, stan- dard deviations, and density functions of RAPr is to use a Monte Carlo method. To wit, first generate N realizations of A from a chosen distribu- tion, and then solve each resulting PageRank problem. With the N different realizations of x(αi), i = 1, . . . , N, we can compute unbiased estimates for E [x(A)] and Std [x(A)] with the formulas 16 For computational efficiency, all the Matlab programming uses row sub- stochastic matrices; see section 2.4.2 for more information. 17 Although using Gauss-Seidel iterations or a strong-component decomposition algorithm is typically faster, these algo- rithms require access to the graph as a structure and manipulate it. E[x(A)] ≈ S t d [ x ( A ) ] ≈ 1N ∑x(αi) ≡ μˆx, N i=1 N − 1 i=1 1 ix from Asmussen and Glynn [2007]. Unfortunately, as with any Monte Carlo method, these estimates con- √ verge as 1/ N [Asmussen and Glynn, 2007], which makes this approach prohibitively expensive for large graphs such as the web graph. The real advantage of the Monte Carlo method is its beautiful simplicity. The following short code is our entire implementation of the Monte Carlo method, including a numerically stable method to update the running vari- ance computation [Chan et al., 1983]. N ∑ ( x ( A ) − μ ˆ ) 2PDF 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 (Standard Web Page)