Effective Heuristics for the Perfect Awareness Problem

Autor(es)

Pereira, Felipe de C. ; de Rezende, Pedro J. ; de Souza, Cid C. ; Ferreira, CE ; Lee, O ; Miyazawa, FK

• Tipo de documento: Artigo Científico
• Fonte: PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM; v. 195, p. 10-pg., 2021-01-01.

Resumo

In this paper, we study the Perfect Awareness Problem (PAP), which models the spreading of information on social networks. In this problem, we seek to find a smallest subset of seminal individuals that are sufficient to ascertain that a given news reaches everyone on a network, under certain dissemination restrictions. Knowing that PAP is NP-hard, we present three novel heuristics based on the metaheuristic GRASP and show that the best of our methods outperforms the only previously known heuristic. Besides the actual heuristics, our contributions include a new publicly available benchmark of 840 instances that simulate social network relations, approaches for preprocessing instances, and a linear programming formulation to generate exact solutions for PAP. Lastly, we present an exhaustive set of comparative experiments, followed by statistical analyses, showing the efficacy and efficiency of our algorithms. (C) 2021 The Authors. Published by Elsevier B.V. (AU)

• Processo FAPESP: 14/12236-1 - AnImaLS: Anotação de Imagem em Larga Escala: o que máquinas e especialistas podem aprender interagindo?
• Beneficiário: Alexandre Xavier Falcão
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• 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
• Processo FAPESP: 18/26434-0 - Algoritmos exatos e heurísticos para solução de problemas difíceis relacionados a geometria computacional
• Beneficiário: Pedro Jussieu de Rezende
• Modalidade de apoio: Auxílio à Pesquisa - Regular