TY - JOUR

T1 - Irreversible k-threshold processes

T2 - Graph-theoretical threshold models of the spread of disease and of opinion

AU - Dreyer, Paul A.

AU - Roberts, Fred S.

N1 - Funding Information:
The authors would like to thank the National Science Foundation for supporting this work through grants CCR 91-19999, BIR 94-12594, DBI 99-82983, SBR 97-09134, SES-92-11492 and EIA-02-05116 to Rutgers University.

PY - 2009/4/6

Y1 - 2009/4/6

N2 - 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, 1 ("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.

AB - 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, 1 ("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.

KW - Firefighter problem

KW - Social network

KW - Spread of disease

KW - Spread of opinion

KW - Threshold models

UR - http://www.scopus.com/inward/record.url?scp=61849177052&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=61849177052&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2008.09.012

DO - 10.1016/j.dam.2008.09.012

M3 - Article

AN - SCOPUS:61849177052

VL - 157

SP - 1615

EP - 1627

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 7

ER -