Design and Implementation of Metaheuristic Algorithms for Social Network Influence Problems

Abstract

Optimization has been a constant concern throughout history, from ancient Greeks seeking the most efficient way to organize cities to modern algorithms optimizing business processes. The significance of optimization lies in its ability to solve complex problems, enhance efficiency, and make informed decisions. Over centuries, optimization has proven to be fundamental for human progress. Nowadays, optimization has gained even greater importance across various fields, owing to the increasing complexity of the challenges we face. From business logistics to route planning in navigation, optimization has become an essential tool for tackling ever-evolving issues. The ability to efficiently and accurately solve problems is crucial in an increasingly interconnected world that heavily relies on technology. To address these challenges, there are various methodologies in optimization, including exact methods, approximations, genetic, and heuristic algorithms. These approaches offer flexible and adaptive solutions for a variety of problems, enabling researchers and professionals to find the best possible solution in different contexts. This thesis focuses specifically on problems related to Social Network Analysis, an area of study that has gained prominence in the digital age. Within this discipline, various problems are identified, with particular attention directed towards the concept of influence. The central problem involves selecting users within a social network in a way that maximizes or minimizes influence on other users, considering potential constraints such as maximum budgets. Defining influence within the context of social networks presents a significant challenge due to the diversity of available methods. The ability to strategically select users has practical applications in marketing campaigns, disease eradication, and the detection of misinformation campaigns. The complexity of these problems is exacerbated by the NP−hard nature of many of them, implying that finding exact solutions is impractical for large social networks. While approximate algorithms exist, in certain cases, it is crucial to have quick and high-quality information, such as in disease detection. Therefore, this thesis focuses on the use of heuristics and metaheuristics to address influence problems in social networks. These approaches provide efficient and adaptable solutions, particularly in situations where speed and precision are paramount. This thesis proposes different heuristic and metaheuristic algorithms to address the most widespread variants of influence problems in social networks. Various methodologies, such as Greedy Randomized Adaptive Procedure Search (GRASP) or Path Relinking (PR), have been applied and evaluated on real-world networks to verify their utility and applicability in these contexts. The results obtained surpass current proposals in all studied variants of social network influence problems.