Resumen
In a society where the immediacy is becoming more and more established, there is a need to obtain solutions to real-world problems quickly and accurately. With respect to precision, or more specifically optimality, the scientific discipline that deals with this issue is optimization. This knowledge area can be seen as a meeting point between various disciplines, such as operations research, statistics, computer science or artificial intelligence. There are a lot of interesting real-life problems that can be approached from the optimization point of view: calculating the fastest route to go from home to work, finding the best way to place the maximum number of containers in a ship to send products around the world, or knowing the weakest point of a computer network in order to dedicate more resources to protect it. All these problems can be solved by two different approaches: exact algorithms or approximated algorithms. The main problem of exact algorithms is that, when the space of solutions to be explored is too large, the computation time required to provide an optimal solution to the problem is unacceptable. In this context, approximated algorithms emerge as an alternative, with the main disadvantage that they do not guarantee to reach an overall optimal solution. However, if the adequate technique is selected, a high-quality solution can be assured. This is the case of heuristic and metaheuristic algorithms. The Community Detection Problem (CDP) is an NP-hard problem that belongs to the Social Network Analysis (SNA) family of problems. The main objective in CDP is to group the users within a social network depending on their characteristics, their relations and other properties of the network itself. It is said that a good solution for the CDP is characterized by a good community structure. Community structure is considered good when the resulting groups contain nodes that are highly connected among them and sparsely connected with nodes in other groups. There are different variants of the same problem in which different constraints are considered. For example, the number of communities that a solution contains is fixed a priori, or nodes can be assigned to different groups simultaneously. The CDP can also be faced optimizing different objective functions simultaneously, and taking into account single or multiple objectives. Despite all of the above, the ultimate goal is always the same: to obtain solutions with a good community structure. In this Thesis different heuristic and metaheuristic algorithms are proposed to solve the most extended variants of CDP. The problems have been tackled by considering a wide variety of methodologies, such as Variable Neighborhood Search (VNS), Iterated Greedy (IG) or Scatter Search (SS). Each proposal has been evaluated against both synthetic and real-world networks to check their utility and application in these contexts. Obtained results overcome the state of the art proposals in all studied variants of CDP.
Sergio Pérez-Peló
Doctor en Inteligencia Artificial
Estudiante de doctorado en la Universidad Rey Juan Carlos