Minimizing Misinformation Profit in Social Networks

Abstract

The widespread and effective online social networks may cause misinformation to diffuse in the networks, which could lead to public panic and even serious economic consequences. The classical misinformation containment (MC) problem aims to select a small node set as positive seeds to compete against the misinformation and limit the influence of misinformation as much as possible, where the misinformation seed set is given. Most of the prior works concentrate on either minimizing the number of users infected by misinformation or maximizing the number of users protected by the positive cascade. That is, they only concentrate on optimizing the number of nodes. However, the interaction effects between nodes differ from user to user and the related profit obtained from interaction activities may also be different. This article proposes a novel problem, called profit minimization of misinformation (PMM), which is the first to analyze the profit of activity in the MC problem. Given a misinformation seed set, the PMM problem aims at selecting a node set satisfying the cardinality constraint to minimize the profit of edges starting from infected nodes but ending at infected or protected nodes. Based on the sandwich method, we design a data-dependent approximation scheme for the PMM problem. We approximate the upper and lower bounds of the objective in the equivalent problem by the reverse influence sampling technique. Our algorithm is verified on realistic data sets, which demonstrate the superiority of our method.