Overview

Graph clustering is the problem of detecting tightly connected regions of a graph. Depending on the task, knowledge about the structure of the graph can reveal information such as voter behavior, the formation of new trends, existing terrorist groups and recruitment or a natural partitioning of data records onto pages. Further application areas include the study of protein interaction, gene expression networks, fraud detection, program optimization and the spread of epidemics---possible applications are plentiful, as almost all systems containing interacting or coexisting entities can be modeled as a graph.

VieClus - Vienna Graph Clustering -- is a memetic algorithm. It includes serveral heuristics to compute a clustering of a graph. We provide it here as easy to use open source software. A key component of our contribution are natural recombine operators that employ ensemble clusterings as well as multi-level techniques. Our recombination operators use the overlay of two clusterings from the population to decide whether pairs of vertices should belong to the same cluster. This is combined with a local search algorithm to find further improvements and also embedded into a multi-level algorithm to find even better clusterings. Lastly, we combine these techniques with a scalable communication protocol, producing a system that is able to compute high-quality solutions in a short amount of time. In our experimental evaluation, we show that our algorithm successfully improves or reproduces all entries of the 10th DIMACS implementation~challenge under consideration in a small amount of time. In fact, for most of the small instances, we can improve the old benchmark result in less than a minute.

News:
8th January 2024: Switched this website to github.
21nd Mai 2020: Switched to CMake as a build system and switched license to MIT.
2nd Mai 2018: Released VieClus v1.00.
20th February 2018: Published ArXiv Report. Link to PDF.


License

The program is licenced under MIT licence.
If you publish results using our algorithms, please acknowledge our work by quoting the following paper (PDF):

@inproceedings{BiedermannHSS18,
             AUTHOR = {Biedermann, Sonja and Henzinger, Monika and Schulz, Christian and Schuster, Bernhard},
             TITLE = {{Memetic Graph Clustering}},
             BOOKTITLE = {{Proceedings of the 17th International Symposium on Experimental Algorithms (SEA'18)}},
             SERIES = {{LIPIcs}},
             PUBLISHER = {Dagstuhl},
             NOTE = {Technical Report, arXiv:1802.07034},
             YEAR = {2018}
}


The algorithms that are included for download are mainly based on the following publications:

  • Sonja Biedermann, Monika Henzinger, Christian Schulz and Bernhard Schuster. Memetic Graph Clustering. Proceedings of the 17th International Symposium on Experimental Algorithms (SEA'18). 2018. Download PDF.

Download

Support

  • Write us an email if you need support!
  • We are glad for any comments and error reports (or even bug fixes or feature requests) that you send us.

Other Open Source Projects

  • KaHIP -- Karlsruhe High Quality Partitioning
  • ParHIP -- Parallel High Quality Partitioning
  • KaMIS -- Karlsruhe Maximum Independent Sets
  • KaLP -- Karlsruhe Longest Paths
  • KaDraw -- Karlsruhe Graph Drawing
  • VieM -- Vienna Mapping and Sparse Quadratic Assignment