Metadata-Version: 2.1
Name: vieclus
Version: 1.2.0
Summary: Vienna Graph Clustering -- VieClus
Keywords: graph,clustering,graph-clustering,modularity,community-detection
Author: Christian Schulz
License: MIT
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: C++
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.8
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering
Project-URL: Homepage, http://vieclus.taa.univie.ac.at
Project-URL: Repository, https://github.com/VieClus/VieClus
Requires-Python: >=3.8
Description-Content-Type: text/markdown

VieClus v1.1 
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
=====

The graph clustering framework VieClus -- Vienna Graph Clustering.

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. 



This is the release of our memetic algorithm, VieClus (Vienna Graph Clustering), to tackle the graph clustering problem. 
A key component of our contribution are natural recombine operators that employ ensemble clusterings as well as multi-level techniques. 
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.
Moreover, while the previous best result for different instances has been computed by a variety of solvers, our algorithm can now be used as a single tool to compute the result. **In short our solver is the currently best modularity based clustering algorithm available.**

<p align="center">
<img src="./img/example_clustering.png"
  alt="example clustering"
  width="538" height="468">
</p>

## Main project site:
http://vieclus.taa.univie.ac.at

Installation Notes
=====

Before you can start you need to install the following software packages:

- Argtable (http://argtable.sourceforge.net/)
- OpenMPI (http://www.open-mpi.org/). Note: due to removed progress threads in OpenMPI > 1.8, please use an OpenMPI version < 1.8 or Intel MPI to obtain a scalable parallel algorithm.

Once you installed the packages, just type 
``./compile_withcmake.sh``

To compile without MPI support (using pseudo_mpi.h), use:
``./compile_withcmake.sh NOMPI``

**Note:** MPI support is preferred as it enables the parallel algorithm which typically yields better solutions.

Once you did that you can try to run the following command:

With MPI support:
``mpirun -n 2 ./deploy/vieclus examples/astro-ph.graph --time_limit=60``

Without MPI support:
``./deploy/vieclus examples/astro-ph.graph --time_limit=60``

For a description of the graph format please have a look into the manual.


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

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

