Paper Info
Title
A Parallel Graph Partitioning Approach To Enhance Community Detection In Social Networks
Abstract
Dealing with complex networks is often a challenge due to the high computational cost in analyzing a huge amount of data. Partitioning methods can decrease the complexity of large structures by reducing them to smaller, less connected parts. Also, the data splitting allows the use of multiprocessing to accelerate the execution of data procedures with simultaneity and parallelism. In this paper, we propose a new parallel partitioning algorithm with a focus on assisting in community detection in social networks. The algorithm uses a subtree-splitting strategy, as well as boundaries defined, in order to cut the network into n balanced subnetworks. Our proposal stands out for the focus on aiding density-based approaches, such as the NetSCAN clustering algorithm, considering two particulars: (i) keeping the partitions connectivity, and; (ii) allowing node overlapping between partitions. Experiments were carried out with different instances intending to investigate the partitions obtained and evaluate our proposal. Furthermore, the algorithm performance analysis in a large network is employed, sequential and parallel implementations are compared in terms of execution time and memory consumption. Evidence was provided that the proposed algorithm is able to split an extensive data set into balanced partitions with optimistic performance results.
Year
DOI
Venue
2020
10.1109/ISCC50000.2020.9219602
2020 IEEE SYMPOSIUM ON COMPUTERS AND COMMUNICATIONS (ISCC)
Keywords
DocType
ISSN
social network, parallel partitioning approach, community detection, subtree-splitting strategy, performance analysis
Conference
1530-1346
Citations 
PageRank 
References 
0
0.34
0
Authors
5
Name
Order
Citations
PageRank
Tales Lopes101.01
Victor StröEle22911.27
Mario A. R. Dantas36925.60
Regina M. M. Braga49425.25
Jean-François Méhaut528837.88