I am looking for a source of huge data sets to test some graph algorithm implemention. Please also provide some information about the type/distribution (e.g. directed/undirected, simple/not simple, weighted/unweighted) of the graphs in the source if they are known.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ related post: cstheory.stackexchange.com/questions/16751/… $\endgroup$– Neal YoungCommented Mar 18, 2013 at 16:44
Add a comment
|
10 Answers
$\begingroup$
$\endgroup$
Check the following links for graph instances
DIMACS Graphs: Benchmark Instances and Best Upper Bounds foo
answered Aug 29, 2010 at 14:25
$\begingroup$
$\endgroup$
I'll try to give a more high-level answer than the other ones.
The following classes of inputs are often useful to test the performance of a proposed algorithm or the validity of a conjecture in graph theory:
Random graphs: For many graph properties, random graphs are extremal in expectation. For instance, the number of times a given complete bipartite graph occurs as a subgraph is minimized in a random graph. (It's a beautiful conjecture of Erdős-Simonovits and Sidorenko that if $H$ is a bipartite graph, then the random graph with edge density $p$ has in expectation asymptotically the minimum number of copies of $H$ over all graphs of the same order and edge density.) Distributions specified through random graphs are the source of many lower bounds for randomized graph algorithms, through Yao's minimax principle.
Structured graphs: This is a rough designation for a class of graphs that are somehow specially structured for the problem at hand. For example, Turán's theorem says that the densest graph on $n$ vertices which is triangle-free is the complete bipartite graph $K_{n/2,n/2}$; this graph is clearly specially built to avoid triangles.
"Non-random" graphs: These are intermediate between being completely generic, as in random graphs, and completely specific to the problem, as in structured graphs. For example, such a family could be random subgraphs of structured graphs. Such examples come up often in creating stronger variants of Szemerédi's regularity lemma. One way to produce these examples is to come up with a definition of "pseudorandomness" that models random inputs, so that for pseudorandom inputs, you can show that your algorithm or your conjecture works. Then, you identify obstructions to pseudorandomness, and graphs which have these obstructions can then produce a large collection of non-random graphs which are counterexamples. A more involved discussion of this principle can be found at Terry Tao's ICM talk in 2006. These non-random graphs roughly correspond to the "nilsequences" in some of his works with Ben Green and others.
$\begingroup$
$\endgroup$
For generating graphs, I usually use the geng program that comes with nauty:
http://cs.anu.edu.au/~bdm/nauty/
This produces undirected graphs (also known as "graphs"). To produce directed graphs you can pipe the output through directg which also comes with nauty.
Using geng is suitable for scenarios where you want to test all graphs on (say) up to n vertices, or all connected graphs with m edges or something like that. If you have more specific requirements, then please state these in your question.
$\begingroup$
$\endgroup$
The Stanford GraphBase may be of help for you: http://www-cs-staff.stanford.edu/~knuth/sgb.html
In all likelihood, however, you will probably want to generate the graphs yourself, and you will probably want the generated graphs to all have (or not have) certain properties. Random graphs are often a poor approximation of the graphs an algorithm actually gets used upon.
$\begingroup$
$\endgroup$
2
Not huge, but maybe still useful, 3054 "standard named graphs" from Mathematica's GraphData collection
The format is one graph per line, with name and list of adjacent nodes like this
{<graph name>, {{1, 4}, {1, 5}, {1, 6}, {2, 5}, {2, 6}, {3, 6}}
<graph name> can of the form "AGraph" or {"Andrasfai", 6}
answered Aug 30, 2010 at 0:19
-
$\begingroup$ Are these graphs or directed graphs? $\endgroup$– EmilCommented Aug 30, 2010 at 18:21
-
$\begingroup$ A cursory glance suggests that digraphs are supported. $\endgroup$ Commented Feb 15, 2023 at 12:17
$\begingroup$
$\endgroup$
Igraph package has different types of graph generator including both random graphs and structured graphs.
http://igraph.sourceforge.net/doc/html/igraph-Generators.html
$\begingroup$
$\endgroup$
1
There is an interesting and promising new community-based project for a graph database:
Introducing paper
The Open Graph Archive: A Community-Driven Effort
or the direct link
Time will show if it is a good place to go for test instances.
-
$\begingroup$ Perhaps the project (graph-archive.org fetches 404) has been discontinued. $\endgroup$ Commented Feb 15, 2023 at 12:15
$\begingroup$
$\endgroup$
The 9th DIMACS Implementation Challenge - Shortest Paths ran in 2005-2006 with the goal to produce "a standard set of benchmark instances and generators, as well as benchmark implementations of well-known shortest path algorithms."
The download page contains zipped USA road network graphs that range from 2MB to 335MB with both distance and time weights.
http://www.dis.uniroma1.it/challenge9/download.shtml
I found this useful to benchmark my own toy implementations of graph functions.
$\begingroup$
$\endgroup$
You can use Musketeer, see
https://people.cs.clemson.edu/~isafro/musketeer/index.html
This is a multiscale graph generator that accepts some input graph and generates another graph that can be arbitrarily similar to the original. The parameters are flexible enough to generate a new structure at different coarse-grained resolutions. See examples in the gallery. This package is perfect for creating experimental instances for verification and benchmarking algorithms.
$\begingroup$
$\endgroup$
Links to real-world graphs with more than 1G edges: https://sites.google.com/view/limass/datasets
A collection of smaller real-world graphs: http://snap.stanford.edu/data/index.html
