Maximização do bloqueio de influência generalizado

Abstract

Resumo: O termo desinformação pode ser entendido como uma informação falsa, dada no propósito de confundir ou induzir a erro. A partir dessa definição é possível relacionar o termo com o problema de maximização do bloqueio de influência. Esse problema é definido como: dada uma rede e um conjunto de vértices que são os pontos de partida para a disseminação de uma desinformação e um inteiro :, seu objetivo é encontrar : vértices na rede para serem pontos de partida para uma informação concorrente, de modo que o alcance da desinformação seja minimizado. Esse problema está altamente relacionado a disseminação de notícias falsas, abordá-lo é uma das maneiras de frear a disseminação de notícias falsas em redes sociais. Nos trabalhos da literatura, não são levados em consideração um custo para a escolha dos vértices. Tendo isso em vista, propomos cenários diferentes para esse problema, atribuindo custos diferentes para os vértices da rede, onde há um "orçamento" para escolher vértices da solução, chamamos esse problema de maximização do bloqueio de influência generalizado. Apresentamos demonstrações de propriedades matemáticas para o problema que podem garantir uma aproximação com um algoritmo guloso em relação à solução ótima. Ademais, são realizados experimentos que mostram que o sucesso de uma determinada estratégia varia substancialmente, dependendo da função que determina o custo de cada vértice. Em particular, investigamos a função de custo implicitamente usada em trabalhos anteriores na área que chamamos de custo uniforme (ou seja, todos os vértices têm custo 1) e uma função de custo que atribui custos de acordo com o grau dos vértices, chamada de penalização de grau. Mostramos que, embora as estratégias com bom desempenho nesses dois casos sejam muito diferentes umas das outras, ambas se correlacionam bem com estratégias simples de medidas de centralidade. Palavras-chave: Maximização do Bloqueio de Influência, Disseminação de Informações, Redes Sociais.

Abstract: The term disinformation can be understood as false information, either to confuse or mislead. From this definition, it is possible to relate the term to the problem of influence blocking maximization. This problem is defined as follows: given a network and a set of vertices that are the starting points for the dissemination of misinformation and an integer :, your goal is to find the : vertices in the network to be starting points for concurrent information so that the scope of disinformation is minimized. This problem is highly related to the spread of fake news, addressing it is one of the ways to stop the spread of fake news on social networks. In the literature, the cost for choosing the vertices is not taken into account. With this in mind, we propose different scenarios for this problem, assigning different costs to the vertices of the network, where there is a "budget" to choose vertices of the solution, we call this problem generalized influence blocking maximization. We present demonstrations of mathematical properties for the problem that can guarantee an approximation with a greedy algorithm concerning the optimal solution. Besides, experiments are carried out that show that the success of a given strategy varies, depending on the function that determines the cost of each vertex. In particular, we investigate the cost function implicitly used in previous work in the area we call uniform cost (that is, all vertices have a cost of 1) and a cost function that assigns costs according to the degree of the vertices, called degree penalty. We show that, although the strategies with good performance in these two cases are very different from each other, both correlate well with simple strategies of measures of centrality. Keywords: Influence Blocking Maximization, Information Spread, Misinformation.