Nerstrand - Fast Multi-threaded Graph Clustering

Nerstrand is a multi-threaded multilevel graph clustering tool for generating clusterings with high modularity. It supports both finding a specified number of clusters/communities as well as detecting the number of clusters/communities.

Source Code

Latest - nerstrand-0.5.0.tar.gz
Archive

Nerstrand is available under the MIT license.

Building

Building Nerstrand requires a C99 compiler supporting OpenMP specification 3.0 or greater (almost all of my testing is with GCC) and CMake. The configure script requires Bash, however it is possible to do the configuration by hand. To build Nerstrand with the default options, execute:

./configure && make

After it is built, the binary and the library will reside in ./build/[system-arch]/bin and ./build/[system-arch]/lib respectively (for most systems, [system-arch] will be Linux-x86_64, but depends on your OS/architecture). Nerstrand can the optionally be installed using make install (the default prefix is /usr/local, but can be changed with configure --prefix="my_prefix").

Usage

Nerstrand can then be used to cluster a graph as follows:

nerstrand test.graph

Most users will actually want the cluster assignment and not just runtime statistics, and should append the name of the output file.

nerstrand test.graph test.cluster

The Nerstrand binary currently only supports the Metis Graph Format for input.

Nerstrand currently has a large number of options, many of which are experimental. For a complete list, use the -h option:

nerstrand -h

Publications

Multi-threaded Modularity Based Graph Clustering using the Multilevel Paradigm

@article{lasalle2014nerstrand,
  title={Multi-threaded Modularity Based Graph Clustering using the Multilevel Paradigm},
  journal = "Journal of Parallel and Distributed Computing ",
  year = "2014",
  issn = "0743-7315",
  doi = "http://dx.doi.org/10.1016/j.jpdc.2014.09.012",
  url = "http://www.sciencedirect.com/science/article/pii/S0743731514001750",
  author = "Dominique LaSalle and George Karypis"
}

The Nerstrand Library API

Nerstrand provides an interface so that other programs can directly call Nerstrand. Please see the API for details.

Contact

You can contact me, Dominique LaSalle, at my last name (a) cs * umn.edu