36
$\begingroup$

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.

$\endgroup$
21
$\begingroup$

Check the following links for graph instances

DIMACS Graphs: Benchmark Instances and Best Upper Bounds foo

Graph Coloring Instances

CLIQUE Benchmark Instances

$\endgroup$
17
$\begingroup$

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:

  1. 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.

  2. 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.

  3. "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.

$\endgroup$
14
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ Are these graphs or directed graphs? $\endgroup$ – Emil Aug 30 '10 at 18:21
4
$\begingroup$

Igraph package has different types of graph generator including both random graphs and structured graphs.

http://igraph.sourceforge.net/doc/html/igraph-Generators.html

$\endgroup$
4
$\begingroup$

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

Graph-Archive.org

Time will show if it is a good place to go for test instances.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy