# DIMACS10

Kind: Random Undirected Graph, Random Unweighted Graph, Undirected Graph, Undirected Multigraph, Undirected Random Graph, Undirected Weighted Graph
Max Nonzeros: 265114400
Number of Graphs: 151
Number of Nodes (Median): 196621
Number of Nodes (Range): 39 - 50912018

```

http://www.cc.gatech.edu/dimacs10/index.shtml
http://www.cise.ufl.edu/research/sparse/dimacs10

Problems Addressed

    * Graph partitioning
    * Graph clustering

There are 12 data sets in the DIMACS10 collection:

clustering: real-world graphs commonly used as benchmarks
coauthor:   citation and co-author networks
Delaunay:   Delaunay triangulations of random points in the plane
dyn-frames: frames from a 2D dynamic simulation
Kronecker:  synthetic graphs from the Graph500 benchmark
numerical:  graphs from numerical simulation
random:     random geometric graphs (random points in the unit square)
streets:    real-world street networks
Walshaw:    Chris Walshaw's graph partitioning archive
matrix:     graphs from the UF collection (not added here)
redistrict: census networks
star-mixtures : artificially generated from sets of real graphs

Some of the graphs already exist in the UF Collection.  In some cases,
the original graph is unsymmetric, with values, whereas the DIMACS
graph is the symmetrized pattern of A+A'.  Rather than add duplicate
patterns to the UF Collection, a MATLAB script is provided at
http://www.cise.ufl.edu/research/sparse/dimacs10 which downloads
each matrix from the UF Collection via UFget, and then performs whatever
operation is required to convert the matrix to the DIMACS graph problem.
Also posted at that page is a MATLAB code (metis_graph) for reading the
DIMACS *.graph files into MATLAB.

--------------------------------------------------------------------------------
clustering:  Clustering Benchmarks
--------------------------------------------------------------------------------

    These real-world graphs are often used as benchmarks in the graph
    clustering and community detection communities.  All but 4 of the 27
    graphs already appear in the UF collection in other groups.  The
    DIMACS10 version is always symmetric, binary, and with zero-free
    diagonal.  The version in the UF collection may not have those
    properties, but in those cases, if the pattern of the UF matrix
    is symmetrized and the diagonal removed, the result is the DIMACS10
    graph.

    DIMACS10 graph:                 new?   UF matrix:
    ---------------                 ----   -------------
    clustering/adjnoun                     Newman/adjoun
    clustering/as-22july06                 Newman/as-22july06
    clustering/astro-ph                    Newman/astro-ph
    clustering/caidaRouterLevel      *     DIMACS10/caidaRouterLevel
    clustering/celegans_metabolic          Arenas/celegans_metabolic
    clustering/celegansneural              Newman/celegansneural
    clustering/chesapeake            *     DIMACS10/chesapeake
    clustering/cnr-2000                    LAW/cnr-2000
    clustering/cond-mat-2003               Newman/cond-mat-2003
    clustering/cond-mat-2005               Newman/cond-mat-2005
    clustering/cond-mat                    Newman/cond-mat
    clustering/dolphins                    Newman/dolphins
    clustering/email                       Arenas/email
    clustering/eu-2005                     LAW/eu-2005
    clustering/football                    Newman/football
    clustering/hep-th                      Newman/hep-th
    clustering/in-2004                     LAW/in-2004
    clustering/jazz                        Arenas/jazz
    clustering/karate                      Arenas/karate
    clustering/lesmis                      Newman/lesmis
    clustering/netscience                  Newman/netscience
    clustering/PGPgiantcompo               Arenas/PGPgiantcompo
    clustering/polblogs                    Newman/polblogs
    clustering/polbooks                    Newman/polbooks
    clustering/power                       Newman/power
    clustering/road_central          *     DIMACS10/road_central
    clustering/road_usa              *     DIMACS10/road_usa

    the following graphs were added on July 2012:

    G_n_pin_pout
    preferentialAttachment
    smallworld

    uk-2002 was 'added' on July 2012 to the dimacs10 MATLAB interface,
    but it already appears as the LAW/uk-2002 matrix.

    uk-2007-05 is in the DIMACS10 collection but is not yet added here,
    because it's too large for the file format of the UF collection.

--------------------------------------------------------------------------------
coauthor:  Citation Networks
--------------------------------------------------------------------------------

    These graphs are examples of social networks used in R. Geisberger, P.
    Sanders, and D. Schultes. Better approximation of betweenness
    centrality. In 10th Workshop on Algorithm Engineering and
    Experimentation, pages 90-108, San Francisco, 2008. SIAM.

--------------------------------------------------------------------------------
Delaunay:  Delaunay Graphs
--------------------------------------------------------------------------------

    These files have been generated as Delaunay triangulations of random
    points in the unit square.

    Engineering a scalable high quality graph partitioner,
    M. Holtgrewe, P. Sanders, C. Schulz, IPDPS 2010
    http://dx.doi.org/10.1109/IPDPS.2010.5470485

--------------------------------------------------------------------------------
dyn-frames:  Frames from 2D Dynamic Simulations
--------------------------------------------------------------------------------

    These files have been created with the generator described in Oliver
    Marquardt, Stefan Schamberger: Open Benchmarks for Load Balancing
    Heuristics in Parallel Adaptive Finite Element Computations. In Proc.
    International Conference on Parallel and Distributed Processing
    Techniques and Applications (PDPTA 2005), Volume 2, pp. 685-691. CSREA
    Press 2005, ISBN 1-932415-59-9685-691.

    The graphs are meshes taken from indivudual frames of a dynamic
    sequence that resembles two-dimensional adaptive numerical simulations.
    Smaller versions of these files (and their dynamic sequences as videos)
    can be found on Stefan Schamberger's website (
    http://www.upb.de/cs/schaum/benchmark.html ) dedicated to these
    benchmarks. The files presented here are the frames 0, 10, and 20 of
    the sequences, respectively.

--------------------------------------------------------------------------------
Kronecker:  Kronecker Generator Graphs
--------------------------------------------------------------------------------

    The original Kronecker files contain self-loops and multiple edges.
    These properties are also present in real-world data sets. However,
    some tools cannot handle these "artifacts" at the moment. That is why
    we present "cleansed" versions of the data sets as well.  For the
    Challenge you should expect to be confronted with the original data
    with self-loops and multiple edges. However, the final decision on
    this issue will be made based on participant feedback.

    All files have been generated with the R-MAT parameters A=0.57, B=0.19,
    C=0.19, and D=1-(A+B+C)=0.05 and edgefactor=48, i.e., the number of
    edges equals 48*n, where n is the number of vertices. Details about the
    generator and the parameter meanings can be found on the Graph500
    website.  ( http://www.graph500.org/Specifications.html )

    There are 12 graphs in the DIMACS10 test set at
    http://www.cc.gatech.edu/dimacs10/index.shtml .  Them come in 6 pairs.
    One graph in each pair is a multigraph, with self-edges.  The other
    graph is the nonzero pattern of the first (binary), with self-edges
    removed.  MATLAB cannot directly represent multigraph, so in the UF
    Collection the unweighted multigraph G is represented as a matrix A
    where A(i,j) is an integer equal to the number edges (i,j) in G.

    The binary graphs include the word 'simple' in their
    name In the UF Collection, only the multigraph is included,
    since the simple graph can be constructed from the multigraph.
    If A is the multigraph, the simple graph S can be computed as:

       S = spones (tril (A,-1)) + spones (triu (A,1)) ;

    DIMACS10 graph:                        UF matrix:
    ---------------                        -------------
    kronecker/kron_g500-logn16             DIMACS10/kron_g500-logn16
    kronecker/kron_g500-simple-logn16

    kronecker/kron_g500-logn17             DIMACS10/kron_g500-logn17
    kronecker/kron_g500-simple-logn17

    kronecker/kron_g500-logn18             DIMACS10/kron_g500-logn18
    kronecker/kron_g500-simple-logn18

    kronecker/kron_g500-logn19             DIMACS10/kron_g500-logn19
    kronecker/kron_g500-simple-logn19

    kronecker/kron_g500-logn20             DIMACS10/kron_g500-logn20
    kronecker/kron_g500-simple-logn20

    kronecker/kron_g500-logn21             DIMACS10/kron_g500-logn21
    kronecker/kron_g500-simple-logn21

    References: "Introducing the Graph 500," Richard C. Murphy, Kyle B.
    Wheeler, Brian W. Barrett, James A. Ang, Cray User's Group (CUG), May
    5, 2010.

    D.A. Bader, J. Feo, J. Gilbert, J. Kepner, D. Koester, E. Loh, K.
    Madduri, W. Mann, Theresa Meuse, HPCS Scalable Synthetic Compact
    Applications #2 Graph Analysis (SSCA#2 v2.2 Specification), 5
    September 2007.

    D. Chakrabarti, Y. Zhan, and C. Faloutsos, R-MAT: A recursive model
    for graph mining, SIAM Data Mining 2004.

    Section 17.6, Algorithms in C (third edition). Part 5 Graph
    Algorithms, Robert Sedgewick (Programs 17.7 and 17.8)

    P. Sanders, Random Permutations on Distributed, External and
    Hierarchical Memory, Information Processing Letters 67 (1988) pp
    305-309.

    "DFS: A Simple to Write Yet Difficult to Execute Benchmark," Richard C.
    Murphy, Jonathan Berry, William McLendon, Bruce Hendrickson, Douglas
    Gregor, Andrew Lumsdaine, IEEE International Symposium on Workload
    Characterizations 2006 (IISWC06), San Jose, CA, 25-27 October 2006.

   

--------------------------------------------------------------------------------
numerical: graphs from numerical simulations
--------------------------------------------------------------------------------

    For the graphs adaptive and venturiLevel3, please refer to the preprint:

    Hartwig Anzt, Werner Augustin, Martin Baumann, Hendryk Bockelmann,
    Thomas Gengenbach, Tobias Hahn, Vincent Heuveline, Eva Ketelaer,
    Dimitar Lukarski, Andrea Otzen, Sebastian Ritterbusch, Bjo"rn Rocker,
    Staffan Ronnås, Michael Schick, Chandramowli Subramanian, Jan-Philipp
    Weiss, and Florian Wilhelm.  Hiflow3 - a flexible and hardware-aware
    parallel Finite element package. In Parallel/High-Performance Object-
    Oriented Scientific Computing (POOSC'10).

    For the graphs channel-500x100x100-b050 and packing-500x100x100-b050,
    please refer to:

    Markus Wittmann, Thomas Zeiser. Technical Note: Data Structures of
    ILBDC Lattice Boltzmann Solver.
    http://www.cc.gatech.edu/dimacs10/archive/numerical-overview-Erlangen.pdf

    The instances NACA0015, M6, 333SP, AS365, and NLR are 2-dimensional FE
    triangular meshes with coordinate information. 333SP and AS365 are actually
    converted from existing 3-dimensional models to 2D places, while the rest
    are created from geometry. The corresponding coordinate files have been
    assembled in one archive. They have been created and contributed by Chan
    Siew Yin with the help of Jian Tao Zhang, Department of Mechanical
    Engineering, University of New Brunswick, Fredericton, Canada. 

--------------------------------------------------------------------------------
random:  Random Geometric Graphs
--------------------------------------------------------------------------------

    rggX is a random geometric graph with 2^X vertices. Each vertex is a
    random point in the unit square and edges connect vertices whose
    Euclidean distance is below 0.55 (ln n)/n. This threshold was choosen
    in order to ensure that the graph is almost connected.

    Note:  the UF Collection is a collection of matrices primarily from
    real applications.  The only random matrices I add to the collection
    are those used in established benchmarks (such as DIMACS10).

    Engineering a scalable high quality graph partitioner,
    M. Holtgrewe, P. Sanders, C. Schulz, IPDPS 2010.
    http://dx.doi.org/10.1109/IPDPS.2010.5470485

--------------------------------------------------------------------------------
steets:  Street Networks
--------------------------------------------------------------------------------

    The graphs Asia, Belgium, Europe, Germany, Great-Britain, Italy,
    Luxemburg and Netherlands are (roughly speaking) undirected and
    unweighted versions of the largest strongly connected component
    of the corresponding Open Street Map road networks. The Open
    Street Map road networks have been taken from
    http://download.geofabrik.de and have been converted for DIMACS10
    by Moritz Kobitzsch (kobitzsch at kit.edu) as follows:

    First, we took the corresponding graph and extracted all routeable
    streets. Routable streets are objects in this file that are tagged
    using one of the following tags: motorway, motorway_link, trunk
    trunk_link, primary, primary_link, secondary, secondary_link,
    tertiary, tertiary_link, residential, unclassified, road,
    living_street, and service.  Next, we now compute the largest
    strongly connected component of this extracted open street map graph.
    Self-edges and parallel edges are removed afterwards.
    The DIMACS 10 graph is now the undirected and unweighted version
    of the constructed graph, i.e.  if there is an edge (u,v) but the
    reverse edge (v,u) is missing, we insert the reverse edge into the
    graph.  The XY coordinates of each node in the graph are preserved.

--------------------------------------------------------------------------------
Walshaw:  Chris Walshaw's graph partitioning archive
--------------------------------------------------------------------------------

    Chris Walshaw's graph partitioning archive contains 34 graphs that
    have been very popular as benchmarks for graph partitioning algorithms
    ( http://staffweb.cms.gre.ac.uk/~wc06/partition/ ).

    17 of them are already in the UF Collection.  Only the 17 new graphs
    not yet in the collection are added here in the DIMACS10 set.

    DIMACS10 graph:                 new?   UF matrix:
    ---------------                 ----   -------------
    walshaw/144                      *     DIMACS10/144
    walshaw/3elt                           AG-Monien/3elt
    walshaw/4elt                           Pothen/barth5
    walshaw/598a                     *     DIMACS10/598a
    walshaw/add20                          Hamm/add20
    walshaw/add32                          Hamm/add32
    walshaw/auto                     *     DIMACS10/auto
    walshaw/bcsstk29                       HB/bcsstk29
    walshaw/bcsstk30                       HB/bcsstk30
    walshaw/bcsstk31                       HB/bcsstk31
    walshaw/bcsstk32                       HB/bcsstk32
    walshaw/bcsstk33                       HB/bcsstk33
    walshaw/brack2                         AG-Monien/brack2
    walshaw/crack                          AG-Monient/crack
    walshaw/cs4                      *     DIMACS10/cs4
    walshaw/cti                      *     DIMACS10/cti
    walshaw/data                     *     DIMACS10/data
    walshaw/fe_4elt2                 *     DIMACS10/fe_4elt2
    walshaw/fe_body                  *     DIMACS10/fe_body
    walshaw/fe_ocean                 *     DIMACS10/fe_ocean
    walshaw/fe_pwt                         Pothen/pwt
    walshaw/fe_rotor                 *     DIMACS10/fe_rotor
    walshaw/fe_sphere                *     DIMACS10/fe_sphere
    walshaw/fe_tooth                 *     DIMACS10/fe_tooth
    walshaw/finan512                       Mulvey/finan512
    walshaw/m14b                     *     DIMACS10/m14b
    walshaw/memplus                        Hamm/memplus
    walshaw/t60k                     *     DIMACS10/t60k
    walshaw/uk                       *     DIMACS10/uk
    walshaw/vibrobox                       Cote/vibrobox
    walshaw/wave                           AG-Monien/wave
    walshaw/whitaker3                      AG-Monien/whitaker3
    walshaw/wing                     *     DIMACS10/wing
    walshaw/wing_nodal               *     DIMACS10/wing_nodal

--------------------------------------------------------------------------------
redistrict:  census networks
--------------------------------------------------------------------------------

    These graphs represent US states. They are used for solving the
    redistricting problem. All data have been provided by Will Zhao. As stated
    on the project website,  The nodes are Census2010 blocks. Two nodes have an
    edge linking them if they share a line segment on their borders, i.e.
    rook-style neighboring. The nodes weights are the POP100 variable of
    Census2010-PL94, and the area of eache district.

--------------------------------------------------------------------------------
star-mixtures : artificially generated from sets of real graphs
--------------------------------------------------------------------------------

    Each graph in this benchmark represents a star-like structure of different
    graphs S0 , . . . , St. Graphs S1 , . . . , St are weakly connected to the
    center S0 by random edges. The total number of edges between each Si and S0
    was less than 3% out of the total number of edges in Si . The graphs are
    mixtures of the following structures: social networks, finite-element
    graphs, VLSI chips, peer-to-peer networks, and matrices from optimization
    solvers.

    More info can be found in the paper I. Safro, P. Sanders, C. Schulz:
    Advanced Coarsening Schemes for Graph Partitioning, SEA 2012.

    Communicated by Christian Schulz, uploaded on March 30, 2012.
```