A Computational Study of the Perfect Awareness Problem

• Felipe de C. Pereira UNICAMP
• Pedro J. de Rezende UNICAMP
• Cid C. de Souza UNICAMP

DOI: https://doi.org/10.5753/ctd.2022.222955

Resumo

The Perfect Awareness Problem (PAP) is a combinatorial optimization problem that models the spreading of information in social networks. The objective is to find a smallest subset of individuals that are able to start a viral propagation whereby a given news reaches everyone on a network, under certain dissemination restrictions. Considering that PAP is NP-hard, we present four novel heuristics based on the metaheuristic GRASP and show that the best one of our methods outperforms the only previously known heuristic designed for the problem. Our contributions also include: (i) a new publicly available benchmark of 840 instances that simulate social network relations, (ii) procedures for preprocessing instances, and (iii) two integer programming models to generate exact solutions for PAP. We conducted an exhaustive set of comparative experiments, followed by statistical analyses, showing the efficacy and efficiency of our algorithms.

Palavras-chave: Spreading of information, Social networks, GRASP (Metaheuristic), Integer programming

Referências

Bakshy, E., Rosenn, I., Marlow, C., and Adamic, L. (2012). The role of social networks in information diffusion. In Proceedings of the 21st International Conference on World Wide Web, pages 519–528.

Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science, 286:509–512.

Chen, N. (2009). On the approximability of influence in social networks. SIAM Journal on Discrete Mathematics, 23(3):1400–1415.

Chen, W., Lakshmanan, L., and Castillo, C. (2013). Information and influence propagation in social networks. Synthesis Lectures on Data Management, 5:1–177.

Cordasco, G., Gargano, L., Rescigno, A., and Vaccaro, U. (2018). Evangelism in social networks: Algorithms and complexity. Networks, 71(4):346–357.

Cordasco, G., Gargano, L., and Rescigno, A. A. (2019). Active influence spreading in social networks. Theoretical Computer Science, 764:15–29.

Grandoni, F. (2006). A note on the complexity of minimum dominating set. Journal of Discrete Algorithms, 4(2):209–214.

Hochbaum, D. S. (1997). Approximation Algorithms for NP-hard Problems. PWS Publishing Co., USA.

Pereira, F. C. (2021). A computational study of the Perfect Awareness Problem. Master’s thesis, University of Campinas, Brasil.

Pereira, F. C., de Rezende, P. J., and de Souza, C. C. (2020a). Exact Algorithms and Heuristics for the Perfect Awareness Problem. In Posters of the LATIN Conference 2020, São Paulo. Abstract and poster available on [link] and [link].

Pereira, F. C., de Rezende, P. J., and de Souza, C. C. (2021). Effective heuristics for the perfect awareness problem. Procedia Computer Science, 195:489–498. Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium.

Pereira, F. C., de Souza, C. C., and de Rezende, P. J. (2020b). The Perfect Awareness Problem Benchmark Instances. Available on [link].

Resende, M. G. and Ribeiro, C. C. (2010). Greedy randomized adaptive search procedures: Advances, hybridizations, and applications. In Handbook of Metaheuristics, pages 283–319. Springer, USA.