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 matrices
Id Name Group Rows Cols Nonzeros Kind Date Download File
2852 GAP-twitter GAP 61,578,415 61,578,415 1,468,364,884 Directed 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
2854 GAP-road GAP 23,947,347 23,947,347 57,708,624 Directed Weighted Graph 2017 MATLAB Rutherford Boeing Matrix Market
2855 GAP-kron GAP 134,217,726 134,217,726 4,223,264,644 Random Undirected 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