Abstract:  

In Social Network Analysis (SNA), a common algorithm for community detection iteratively applies three phases: spectral mapping, clustering (using either the Fuzzy C-Means or the K-Means algorithms) and modularity computation. Despite its effectiveness, this method is not very efficient. A feasible solution to this problem is to use Graphics Processing Units. Moreover, due to the iterative nature of this algorithm, the emerging dynamic parallelism technology lends itself as a very appealing solution. In this work, we present different novel GPU implementations of both versions of the algorithm: Hybrid CPU-GPU, Dynamic Parallel and Hybrid Nested Parallel. These novel implementations differ in how much they rely on CPU and whether they utilize dynamic parallelism or not. We perform an exten- sive set of experiments to compare these implementations under different settings. The results show that the Hybrid Nested Parallel implementation provide about two orders of magnitude of speedup.