PDF Publication Title:
Text from PDF Page: 132
112 5 ⋅ an inner-outer iteration for pagerank Table 5.4 – Inner-Outer preconditioned BiCG-STAB performance. Matrix-vector products required for BiCG-STAB on in-2004, including preconditioning and residual computations, to converge on the system (I − αP ̄ ) with preconditioner ∑m (βP)k . A dash indicates the method made k=0 √ progress but did not converge to a tolerance of ( 1 − α)10−7 in the maximum number of iterations required for the power method (100 for α = 0.85, ≈1500 for α = 0.99, ≈15000 for α = 0.999), and an × indicates the method diverged or broke-down. When m = 0, there is no preconditioning and the results are independent of β. α 0.85 0.99 0.999 m 0.25 0 102 2 128 4 186 7 — 25— 0.50 0.75 0.85 102 102 102 88 76 76 120 84 78 207 108 72 — — 81 0.25 0.50 0.75 0.85 0.25 0.50 0.75 0.85 βββ ×××× 1140 672 508 500 1584 786 438 414 2565 1053 621 441 — — 1809 1026 ×××× × 6276 3972 2772 × 5178 2358 2112 × 9567 2709 1449 — 20385 7911 2754 BiCG-STAB diverges or breaks down on in-2004 without precondition- ing for α = 0.99, see table 5.4. This matches observations by Del Corso et al. [2007] that Krylov methods often have convergence difficulties. Adding the preconditioner with m = 2 and β ≥ 0.5 avoids these break-down cases. The remainder of the table shows that preconditioning accelerates conver- gence in many cases for “reasonable” parameter choices. Among the methods discussed, BiCG-STAB with this preconditioner converges with the fewest matrix-vector multiplications on the in-2004 graph with α = 0.99 and α = 0.999. However, the cost per iteration is higher. 5.6.5 Other applications The IsoRank algorithm [Singh et al., 2007] is a heuristic to solve the net- work alignment problem. Given two graphs, A and B, the goal in the network alignment problem is to find a match for each vertex of graph A in B and vice-versa. The resulting matching should maximize the number of cases whereiinAismappedto jinB,i′ inAismappedto j′ inB,andbothof the edges (i, i′) ∈ A and (j, j′) ∈ B exist. This objective alone is NP-hard. Often there are weights for possible matches, e.g. Vji for i in A and j in B, that should bias the results towards these matchings, and hence the objective also includes a term to maximize these weights. Let P and Q be the uniform random-walk transition matrices for A and B, respectively. Also, let the weights in V be normalized so that eT Ve = 1 and Vi j ≥ 0. IsoRank uses the PageRank vector x = α(P ⊗ Q)x + (1 − α)v, where the teleportation vector v = vec(V) encodes the weights and α indi- cates how much emphasis to place on matches using the weights information. Thus the IsoRank algorithm is a case when v is not uniform, and α has a morePDF 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)