Maximal Component Detection in Graphs Using Swarm-Basedand Genetic Algorithms

Abstract

Nowadays, there is an increasing interest in the application of Collective Intelligence and Evolutive optimization algorithms for solving NP-complete problems. This is because the solution or optimization process of these type of problems requires a huge amount of resources (such as computational effort or time). Some examples of these types of problems are scheduling problems, constrained satisfaction problems, or routing problems. Collective strategies are heuristics that allow to look for new solutions in real complex problems using concepts extracted from a metaphor of social behavior of ants, bees, bacteria, flocks of birds and/or schools of fish. In this paper we propose a practical comparison between a classical Geneticbased approach and a Swarm-based strategy applied to the detection of maximal component in graphs. This work describes how these two different optimization strategies can be adapted and used to extract the different sub-graphs that contains the maximum number of nodes. Experimental results show the best results are obtained using ACO algorithm, but new strategies must be taken into account in order to improve the results.

Antonio Gonzalez-Pardo

Associate Professor

Lecturer at the Computer Science Department. Main research interests are related to Computational Intelligence and Metaheuristics applied to Social Networks Analysis, and the optimization of graph-based problems.