A Parallel Particle Swarm Optimization for Community Detection in Large Attributed Graphs

A Parallel Particle Swarm Optimization for Community Detection in Large Attributed Graphs

Chaitanya Kanchibhotla, Somayajulu D. V. L. N., Radha Krishna P.
Copyright: © 2022 |Pages: 23
DOI: 10.4018/IJAMC.306913
Article PDF Download
Open access articles are freely available for download


Social network analysis (SNA) is an active research domain that mainly deals with large social graphs and their properties. Community detection (CD) is one of the active research topics belonging to this domain. Social graphs in real-time are huge, complex, and require more computational resources to process. In this paper, the authors present a CPU-based hybrid parallelization architecture that combines both master-slave and island models. They use particle swarm optimization (PSO)-based clustering approach, which models community detection as an optimization problem and finds communities based on concepts of PSO. The proposed model is scalable, suitable for large datasets, and is tested on real-time social networking datasets with node attributes belonging to all three sizes (small, medium, and large). The model is tested on standard benchmark functions and evaluated on well-known evaluation strategies related to both community clusters and parallel systems to show its efficiency.
Article Preview

1. Introduction

Real-world optimization problems are usually complex in nature and are NP-hard. It can be due to large dimensions and multiple objectives. One of such real-world problems belongs to the domain of complex networks. The social networks domain belongs to complex networks in which several fundamental problems can be considered as optimization problems. Resolving complex optimization problems requires heavy CPU computation time and is challenging for a computer with standard hardware. Some of the reasons for the complexity in real-world social networks are large network topologies with numerous edges and nodes and the frequency of network growth.

The derivation of important structures from large social networks is always an interesting and noteworthy problem. In social network terminology, these structures are called communities. From the social network's perspective, a community is a dense substructure in which the nodes communicate more frequently with each other when compared to node communications outside of the group (Newman,2011). Analyzing social network groups allows us to expose the social features and predict important information such as discussion, entities involved in the discussion, etc. (Stanley,1994) In literature, two types of algorithms have been proposed by researchers. The first type considers community detection is considered as a clustering problem. In contrast, the second type considers community detection as an optimization problem and is solved by techniques such as optimizing modularity (Newman,2004)(Hespanha,2004)(Guimera,2011)(Blondel,2008). These works focus on graph structures that do not analyze the content of nodes in a graph. Analyzing node contents is important because most real-time social networks store helpful information in their nodes, not limited to user information and connectivity information.

In this work, we consider community detection is considered to be an optimization problem and solve it using a popular evolutionary, iterative algorithm called Particles Swarm Optimization (PSO). Most of the evolutionary algorithms are parallel by nature, and they contain individuals which improve during iterations. PSO has already proved to solve many real-world problems (Goldberg. 1989)On the other hand, applying optimization on large real-world networks can be computationally expensive due to the presence of large number of decision variables. Due to the iterative nature of evolutionary algorithms, applying optimization on large real-world networks can be time, resource-consuming and can increase the objective function evaluation time. Applying PSO to large-scale real-world optimization problems can degrade the algorithm's performance, making it unsuitable for large-scale optimizations R. Cheng and Y. Jin,(2015).To address the above problems, we present a hybrid parallel architecture and implement it on one of the previously introduced community detection algorithms based on PSO called PSO-based clustering (PSOC) (K. Chaitanya et al., 2018).

Complete Article List

Search this Journal:
Volume 14: 1 Issue (2023)
Volume 13: 4 Issues (2022): 2 Released, 2 Forthcoming
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing