22 mar 2021
14:00 Defesa de Mestrado Integralmente a distância
Tema
Um Estudo Computacional do Problema do Gnosticismo Perfeito
Aluno
Felipe de Carvalho Pereira
Orientador / Docente
Pedro Jussieu de Rezende (Orientador) / Cid Carvalho de Souza (Coorientador)
Breve resumo
"O Problema do Gnosticismo Perfeito (PAP do inglês Perfect Awareness Problem) é um problema de otimização combinatória inserido no tópico de marketing viral que envolve a propagação de informações em redes sociais. O problema pode ser descrito da seguinte forma. A entrada consiste em um par (G,t), onde G = (V,E) é um grafo não direcionado e t : V → Z+ é uma função limiar. O conjunto de vértices V corresponde à coleção de indivíduos de uma rede social e o conjunto de arestas E representa as comunicações possíveis entre tais indivíduos.
Supõe-se que, inicialmente, todos os indivíduos da rede são desconhecedores de uma determinada informação, exceto por um conjunto inicial de disseminadores, denominado conjunto semente. Se um vértice desconhecedor v é informado por um vizinho disseminador, então v se torna conhecedor. Além disso, assim que v é informado por uma quantidade de vizinhos disseminadores maior que ou igual a t(v), v passa a ser também um disseminador. O objetivo do problema é determinar um conjunto semente de tamanho mínimo, a partir do qual uma propagação da informação faz com que todos os membros da rede sejam conhecedores dela.
O PAP é um problema NP-difícil e até agora somente um método heurístico foi relatado na literatura para lidar com ele. Neste trabalho, apresentamos quatro novas heurísticas para o PAP baseadas na meta-heurística GRASP. Além desses algoritmos, desenvolvemos as duas primeiras formulações de Programação Linear Inteira (PLI) para o problema, com o objetivo de obtermos soluções ótimas para instâncias do PAP e podermos comparar com elas as soluções produzidas por nossas heurísticas.
As contribuições da pesquisa também incluem três abordagens de pré-processamento de instâncias para redução do tamanho das entradas e um novo benchmark de 840 instâncias do PAP que simulam redes sociais. Foi realizado ainda um conjunto extenso de experimentos comparativos, seguidos de análises estatísticas, mostrando a eficácia e eficiência das heurísticas propostas. Além disso, aplicamos a melhor de nossas heurísticas a 17 instâncias da literatura que representam redes sociais reais e verificamos que nosso algoritmo supera a única heurística previamente existente para o PAP."
Banca examinadora
Titulares:
| Pedro Jussieu de Rezende | IC/UNICAMP |
| Claudio Nogueira de Meneses | CMCC/UFABC |
| Fábio Luiz Usberti | IC/UNICAMP |
Suplentes:
| Lehilton Lelis Chaves Pedrosa | IC/UNICAMP |
| Maycon Sambinelli | CMCC/UFABC |