16 dez 2024
14:00 Defesa de Doutorado Sala 85 do IC2
Tema
Exact Algorithms and Heuristics for Optimization Problems on the Spread of Information on Social Networks
Aluno
Felipe de Carvalho Pereira
Orientador / Docente
Pedro Jussieu de Rezende - Coorientador: Tallys Hoover Yunes
Breve 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 dissertação, investigamos três problemas de otimização NP-difíceis relacionados à 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últiplas 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.
Banca examinadora
Titulares:
| Pedro Jussieu de Rezende | IC/UNICAMP |
| Breno Piva Ribeiro | DCOMP/UFS |
| Fábio Protti | IC/UFF |
| Kelly Cristina Poldi | IMECC/UNICAMP |
| Santiago Valdés Ravelo | IC/UNICAMP |
Suplentes:
| Ruben Interian Kovaliova | IC/UNICAMP |
| Carla Negri Lintzmayer | CMCC/UFABC |
| Mário César San Felice | DC/UFSCar |
| Hugo Kooki Kasuya Rosado | TUM/Alemanha |