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:
2nd Mai 2018: Released VieClus v1.00.
20th February 2018: Published ArXiv Report. Link to PDF.


License

The program is licenced under GPL 2.0. Please let us know if you need a commercial 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:1702.04164},
             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