## Group GAP

Group Description |
GAP Benchmark matrices: Scott Beamer, Krste Asanovic', and David Patterson. as described in "The GAP Benchmark Suite", https://arxiv.org/abs/1508.03619 . (1) GAP-twitter (|V|=61.6M, |E|=1,468.4M, directed) is an example of a social network topology [18]. This particular crawl of Twitter has been commonly used by researchers and thus eases comparisons with prior work. By virtue of it coming from real-world data, it has interesting irregularities and the skew in its degree distribution can be a challenge for some implementations. [18] Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. What is Twitter, a social network or a news media? International World Wide Web Conference (WWW), 2010. A permuted version of this matrix appears as SNAP/twitter7 in the SuiteSparse Matrix Collection. (2) GAP-web (|V|=50.6M, |E|=1,949.4M, directed) is a web-crawl of the .sk domain (sk-2005) [9]. Despite its large size, it exhibits substantial locality due to its topology and high average degree. The matrix comes from the Laboratory for Web Algorithmics (LAW), Universita degli Studi di Milano, http://law.di.unimi.it/index.php. The pattern of this GAP-web matrix also appears as LAW/sk-2005, in the SuiteSparse Matrix Collection. (3) GAP-road (|V|=23.9M, |E|=58.3M, directed) is the distances of all of the roads in the USA [10]. Although it is substantially smaller than the rest of the graphs, it has a high diameter which can cause some synchronous implementations to have long runtimes. [10] 9th DIMACS implementation challenge -- shortest paths. http://www.dis.uniroma1.it/challenge9/, 2006. The pattern of the GAP-road matrix also appears as DIMACS10/road_usa in the SuiteSparse Matrix Collection. (4) GAP-kron (|V|=134.2M, |E|=2,111.6M, undirected) uses the Kronecker synthetic graph generator [19] with the same parameters as Graph 500 (A=0.57, B=C=0.19, D=0.05) [14]. It has been used frequently in research due to Graph 500, so it also provides continuity with prior work. [19] Jurij Leskovec, Deepayan Chakrabarti, Jon Kleinberg, and Christos Faloutsos. Realistic, mathematically tractable graph generation and evolution, using Kronecker multiplication. European Conference on Principles and Practice of Knowledge Discovery in Databases, 2005. [14] Graph500 benchmark. www.graph500.org. (5) GAP-urand (|V|=134.2M, |E|=2,147.4M, undirected) is synthetically generated by the Erdos– Reyni model (Uniform Random) [11]. With respect to locality, it represents the worst case as every vertex has equal probability of being a neighbor of every other vertex. When contrasted with the similarly sized kron graph, it demonstrates the impact of kron’s scale-free property. [11] Paul Erdos and Alfred Reyni. On random graphs. I. Publicationes Mathematicae, 6:290–297, 1959. |
---|

Displaying

**all 5**collection matricesId | Name | Group | Rows | Cols | Nonzeros | Kind | Date | Download File |
---|---|---|---|---|---|---|---|---|

2855 | GAP-kron | GAP | 134,217,726 | 134,217,726 | 4,223,264,644 | Random Undirected Weighted Graph | 2017 | MATLAB Rutherford Boeing Matrix Market |

2854 | GAP-road | GAP | 23,947,347 | 23,947,347 | 57,708,624 | Directed Weighted Graph | 2017 | MATLAB Rutherford Boeing Matrix Market |

2852 | GAP-twitter | GAP | 61,578,415 | 61,578,415 | 1,468,364,884 | Directed Weighted Graph | 2017 | MATLAB Rutherford Boeing Matrix Market |

2856 | GAP-urand | GAP | 134,217,728 | 134,217,728 | 4,294,966,740 | Random Undirected Weighted Graph | 2017 | MATLAB Rutherford Boeing Matrix Market |

2853 | GAP-web | GAP | 50,636,151 | 50,636,151 | 1,930,292,948 | Directed Weighted Graph | 2017 | MATLAB Rutherford Boeing Matrix Market |