Improving fuzzy C-mean-based community detection in social networks using dynamic parallelism

摘要

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 extensive 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. (C) 2018 Elsevier Ltd. All rights reserved.