Hybrid metaheuristic approach for community detection in complex networks

Abstract

Optimization is a scientific field dedicated to identifying optimal solutions from a set of feasible alternatives. Numerous critical problems in business, economics, and engineering can be formulated as optimization tasks. However, most such problems are classified as NP-Hard, meaning that finding an exact optimal solution is computationally infeasible for large-scale instances. In such cases, stochastic meta-heuristic methods are preferred as they provide near-optimal solutions within a reasonable timeframe. This stands in contrast to exact methods, which guarantee optimality but at the cost of exponentially longer runtimes. Consequently, the hybridization of optimization methods has garnered significant research interest in recent years as a strategy to reduce computational time while enhancing solution quality, i.e., both effectiveness and accuracy. This thesis addresses a specific NP-Hard optimization problem: community detection in complex networks, where the objective is to maximize the modularity metric. To tackle this challenge, we propose two novel hybrid meta-heuristics: • The Clustering Coefficient Discrete Bat Algorithm (CC-DBAT): This approach utilizes the clustering coefficient to generate an intelligent initial population. It is further enhanced by hybridizing it with the Fast Local Move heuristic and a random neighbors technique to improve its search capability. • The Fast Local Move Iterated Greedy (FLMIG) Algorithm: This method hybridizes the Iterated Greedy (IG) framework with the Fast Local Move heuristic. A novel reconstruction procedure is incorporated to ensure the connectivity of the detected communities. Experimental results, evaluated using multiple performance metrics, demonstrate that the proposed algorithms outperform existing state-of-the-art methods, achieving superior performance in both solution quality and computational efficiency