A Parallel Graph Partitioning Approach to Enhance Community Detection in Social Networks

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.