17
$\begingroup$

I am studying graph algorithms.

I need a database of graphs on which I can test my algorithms.

Where can I find a reliable database of graphs of all kinds?

Thanks!

$\endgroup$
  • 7
    $\begingroup$ You might want to be more specific. Do you want all graphs on $n$ vertices or less? Do you want pathological examples? How do you want your graphs presented to you? Graphically? An edge list? As an input to a specific piece of software. SAGE has large classes of graphs built-in. $\endgroup$ – Cam McLeman May 6 '10 at 17:42
  • $\begingroup$ One option is to generate random graphs -- the usefulness of this would depend on the specific application in mind. $\endgroup$ – Douglas S. Stones May 7 '10 at 1:41
14
$\begingroup$

You might want to look at Donald Knuth's Stanford GraphBase: A Platform for Combinatorial Computing (1994, 2009) and the accompanying website.

See also The Stony Brook Algorithm Repository.

| cite | improve this answer | |
$\endgroup$
8
$\begingroup$

There's a nice collection of data on regular graphs at Markus Meringer's webpage.

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

Sage (http://www.sagemath.org/) provides access to a large collection of graphs, as well as tools for working with them.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

nauty comes with some additional programs. In particular, you might be interested in geng. As the website says "geng can generate non-isomorphic graphs very quickly. There are also generators for bipartite graphs, digraphs, and multigraphs."

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

Discrete ZOO should also be mentioned here. As of 2 March 2018, it reports to host 212238 graphs.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Maple 13 or newer has a GraphTheory package that has a graph generator which allows you to generate all non-isomorphic graphs satisfying various criteria. You can use that to produce graphs and export them in various formats. In addition, you can produce random graphs using this package.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Here's a collection of 3054 "standard named graphs" from Mathematica's GraphData collection http://yaroslavvb.com/upload/graphs2.txt

It's one graph per line, description followed by pairs of adjacent vertices

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Two such websites I am aware of are:

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Some hint useful in year 2020: google: "graph dataset", but NOT "graph database" (which means somewhat different thing).

Google will give a lot. Let me also give some direct links with some comments:

  1. http://networkrepository.com/ That dataset collection seems to be the most advanced - big, well ogranized, with online analysis tools
  2. https://snap.stanford.edu/data/index.html#socnets "SNAP" - Stanford Network Analysis Platform Maintained by group of well-known expert in applied graph analysis: Jure Leskovec
  3. https://graphchallenge.mit.edu/data-sets many links to datasets, in particular: Protein k-mer graphs generated using data from GenBank: https://www.ncbi.nlm.nih.gov/genbank/ are available below. Nodes of the graph represent segments of amino acids.
  4. https://www.quora.com/Where-can-I-find-large-graph-test-datasets Quora answers contains a lot of links
  5. https://biit.cs.ut.ee/graphweb/welcome.cgi?t=examples Here are around dozen datasets for protein interaction in different organizms: human, mouse, yeast ... See some info on protein-protein interactions can be found here: https://www.ebi.ac.uk/training/online/course/network-analysis-protein-interaction-data-introduction/protein-protein-interaction-networks
  6. https://kateto.net/2016/05/network-datasets/ Katya Ognyanova site - here are links to collections of datasets
  7. https://www.kaggle.com/devisangeetha/network-visualizations-with-igraph Kaggle-dataset: Stack Overflow Tag Network Network (links and nodes) of Stack Overflow tags based on Developer Stories

Let me also mention that modern software tools have ready to use graph examples or can easily generate them. For example

  1. "Pytorch" from Facebook: https://pytorch-geometric.readthedocs.io/en/latest/modules/datasets.html A variety of graph kernel benchmark datasets, .e.g. “IMDB-BINARY”, “REDDIT-BINARY” or “PROTEINS”, collected from the TU Dortmund University. In addition, this dataset wrapper provides cleaned dataset versions as motivated by the “Understanding Isomorphism Bias in Graph Data Sets” paper, containing only non-isomorphic graphs. The citation network datasets “Cora”, “CiteSeer” and “PubMed” from the “Revisiting Semi-Supervised Learning with Graph Embeddings” paper. Nodes represent documents and edges represent citation links. Training, validation and test splits are given by binary masks.
  2. networkX - most comprehensive Python library for graphs, support generation of may be hundred family of examples. See the list here: https://networkx.github.io/documentation/stable/reference/generators.html And let me quote may be most interesting ones:
Expanders
Provides explicit constructions of expander graphs.
margulis_gabber_galil_graph(n[, create_using])
Returns the Margulis-Gabber-Galil undirected MultiGraph on n^2 nodes.
chordal_cycle_graph(p[, create_using])
Returns the chordal cycle graph on p nodes.

Random Graphs:
erdos_renyi_graph(n, p[, seed, directed])
Returns a Gn,p random graph, also known as an Erdős-Rényi graph or a binomial graph.
binomial_graph(n, p[, seed, directed])
Returns a Gn,p random graph, also known as an Erdős-Rényi graph or a binomial graph.
newman_watts_strogatz_graph(n, k, p[, seed])
Returns a Newman–Watts–Strogatz small-world graph.
watts_strogatz_graph(n, k, p[, seed])
Returns a Watts–Strogatz small-world graph.
connected_watts_strogatz_graph(n, k, p[, …])
Returns a connected Watts–Strogatz small-world graph.
random_regular_graph(d, n[, seed])
Returns a random d-regular graph on n nodes.
barabasi_albert_graph(n, m[, seed])
Returns a random graph according to the Barabási–Albert preferential attachment model.
dual_barabasi_albert_graph(n, m1, m2, p[, seed])
Returns a random graph according to the dual Barabási–Albert preferential attachment model.

So one might generate/explore/plot graphs with few lines of code, for example: enter image description here

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.