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 Ver menos

Abstract: The Perfect Awareness Problem (PAP) is a combinatorial optimization problem within the area of viral marketing and related to the spread of information in social networks. The problem can be described as follows. The input consists of a pair (G,t) where G = (V,E) is an undirected graph and t : V -> N* is a "threshold function". The set of vertices V corresponds to the collection of individuals in a social network and the edges in E indicate pairs of individuals between whom communication is possible. It is assumed that, initially, all individuals in the network are ignorant of a certain information, except for an initial set of "spreaders", called "seed set". If an ignorant vertex v is informed by a neighboring spreader, then v becomes "aware". Moreover, as soon as v is informed by a number of neighboring spreaders greater than or equal to t(v), v also becomes a spreader. The objective of the problem is to find a seed set of minimum size, from which the propagation of the information makes all members of the network aware. The PAP is NP-hard and, so far, only one heuristic has been reported in the literature for this problem. In this work, we present four novel heuristics for the PAP, based on the metaheuristic GRASP. In addition to these algorithms, we developed the first two Integer Programming formulations for the problem, in order to obtain optimal solutions for PAP instances, so as to compare them with the solutions produced by our heuristics. The contributions of this research also include three preprocessing approaches for reducing the size of input instances and a new benchmark of 840 instances of the PAP that simulate social networks. An extensive set of comparative experiments was conducted, followed by statistical analyses, showing the effectiveness and efficiency of the proposed heuristics. Furthermore, we applied the best one of our heuristics to 17 instances from the literature that represent real social networks and found that our algorithm surpasses the only previously reported heuristic for the PAP Ver menos