Best partition

This repo is the author's implementation of the algorithms described in the papers:

1. "Subnetwork Constraints for Tighter Upper Bounds and Exact Solution of the Clique Partitioning Problem"
2. "Network Size Reduction Preserving Optimal Modularity and Clique Partition."

Depending on the user choice, the program reproduces results from the corresponding article. The first algorithm applies the branch-and-bound method to solve the clique partitioning problem or maximize the modularity function revealing the network's community structure. The second article described a technique for network size reduction that preserves the optimal partition allowing for a much faster solution of the CPP.

If you find this work useful, please, consider citing:

A. Belyi, S. Sobolevsky, A. Kurbatski, C. Ratti, "Subnetwork Constraints for Tighter Upper Bounds and Exact Solution of the Clique Partitioning Problem," arXiv preprint arXiv:2110.05627

Building and running

We tested this code only on Linux and Mac. In theory, it should also work on Windows, but please feel free to contribute if you find any problems.

The project is configured using CMake, so you need to install it first. Furthermore, to solve linear programming problems, we use COIN_OR CLP and CBC, so in order to build the project, you also need to install the COIN_OR CBC solver. To do that, follow the instructions from the official page. On Mac we recommend using Homebrew, on ubuntu/debian use sudo apt install coinor-libcbc-dev. If you installed to custom location, provide CBC_ROOT="path/to/cbc" variable to CMake. You can also use CPLEX if you have it. CMake should find it if installed in the default location, otherwise provide the path in CPLEX_ROOT. The steps are:

1. Install CMake;
2. Install CBC;
3. Run CMake:

mkdir build
cd build
cmake ..

4. Run make;
5. Run built program: ./BestPartition.

It should reproduce the results presented in the paper. To run the algorithm on a custom network, modify main.cpp accordingly, rebuild, and run.