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

Paul A. Dreyer, Fred S. Roberts

Research output: Contribution to journalArticlepeer-review

141 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1615-1627
Number of pages13
JournalDiscrete Applied Mathematics
Volume157
Issue number7
DOIs
StatePublished - Apr 6 2009

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Firefighter problem
  • Social network
  • Spread of disease
  • Spread of opinion
  • Threshold models

Fingerprint

Dive into the research topics of 'Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion'. Together they form a unique fingerprint.

Cite this