# Walshaw

Note: We do not provide the the data ourselves. Walshaw requests to be emailed for the distribution of the data, and so we link to their site and to the graphs found in the SuiteSparse Matrix Collection. 
Origin Notes: C. Walshaw, collected for an archive of graph partitions which has been maintained since 2000.  These are multilevel mesh partitions of heterogeneous networks from a variety of domains. 
graph features handled: Mesh, Partition, Weighted edges, Weighted nodes
Graph features in papers: clusters (generated),generic,generic,generic,large,generic,high degree,large,dynamic,multilevel,large
Origin Paper:  A Combined Evolutionary Search and Multilevel Optimisation Approach to Graph Partitioning (https://www.notion.so/A-Combined-Evolutionary-Search-and-Multilevel-Optimisation-Approach-to-Graph-Partitioning-d58eded005d14e428a11b9ca02c64eb1?pvs=21),  Mesh Partitioning: a Multilevel Balancing and Refinement Algorithm (https://www.notion.so/Mesh-Partitioning-a-Multilevel-Balancing-and-Refinement-Algorithm-97fff4a9a42b469cbd16a74d0a4aa48f?pvs=21)
Originally found at: https://chriswalshaw.co.uk/partition/ where C. Walshaw requests to be emailed for the dataset at mailto:c.walshaw@gre.ac.uk. the individual graphs can also be found on the SuiteSparse Matrix Collection under different groups. 

Size: 34 graphs, 2395-448695 nodes, 6837-3314611 edges. Node-weighted, edge-weighted. Partitions of the 34 graphs are given with various partition sizes and imbalance percentages.
Child collections: SuiteSparse Matrix Collection (SuiteSparse%20Matrix%20Collection%20b8772d6a2cbb456894b4673e32c6f956.md), Scotch Graph Collection (Scotch%20Graph%20Collection%20cfe6f105da3a4c699fa3e02ca1f6e88a.md)
Appeared in years: 2002,2007,2005,2006,2004,2017,2008,2019,2020
Type of Collection: Subset of other collection
is it stored properly?: No
must be analyzed: Yes
In repo?: No
Related to Literature - Algorithm (1) (Dataset tag relations): Efficient and High Quality Force-Directed Graph Drawing (https://www.notion.so/Efficient-and-High-Quality-Force-Directed-Graph-Drawing-0690316942ef4c97bec1a11b26255410?pvs=21), Drawing graphs by eigenvectors: theory and practice (https://www.notion.so/Drawing-graphs-by-eigenvectors-theory-and-practice-1b5e3919d8c94ad18f29f20c7480b07a?pvs=21), Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm (https://www.notion.so/Drawing-Large-Graphs-with-a-Potential-Field-Based-Multilevel-Algorithm-27a6b266bb2c4c92976ed04d2afe9bed?pvs=21), ACE: A Fast Multiscale Eigenvectors Computation for Drawing Huge Graphs (https://www.notion.so/ACE-A-Fast-Multiscale-Eigenvectors-Computation-for-Drawing-Huge-Graphs-44f8183954f14ada944d642d9ff1298e?pvs=21), Drawing Big Graphs Using Spectral
Sparsification (https://www.notion.so/Drawing-Big-Graphs-Using-Spectral-Sparsification-89da2043d0444f75a6c663b1fc999512?pvs=21), Multi-Level Graph Layout on the GPU (https://www.notion.so/Multi-Level-Graph-Layout-on-the-GPU-916f610d6b534e48a2478e5910bf085e?pvs=21), Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm (https://www.notion.so/Drawing-Large-Graphs-with-a-Potential-Field-Based-Multilevel-Algorithm-a4fe70c68ad64ed3849c47d95afc8798?pvs=21), SDE: Graph Drawing Using Spectral Distance Embedding (https://www.notion.so/SDE-Graph-Drawing-Using-Spectral-Distance-Embedding-a840905de8674a85a99706d2c17505aa?pvs=21), Multi-level Graph Drawing Using Infomap Clustering (https://www.notion.so/Multi-level-Graph-Drawing-Using-Infomap-Clustering-ad97d205cc804c748ab87d3012b18ebc?pvs=21), Online Dynamic Graph Drawing (https://www.notion.so/Online-Dynamic-Graph-Drawing-ae22e4cc10ec451bb95c2ba6cfc35499?pvs=21), Eigensolver methods for progressive multidimensional scaling of large data (https://www.notion.so/Eigensolver-methods-for-progressive-multidimensional-scaling-of-large-data-b5ab815edb48469192605e5ad31329c0?pvs=21), An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs (https://www.notion.so/An-Experimental-Comparison-of-Fast-Algorithms-for-Drawing-General-Large-Graphs-bbb7bb7d51d84d109030dee3c06d895d?pvs=21), A Multilevel Algorithm for Force-Directed Graph Drawing (https://www.notion.so/A-Multilevel-Algorithm-for-Force-Directed-Graph-Drawing-d1ebfc7319b04b66833d7e71c060d400?pvs=21), Large-Graph Layout with the Fast Multipole Multilevel Method (https://www.notion.so/Large-Graph-Layout-with-the-Fast-Multipole-Multilevel-Method-def1fdc467f441abb94868eccd8a5a34?pvs=21), Topological fisheye views for visualizing large graphs (https://www.notion.so/Topological-fisheye-views-for-visualizing-large-graphs-e2f5c279f5514a6da3a0241c978f564d?pvs=21)
cleaned format?: No
duplicate?: No
link works?: No
Added in paper: No
Origin paper plaintext:  A Combined Evolutionary Search and Multilevel Optimisation Approach to Graph Partitioning,  Mesh Partitioning: a Multilevel Balancing and Refinement Algorithm
Page id: e40b37a1147942d89ff1d8dfad285256
unavailable/skip: Yes
Cleaned ALL data: No
first look: No
Related to Literature - Algorithm (Dataset tag relations) 1: A Multilevel Algorithm for Force-Directed Graph Drawing (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/A%20Multilevel%20Algorithm%20for%20Force-Directed%20Graph%20Dr%20234ec1ad86724e0baed5830877d0c70d.md), Multi-Level Graph Layout on the GPU (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Multi-Level%20Graph%20Layout%20on%20the%20GPU%20f855194c9d8a40b8821fafe30add0699.md), ACE: A Fast Multiscale Eigenvectors Computation for Drawing Huge Graphs (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/ACE%20A%20Fast%20Multiscale%20Eigenvectors%20Computation%20for%205e8de72ea8d0436babf760ca379cc457.md), Drawing graphs by eigenvectors: theory and practice (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Drawing%20graphs%20by%20eigenvectors%20theory%20and%20practice%2039ccd4aeec6448f8a58d51b986c9d097.md), SDE: Graph Drawing Using Spectral Distance Embedding (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/SDE%20Graph%20Drawing%20Using%20Spectral%20Distance%20Embeddin%208ce58ef9bc5d4e1aa66f2935bf122f92.md), Efficient and High Quality Force-Directed Graph Drawing (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Efficient%20and%20High%20Quality%20Force-Directed%20Graph%20Dr%201e92a86c6b4f4577b1c2c30903173220.md), Large-Graph Layout with the Fast Multipole Multilevel Method (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Large-Graph%20Layout%20with%20the%20Fast%20Multipole%20Multile%20b88c56b7799741ccbbb9d4f05ea8df4b.md), Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Drawing%20Large%20Graphs%20with%20a%20Potential-Field-Based%20%203c0831d7e44545b0894bb5b8a4aa8f54.md), Drawing Big Graphs Using Spectral
Sparsification (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Drawing%20Big%20Graphs%20Using%20Spectral%20Sparsification%20e5d3efdca48541f2b1789ec74357ebf6.md), An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/An%20Experimental%20Comparison%20of%20Fast%20Algorithms%20for%20%20190e5036cf974a879b50614cfff525f1.md), Eigensolver methods for progressive multidimensional scaling of large data (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Eigensolver%20methods%20for%20progressive%20multidimension%20b4b33cff0cf94e8db1fd3dcdab73f9e4.md), Topological fisheye views for visualizing large graphs (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Topological%20fisheye%20views%20for%20visualizing%20large%20gr%2094f9c1efaeed4304bd4c6686d2962159.md), Online Dynamic Graph Drawing (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Online%20Dynamic%20Graph%20Drawing%203c5e54c02d0b473294442f7387ddb03d.md), Multi-level Graph Drawing Using Infomap Clustering (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Multi-level%20Graph%20Drawing%20Using%20Infomap%20Clustering%20eadf3605c6ed46ff93629fb92858fbd4.md), A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/A%20Random%20Sampling%20O(n)%20Force-calculation%20Algorithm%2086599a831f314d1cb8871a5a92420d0f.md), Sublinear Time Force Computation for Big Complex Network Visualization (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Sublinear%20Time%20Force%20Computation%20for%20Big%20Complex%20N%20999af7d2d1c942628bada6371a87100f.md)

# Body

### Descriptions from Literature

From “[An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs](https://link.springer.com/chapter/10.1007/11618058_22)”:

> The rest of the test graphs are taken from real-world applications. In particular, we selected graphs from the AT&T graph library [1], from C. Walshaw’s graph collection [20], and a graph that describes a social network of 2113 people that we obtained from C. Lipp.
> 

From “[A Combined Evolutionary Search and Multilevel Optimisation Approach to Graph-Partitioning](https://doi.org/10.1023/B:JOGO.0000042115.44455.f3)”:

> The test graphs have been chosen to be a representative sample of small to medium scale real-life problems (mostly mesh-based) and include both 2D and 3D examples of nodal graphs (where the mesh nodes are partitioned) and dual graphs (where the mesh elements are partitioned). In addition there is a 3D semi-structured graph, cti, which is unstructured in the x−y plane but extended regularly along the z-axis. Finally the test suite includes three non mesh-based graphs (add32, vibrobox, bcsstk32) which arise from various scientific computing applications2. None of the graphs have either vertex or edge weights; such graphs are not widely available since most applications do not accurately instrument costs and it is difficult to draw meaningful conclusions from the few examples that we have access to.
> 

![Untitled](Walshaw%20e40b37a1147942d89ff1d8dfad285256/Untitled.png)

### Example Figures

From “[An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs](https://link.springer.com/chapter/10.1007/11618058_22)”:

![Untitled](Walshaw%20e40b37a1147942d89ff1d8dfad285256/Untitled%201.png)

From “[Multi-Level Graph Layout on the GPU](https://doi.org/10.1109/TVCG.2007.70580)”:

![Untitled](Walshaw%20e40b37a1147942d89ff1d8dfad285256/Untitled%202.png)

**Fig. 11.** 4elt. Red: our layout, black: Kamada-Kawai layout

### Other

From [*Group DIMACS10 in the SuiteSparse Matrix Collection*](https://sparse.tamu.edu/DIMACS10):

```
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
```

=== STOP RENDERING ===

Made explicit that they want people to reach out to them for the dataset so we do not collect it. Also in Suite Sparse, and many of the graphs are included in the Scotch graph collection.

From: [An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs](https://link.springer.com/chapter/10.1007/11618058_22)

![Untitled](Walshaw%20e40b37a1147942d89ff1d8dfad285256/Untitled%203.png)

Graphs found on the Sparse Matrix Collection