Goal of this project was to implement Community detection algorithm (using Louvain method) based on a paper: Community Detection on the GPU.
Flag -f specifies input file, -g gain threshold, -v represents verbose mode
make
./gpulouvain -f mtx-matrix-file -g min-gain [-v]Obviously, first step of the algorithm is to read data from input file.
I assume that given graph is undirected.
Actual algorithm is split into 2 parts:
- modularity optimisation - in this step we find currently optimal community (group of vertices)
- community aggregation - in this we merge vertices within a single community into one new vertex (keeping edges between communities)
These 2 steps are repeated as long as modularity gain is bigger than a threshold (provided by user).
In the end final modularity is printed. In verbose mode original vertex -> final community assignment is additionally printed.
During both phases vertices are divided into buckets based on degrees. This way, we dedicate more resources on a vertex with greater degree. Buckets containing vertices with smaller degrees use only shared memory, this way we utilise slow global memory only when it is necessary.