  While social networks are widely used as a media for information diffusion,
attackers can also strategically employ analytical tools, such as influence
maximization, to maximize the spread of adversarial content through the
networks. We investigate the problem of limiting the diffusion of negative
information by blocking nodes and edges in the network. We formulate the
interaction between the defender and the attacker as a Stackelberg game where
the defender first chooses a set of nodes to block and then the attacker
selects a set of seeds to spread negative information from. This yields an
extremely complex bi-level optimization problem, particularly since even the
standard influence measures are difficult to compute. Our approach is to
approximate the attacker's problem as the maximum node domination problem. To
solve this problem, we first develop a method based on integer programming
combined with constraint generation. Next, to improve scalability, we develop
an approximate solution method that represents the attacker's problem as an
integer program, and then combines relaxation with duality to yield an upper
bound on the defender's objective that can be computed using mixed integer
linear programming. Finally, we propose an even more scalable heuristic method
that prunes nodes from the consideration set based on their degree. Extensive
experiments demonstrate the efficacy of our approaches.
