Resumo: A propagação de influência em redes sociais tem sido estudada como problemas de otimização combinatória desde o início do século XXI e desempenha um papel significativo no contexto do marketing viral. Nesta tese, investigamos três problemas de otimização NP-difíceis relacionados a propagação de informações em redes sociais, nos quais buscamos identificar indivíduos influentes capazes de induzir uma difusão de informações em cadeia e com amplo alcance, minimizando os custos associados ao recrutamento desses influenciadores. Embora esses problemas compartilhem características importantes - eles podem ser descritos como problemas em grafos nos quais os indivíduos são representados por vértices e a informação flui por arestas - eles diferem na forma como a informação se espalha e nas restrições impostas à seleção dos propagadores. Para o Least Cost Directed Perfect Awareness Problem, apresentamos resultados teóricos sobre a dificuldade do problema, juntamente com quatro formulações de programação inteira, três modelos de programação por restrições e uma heurística baseada na meta-heurística GRASP. Para abordar o Weighted Target Set Selection, propomos uma mateurística híbrida com múltiplos estágios que integra um método de pré-processamento com técnicas de programação linear e inteira e um procedimento de large neighborhood search. Por fim, para resolver o Graph Burning Problem, introduzimos um algoritmo exato que encontra soluções ótimas por meio de uma busca binária sobre o espaço de soluções, resolvendo múltiplos problemas de decisão na forma de modelos matemáticos. Para todos esses problemas realizamos experimentos computacionais com uma variedade de instâncias, demonstrando a eficiência e eficácia dos métodos propostos Ver menos

Abstract: The propagation of influence on social networks has been studied as combinatorial optimization problems since the beginning of the 21st century and plays a significant role in the context of viral marketing. In this dissertation, we investigate three NP-hard optimization problems related to the spread of information on social networks, in which we seek to identify influential individuals capable of inducing a widespread cascade diffusion of information while minimizing the costs associated with recruiting these influencers. Although these problems share key characteristics - they can be described as graph problems where individuals are represented by vertices and the information flows through edges - they differ in how information spreads and in the constraints imposed on the selection of the spreaders. For the Least Cost Directed Perfect Awareness Problem, we provide theoretical results regarding the problem's hardness, along with four integer programming formulations, three constraint programming models, and a heuristic based on the metaheuristic GRASP. To tackle the Weighted Target Set Selection, we present a multi-stage hybrid matheuristic that integrates a preprocessing method with linear and integer programming techniques and a large neighborhood search procedure. Lastly, to solve the Graph Burning Problem, we introduce an exact algorithm that finds optimal solutions by performing a binary search on the solution space, solving multiple decision problems in the form of mathematical models. For all these problems, we conduct computational experiments with a variety of instances, demonstrating the efficiency and effectiveness of the proposed methods Ver menos