Algorithms

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.