Maximizing Influence Blocking with Competing Cascades using Integer Linear Programming

In the influence blocking maximization problem, we aim to minimize the spread of disinformation in a network. More specifically, given a set of nodes that initiate the spread of disinformation and an integer k, we must find k nodes in the network to serve as the starting point for competing (say, correct) information so that the misinformation spread is minimized. In this paper, we propose a version of the problem under a dissemination model derived from the Competitive Linear Threshold model. We present an integer linear programming formulation for the problem that, as far as we know, inaugurates the use of mathematical programming in dissemination problems with two competing cascades. We performed experiments to verify the quality of our formulation, evaluating the integrality gap and the scalability. Such results can serve as a baseline for future solutions using integer linear programming.