PDF Publication Title:
Text from PDF Page: 156
136 6 ⋅ software We evaluate each function on either a small set of sample graphs (dfs and dijkstra) or a set of synthetic graphs (scomponents, dirclustercoeffs, prim_mst, and clustercoeffs). For each function, we call it once to ensure that the Matlab just-in-time compiler has the current version compiled. The two search functions that begin with a source vertex—dfs and dijkstra— are called on each of the graphs listed in table 6.2 with 100 random starting vertices, and every test is repeated 30 times. The functions scomponents and dirclustercoeffs are evaluated on 30 instances of random directed graphs with 25 edges per row and 10, 100, 5000, 10000, and 50000 vertices. The function clustercoeffs is evaluated similarly, but with random symmetric graphs instead. Finally, the minimum spanning tree function is evaluated on 30 instances of a random symmetric graph with average degree 25 and 100, 5000, and 10000 vertices. The aggregated results of all these tests are shown in figure 6.4. Graph Verts. Edges allsp1 5 9 clr24-1 9 14 wb-cs.stan 9914 36584 minnesota 2642 3303 tapir 1024 2846 Table 6.2 – gaimc evaluation graphs. 14 12 10 8 6 4 2 0 Standard Fast dfs scomponents dijkstra dirclustercoeffs mst_prim clustercoeffs Figure6.4–Performanceofthegaimclibrary. Anexperimentalcomparisonoftheperformance of the gaimc library to MatlabBGL shows that many functions in gaimc take only twice as much time as their MatlabBGL counterparts. The difference between the standard and fast operations is that fast operations eliminate any data translations and measure pure algorithm speed. Standard calls in these libraries involve some data translation, which is included in the time for the standard operations. With the exception of mst_prim, the gaimc functions are roughly 2-4 times slower than their MatlabBGL counterparts. At the moment, we don’t understand why the dfs function is faster in gaimc or why the mst_prim routine has dramatically different performance. Exploring these differences is a task for the future. 6.5 libbvg and bvgraph’s in matlab The final software package that we discuss in this chapter is libbvg and its Matlab counterpart bvgraph. All the source code and examples for these paired packages are online at the LaunchPad open-source hosting repository, https://launchpad.net/libbvg.19 Both of these packages work with web graphs, which are graphs formed by hyper-linking relationships on the world wide web. These graphs are extremely large—the complete network has over one trillion nodes [Alpert and Hajaj, 2008]—and subsets often have more than one hundred million 19 We anticipate migrating them to the github system soon. SlowdownPDF 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 |