Jordan University of Science and Technology

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


Authors:  ┬áMahmoud Al-Ayyoub , Mohammed Al-andoli , Yaser Jararweh, Mohammad Smadi , Brij Gupta

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.