puzzlef/louvain-communities-openmp

Design of OpenMP-based Parallel Louvain algorithm for community detection, that prevents internally disconnected communities.

louvain-communities-openmp's Issues

How does NetworKit Louvain (PLM) work?

In file include\networkit\community\PLM.hpp:

How does Nido (Chou and Ghosh) multi-GPU Louvain work?

In Nido, each thread manages one or more GPUs.

They appear to use full graph modularity computation, and backing off if the change in modularity is not positive. This is not efficient. It is easier to track delta-modularity instead.

They appear to be using unordered_maps during the aggregation phase. Exploring their program will take much longer than anticipated. Maybe some other day ...

How does Cheong et al.'s multi-GPU Louvain work?

The source code of their implementation is not available online. Lets see what I can find from their paper. They present some interesting profiling results - indicating most of the runtime is spent in the local-moving phase (when unoptimized).

At the highest level, the original network is partitioned into a number of subnetworks and a set of removed links which consists of the links that join nodes residing in different sub-networks. The Louvain method can then be applied to solve the community detection problem in each of the sub-networks in parallel.

After this, the resulting networks are combined into a single network using the removed links, and then the Louvain method is applied once more on this combined network to obtain the final community results.

The second level of parallelism involves visiting nodes in parallel during each iteration of the modularity optimization phase.

The third and lowest level of parallelism involves computing the gain in modularity of inserting a node into each of its neighboring communities in parallel. This level of parallelism is intuitive and would be effective when a node has a large number of neighboring communities.

GPU kernel 1 performs two functions. Based on the current community status of the network, the assigned GPU thread converts each neighboring node ID in the data structure to its corresponding community ID. The thread also prepares the key for the GPU radix sort in the next step.

The GPU radix sort arranges the entire array first in order of increasing node ID and then in order of increasing neighboring community ID for array elements with the same node ID. The radix sort in the Thrust library is used in this paper.

With the sorted array, each node is being assigned a GPU thread in GPU kernel 2. The thread goes down the array elements belonging to the node and sums up the weights for adjacent elements with the same neighboring community ID to give the final output of FNC.

It appears Cheong et al. do not perform aggregation phase on the GPU.

In the paper Scalable multi-node multi-GPU Louvain community detection algorithm for heterogeneous architectures by Bhowmick et al. (Section 6.4.2 Comparison with the work by Cheong et al.):

The GPU is used only to find neighbor communities and best neighbor community, while the other steps of the Louvain algorithm use multi-core CPU.

How does Bhowmick et al.'s multi-node multi-device (HyDetect) work?

I am not able to find details of how they implement Louvain algorithm. The source code isnt linked in the paper. Perhaps I should look at their HyDetect code. Another thing to focus is on parameter optimization.

Below is overview of thier algorithm.

How does Ghosh et al.'s multi-CPU Louvain work?

In the paper Scalable multi-node multi-GPU Louvain community detection algorithm for heterogeneous architectures by Bhowmick et al. (Section 6.4.1 Comparison with the work by Ghosh et al.):

The work by Ghosh et al. uses only the CPUs. In this work, the graph is partitioned randomly.