Problema de minimização de custo de propagação de influência em redes sociais : uma abordagem heurística

Abstract

With the growth of social networks in recent years, problems related to the dissemination of information on these networks have gained more and more notoriety in the scientific community. Many of these problems are about finding individuals who are crucial to the process of spreading influence, including the Social Network Influence Propagation Cost Minimization Problem (PMCPIRS), which is about finding a set of key individuals who can influence a certain number of users at the lowest possible cost to hire them. Currently, the techniques presented in the literature for solving this problem focus only on exact methods. In contrast, this paper presents the development of a metaheuristic as an option for resolution of different instances, that is, characterized by small, medium or large propagations. In terms of GAP, computational experiments performed on a set of 108 instances attest to the efficiency of the method to obtain good PMCPIRS solutions.