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.