Inhibiting the Diffusion of Contagions in Bi-Threshold Systems: Analytical and Experimental Results

We present a bi-threshold model of complex contagion in networks. In this model a node in a network can be in one of two states at any time step, and changes state if enough of its neighbors are in the opposite state, as determined by “up-threshold” and “down-threshold” parameters. This dynamical process models several types of social contagion processes, such as public health concerns and the spread of games on online networks. Motivated by recent literature calling for the investigation of peer pressure to reduce obesity, which can be viewed as a control problem of population dynamics, we focus on the computational complexity of finding critical sets of nodes, which are nodes that we choose to freeze in state 0 (a desirable state) in order to inhibit the spread of an undesirable state 1 in the network. We define a minimum-cost critical set problem and show that it is NP-complete for bi-threshold systems. We show that several versions of the problem can be approximated to within a factor of O(log n), where n is the number of nodes in the network. Using the ideas behind these approximations, we devise a heuristic, called the Maximum Contributor Heuristic (MCH), which can be used even when the diffusion model is probabilistic. We perform simulations with well-known networks from the literature and show that MCH outperforms the High Degree Heuristic by several orders of magnitude.