FastCELF++: Uma heurística de baixo custo computacional para maximização da influência em redes
Maximização de influência, redes sociais, teoria de grafos, otimização
As redes sociais refletem os relacionamentos e interações entre indivíduos e têm desempenhado um papel muito importante na difusão de informação, em que a comunicação de ideias e compartilhamento de opiniões acontecem a todo momento. São diversos os exemplos de como as redes sociais podem afetar o comportamento dos indivíduos, tais como o marketing viral, a difusão de memes e a propagação de fake news. Essa dinâmica de difusão de informação tem motivado o estudo de diversas abordagens para identificar os principais influentes em uma rede.
O problema de Maximização de Influência consiste em encontrar um subconjunto S, chamado de conjunto de sementes, de no máximo k elementos, de modo que a propagação máxima (esperada) seja alcançada por meio de um modelo de difusão, tendo S como os influenciadores iniciais em uma rede. Já foi demonstrado que o o problema de maximização de influência é um problema de otimização NP-difícil, portanto, devido à sua complexidade, é inviável encontrar o subconjunto S que garanta a difusão mais abrangente.
A abordagem mais comum para este problema é a utilização de algoritmos aproximados, destacando-se o Cost-Effective Lazy Forward (CELF), cerca de 700 vezes mais rápido do que a estratégia gulosa proposta por Kemp et al., e o CELF++, que apresenta um ganho em tempo de execução entre 35 a 55% sobre o CELF.
Este trabalho apresenta uma modificação dos dois algoritmos estado-da-arte supracitados, CELF e CELF++, substituindo as simulações de Monte Carlo por estimativas de difusão (metamodelos), para a seleção de conjunto de sementes. Buscou-se sintetizar e, com um foco especial, mostrar que: (1) os metamodelos podem ser usados para estimar qualitativamente a difusão de conjuntos de sementes; (2) o uso de métodos já conhecidos na literatura em conjunto com metamodelos é capaz de identificar, ordens de grandeza mais rápido, indivíduos mais influentes e, em alguns casos, até superar o resultado desses métodos em propagação.