| Full text | |
| Author(s): |
Pereira, Felipe de C.
;
de Rezende, Pedro J.
;
de Souza, Cid C.
;
Ferreira, CE
;
Lee, O
;
Miyazawa, FK
Total Authors: 6
|
| Document type: | Journal article |
| Source: | PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM; v. 195, p. 10-pg., 2021-01-01. |
| Abstract | |
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) | |
| FAPESP's process: | 14/12236-1 - AnImaLS: Annotation of Images in Large Scale: what can machines and specialists learn from interaction? |
| Grantee: | Alexandre Xavier Falcão |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 19/22297-1 - Exact algorithms and heuristics for the Perfect Awareness problem |
| Grantee: | Felipe de Carvalho Pereira |
| Support Opportunities: | Scholarships in Brazil - Master |
| FAPESP's process: | 18/26434-0 - Exact and heuristic algorithms for solving difficult problems related to computational geometry |
| Grantee: | Pedro Jussieu de Rezende |
| Support Opportunities: | Regular Research Grants |