Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion

We will consider models of the spread of disease or opinion through social networks, represented as graphs. In our models, vertices will be in one of two states, I ("infected") or 0 ("uninfected") and change of state will take place at discrete times. After describing several such models, we will concentrate on the model, called an irreversible k-threshold process, where a vertex enters state 1 if at least k of its neighbors are in state 1, and where a vertex never leaves state 1 once it is in it. We will seek sets of vertices with the property that, if they are in state 1 at the beginning, then eventually all vertices end up in state 1. Such vertex sets correspond to vertices that can be infected with a disease or opinion so as to guarantee saturation of the population with the disease or opinion. We will also discuss ways to "defend" against such saturating sets, for example by "vaccination" or designing network topologies. (C) 2008 Elsevier B.V. All rights reserved.