PDF Publication Title:
Text from PDF Page: 160
140 6 ⋅ software 6.5.3 bvgraph The last section discussed a case when using a high-level language like Matlab incurred a possible performance penalty. Nevertheless, using Matlab often increases productivity in other aspects of work. Our final package is bvgraph, which is a Matlab class to work with libbvg. The bvgraph class (in the bvgraph package) creates a Matlab object that presents a libbvg bvgraph type as an adjacency matrix. For example, G = bvgraph(’wb-cs.stanford’); d = sum(G,2); D = diag(G); y = G*rand(n,1); loads the file wb-cs.stanford.graph into memory with libbvg and then computes the degrees of each node by summing a row of the “matrix”; extracts the diagonal entries of the “matrix”; and performs a “matrix”-vector product. The “matrix” in this case is the adjacency matrix of the wb-cs.stan graph. With the bvgraph class, this graph always stays compressed and can reside in main memory (RAM) for faster access, or be streamed from disk when memory is tight. The focus of this thesis is PageRank, and we are willing to spend a bit more time to make PageRank work efficiently. Using just the bvgraph class, unfor- tunately, makes PageRank inefficient. Consider the matrix-vector product with P given only the adjacency matrix G: d = sum(G,2); id = full(spfun(@(x) 1./x, sparse(d))); y = G’*(x.*id); This computation requires storing an extra vector id. For a graph with 108 nodes (such as webbase-2001), an extra vector takes nearly one gigabyte of memory. For many machines, storing an extra vector of memory may not be possible. To address this problem, we introduce the ssbvgraph class: P = ssbvgraph(G); y = P’*x; The ssbvgraph class is a sub-stochastic bvgraph, because it computes a sub- stochastic matrix-vector product. It computes this product implicitly by taking advantage of the same implicit normalization that program 9 used. Using this class, we can substitute a ssbvgraph object for a sub-stochastic matrix in many of the Matlab codes for PageRank given throughout this thesis.23 Together, these classes make it easy to work with huge graphs in Mat- lab. They introduce minimal memory overhead, and integrate nicely with standard Matlab matrix operations. We now end our discussion of the three software packages composed for this thesis. 23 The ssbvgraph class works with both program 2 (the power method), program 5 (Monte Carlo RAPr), pro- gram 6 (path damping RAPr), program 7 (quadrature RAPr), and and program 8 (the inner-outer iteration). It does not work with any of the Gauss-Seidel rou- tines.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 |