miniVite

Short Description
miniVite is a proxy application that implements a single phase of Louvain method in distributed memory for graph community detection.
Institution
Pacific Northwest National Laboratory
Sponsors
NSF, DOE
Parent Application/Code
http://hpc.pnl.gov/people/hala/grappolo.html
Keywords
community detection, graph clustering, parallel graph generation
Programming Languages/Paradigms
C++, MPI, OpenMP
Release/Version Number
1.0
Spack Package Name
minivite
Detailed description
MiniVITE implements a community detection approach known as the Louvain method. It is a form of greedy algorithm applied to the community detection problem. The Louvain method works as follows. At first, the vertices are assigned each own to it's community. Then, at each iteration of the method, every vertex is checked to see whether it is beneficial for the community assignment to move it to a neighboring community. Several iterations are performed until the gains performed in an iteration are below a certain threshold or no vertices are moved. The parallel implementation of the Louvain method is not straight forward, as several updates of the vertices need to be performed in parallel. In practice, it means that each vertex move only contains partial information of the states of the community distribution. Still communication costs are quite high. For more details about the parallel implementation is described in this article.