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...

Full description

Saved in:
Bibliographic Details
Published in:Computers & electrical engineering 2019-03, Vol.74, p.533-546
Main Authors: Al-Ayyoub, Mahmoud, Al-andoli, Mohammed, Jararweh, Yaser, Smadi, Mohammad, Gupta, Brij
Format: Article
Language:English
Subjects:
Algorithms
Clustering
Communities
Community detection
Dynamic parallelism
Fuzzy C-mean
GPUs
Graphics processing units
Iterative methods
Mapping
Modularity
Network analysis
Social networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0045-7906
1879-0755
DOI:10.1016/j.compeleceng.2018.01.003