Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
复制标题
不可逆的 k 阈值过程：疾病和观点传播的图论阈值模型
DOI：
10.1016/j.dam.2008.09.012
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
F. Roberts
中科院分区：
文献类型：
--
作者：
Paul A. Dreyer;F. Roberts
我们将考虑通过社会网络传播疾病或观点的模型，用图形表示。在我们的模型中，顶点将处于两种状态之一，1（“感染”）或0（“未感染”），状态的变化将在离散时间发生。在描述了几个这样的模型之后，我们将集中在一个称为不可逆k阈值过程的模型上，如果一个顶点的邻居中至少有k个处于状态1，那么它就会进入状态1，并且一个顶点一旦进入状态1就不会离开状态1。我们将寻找具有如下属性的顶点集合，如果它们一开始处于状态1，那么最终所有顶点都会处于状态1。这样的顶点集对应于可以感染某种疾病或观点的顶点，从而保证感染该疾病或观点的人群达到饱和。我们还将讨论“防御”这种饱和集的方法，例如通过“接种”或设计网络拓扑。
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.