10th DIMACS Implementation Challenge Updated July 2012 http://www.cc.gatech.edu/dimacs10/index.shtml http://www.cise.ufl.edu/research/sparse/dimacs10 As stated on their main website ( http://dimacs.rutgers.edu/Challenges/ ), the "DIMACS Implementation Challenges address questions of determining realistic algorithm performance where worst case analysis is overly pessimistic and probabilistic models are too unrealistic: experimentation can provide guides to realistic algorithm performance where analysis fails." For the 10th DIMACS Implementation Challenge, the two related problems of graph partitioning and graph clustering were chosen. Graph partitioning and graph clustering are among the aforementioned questions or problem areas where theoretical and practical results deviate significantly from each other, so that experimental outcomes are of particular interest. Problem Motivation Graph partitioning and graph clustering are ubiquitous subtasks in many application areas. Generally speaking, both techniques aim at the identification of vertex subsets with many internal and few external edges. To name only a few, problems addressed by graph partitioning and graph clustering algorithms are: * What are the communities within an (online) social network? * How do I speed up a numerical simulation by mapping it efficiently onto a parallel computer? * How must components be organized on a computer chip such that they can communicate efficiently with each other? * What are the segments of a digital image? * Which functions are certain genes (most likely) responsible for? Challenge Goals * One goal of this Challenge is to create a reproducible picture of the state-of-the-art in the area of graph partitioning (GP) and graph clustering (GC) algorithms. To this end we are identifying a standard set of benchmark instances and generators. * Moreover, after initiating a discussion with the community, we would like to establish the most appropriate problem formulations and objective functions for a variety of applications. * Another goal is to enable current researchers to compare their codes with each other, in hopes of identifying the most effective algorithmic innovations that have been proposed. * The final goal is to publish proceedings containing results presented at the Challenge workshop, and a book containing the best of the proceedings papers. Problems Addressed The precise problem formulations need to be established in the course of the Challenge. The descriptions below serve as a starting point. * Graph partitioning: The most common formulation of the graph partitioning problem for an undirected graph G = (V,E) asks for a division of V into k pairwise disjoint subsets (partitions) such that all partitions are of approximately equal size and the edge-cut, i.e., the total number of edges having their incident nodes in different subdomains, is minimized. The problem is known to be NP-hard. * Graph clustering: Clustering is an important tool for investigating the structural properties of data. Generally speaking, clustering refers to the grouping of objects such that objects in the same cluster are more similar to each other than to objects of different clusters. The similarity measure depends on the underlying application. Clustering graphs usually refers to the identification of vertex subsets (clusters) that have significantly more internal edges (to vertices of the same cluster) than external ones (to vertices of another cluster). 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. ---- sample code for generating these matrices: function ij = kronecker_generator (SCALE, edgefactor) %% Generate an edgelist according to the Graph500 %% parameters. In this sample, the edge list is %% returned in an array with two rows, where StartVertex %% is first row and EndVertex is the second. The vertex %% labels start at zero. %% %% Example, creating a sparse matrix for viewing: %% ij = kronecker_generator (10, 16); %% G = sparse (ij(1,:)+1, ij(2,:)+1, ones (1, size (ij, 2))); %% spy (G); %% The spy plot should appear fairly dense. Any locality %% is removed by the final permutations. %% Set number of vertices. N = 2^SCALE; %% Set number of edges. M = edgefactor * N; %% Set initiator probabilities. [A, B, C] = deal (0.57, 0.19, 0.19); %% Create index arrays. ij = ones (2, M); %% Loop over each order of bit. ab = A + B; c_norm = C/(1 - (A + B)); a_norm = A/(A + B); for ib = 1:SCALE, %% Compare with probabilities and set bits of indices. ii_bit = rand (1, M) > ab; jj_bit = rand (1, M) > ( c_norm * ii_bit + a_norm * not (ii_bit) ); ij = ij + 2^(ib-1) * [ii_bit; jj_bit]; end %% Permute vertex labels p = randperm (N); ij = p(ij); %% Permute the edge list p = randperm (M); ij = ij(:, p); %% Adjust to zero-based labels. ij = ij - 1; function G = kernel_1 (ij) %% Compute a sparse adjacency matrix representation %% of the graph with edges from ij. %% Remove self-edges. ij(:, ij(1,:) == ij(2,:)) = []; %% Adjust away from zero labels. ij = ij + 1; %% Find the maximum label for sizing. N = max (max (ij)); %% Create the matrix, ensuring it is square. G = sparse (ij(1,:), ij(2,:), ones (1, size (ij, 2)), N, N); %% Symmetrize to model an undirected graph. G = spones (G + G.'); -------------------------------------------------------------------------------- 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.