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:
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
- Code available on GitHub here
- User Guide to VieClus v1.00
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.