GALA

Swift Unfolding of Communities: GPU-Accelerated Louvain Algorithm

Dependencies

• GNU Make 4.3
• NVCC 11.6
• GCC/G++ 10.4

Prepare graph

$ cd data
$ bash ./prepare_graph.sh

or

$ cd data
$ wget https://snap.stanford.edu/data/bigdata/communities/com-lj.ungraph.txt.gz
$ gunzip com-lj.ungraph.txt.gz

Compile

$ cd ../src/
$ make -j

Preprocess data

unweighted graph:

$ ./preprocess -f ../data/com-lj.ungraph.txt

weighted graph:

$ ./preprocess -f ../data/weighted-graph.txt -w

Run

$ ./gala_main -f ../data/com-lj.ungraph.txt.bin -t 0.000001 -p 0

-t sets the termination threshold, and -p sets the pruning strategy (0:MG 1:RM 2:Vite 3:MG+RM) .

Output

"iteration" refers to the iterations of the first phase of the Louvain algorithm, "Q" refers to the temporary modularity;

"round" refers to the rounds of both the first and second phases of the algorithm, "number of communities" refers to the current number of community partitions;

"final number of communities" and "final modularity" indicate the resulting partition and modularity at the end, and "elapsed time" refers to the program's running time.