Texto completo
| |
| Autor(es): |
Felipe de Carvalho Pereira
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Data de defesa: | 2021-03-22 |
| Membros da banca: |
Pedro Jussieu de Rezende;
Claudio Nogueira de Meneses;
Fábio Luiz Usberti
|
| Orientador: | Pedro Jussieu de Rezende; Cid Carvalho de Souza |
| 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 -> N* é 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 ignorantes" de uma determinada informação, exceto por um conjunto inicial de "disseminadores", denominado "conjunto semente". Se um vértice ignorante 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 igual ou maior que 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 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 (AU) | |
| Processo FAPESP: | 19/22297-1 - Algoritmos exatos e heurísticos para o problema Perfect Awareness |
| Beneficiário: | Felipe de Carvalho Pereira |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |