模型检测网络传播的策略范文

本站小编为你精心准备了模型检测网络传播的策略参考范文，愿这些范文能点燃您思维的火花，激发您的写作灵感。欢迎深入阅读并收藏。

1.网络传播模型与干预策略问题

网络是由大量个体通过相互作用或者联系构成的有机整体。现实世界中存在大量这样的网络，比如由计算机、人或者森林构成的网络，其中的个体状态随着邻接点的影响而发生动态改变。网络以及其中个体间的相互作用可以形式化地通过图表示。假设G(V,E)是一个图，顶点集1{...}nV=vv表示网络中的个体，边的集合E表示能够导致传播的个体间的连接。每个顶点iv∈v有一个与之对应的状态()iσv，取值为“感染”（infected）或者“易感“（open）。对图中每个顶点定义一个由邻接点构成的集合(){|(,)}ijijρv=v∈Vvv∈E。节点iv的状态变化由邻接点的状态以及iv当前的状态决定，用传递函数f描述[1]。同时，采用局部更新函数g描述节点iv感染后受其自身影响所产生的状态变化[1]。一般来说，根据节点感染后能否重新恢复成易感状态，我们可以将其分为两类：（1）不可恢复和（2）可恢复。以人类的某些传染疾病例，有些疾病凭借着人自身的免疫力，经过一段时间可自愈，这就是可恢复情形。但也有部分疾病无法自愈，这就是不可恢复情形。对于不可恢复情形，具体来讲，节点iv由易感状态变为感染状态的条件是至少需要它的邻接点中有k个是感染的，对应的函数f定义如下：而在不可恢复情形中，由于感染的节点可以恢复，即经过一段时间（比如r）,感染节点的状态变为易感，所以需要记录节点感染时间长度,用infectedk表示一个节点已经被感染了k个时刻，那么初始感染的状态即为infected1，对应的函数定义如下：以上所描述的是未采取干预策略的网络传播模型。为了描述干预策略对传播模型的影响，对节点增加“保护”状态（protected）。被保护的节点将一直保持保护状态，因此不会被感染和用于传播。干预策略的基本思想是通过对部分易感节点进行保护，隔离其它未保护的易感节点和感染节点，实现对网络传播的控制。如果干预策略能将感染节点的数量控制在给定的范围内，则称其是有效的。干预策略通常受到各种因素制约，例如被保护节点数量，实施节点保护的时机等。本文研究不同的网络传播类型，根据给定的目标和资源判断并找出有效的保护策略。根据实施方式的不同，干预策略问题可以分为两类：（1）静态保护问题和（2）动态保护问题。在静态保护问题中，对于易感节点的选择和保护在初始时刻一次性完成，即对于给定结构的传播模型要求在t=0时刻从易感节点中随机选取固定数目(比如m个)的节点进行保护，使得最终感染节点的数量不超过预定的数目。另一方面在现实世界中，由于受运输或保护资源数量等限制，无法一次性保护大量的节点，而只能通过每次保护部分节点，采取分批次方式实施保护，这就是动态保护问题，比如消防员问题。动态保护问题要求在t=0时刻，从易感节点中随机选取数量不多于固定值d的节点进行保护，在随后的各个时刻，即t=1，2，…，当节点的状态完成更新后，不断重复选择和保护节点的过程，直到网络中没有新的节点被感染，使得在整个过程中感染的节点数量控制在给定数目内。与网络传播模型相对应，根据节点感染后能否恢复为易感染状态,即g函数类型的不同，静态保护和动态保护问题又都可以分为不可恢复和可恢复两种情形。其中，可恢复情形由于g不再是单调函数，因此取决于节点被感染的速率和感染节点恢复的速率，感染节点的数量可能增加也可能减少：如果节点被感染节点的速率大于恢复速率，则感染节点的数量增加；否则，感染节点数量减少。所以这种情况下的干预策略问题更为复杂。综上所述，可以将网络传播中的干预策略问题分为四类：（1）不可恢复的静态保护问题(staticunrecoverableproblem)、（2）可恢复的静态保护问题(staticrecoverableproblem)、（3）不可恢复的动态保护问题(dynamicunrecoverableproblem)以及（4）可恢复的动态保护问题(dynamicrecoverableproblem)。由于可恢复的动态保护问题最为复杂，接下来我们以图1为例对其做相关说明。假设传递函数f中k为1，即当前易感染节点只要存在一个感染状态的邻接点，下一时刻它必被感染。另外设g函数中r为1，即经过一个时间感染节点恢复到易感状态。初始网络中只有节点0和2被感染（黑色实心圆），d为1，即每次只能保护1个易感节点。干预策略的目标是将感染节点的数量控制在2以内。可以找到这样一种可行的干预策略：在t=0时刻，保护节点5（灰色实心圆）。t=1时刻，节点1和3根据f函数被感染，而节点2和4根据g函数恢复为易感状态，这时感染节点的数量还是2；在t=2时刻，继续保护节点4；在t=3时刻，节点0和2被感染，节点1和3恢复为感染状态。此后网络中没有新的节点被感染，可以停止保护；在整个过程中，感染节点的数量始终不超过2，因此这是一种有效的干预策略。

2.基于模型检测的干预策略问题分析

模型检测作为一种成熟的自动验证技术，已被广泛用于计算机硬件、通信协议和航空电子等领域。其基本思想是通过对系统的状态空间的穷举搜索，来判断采用时序逻辑所描述的待验证的行为属性是否成立，并且当属性不成立时，提供反例说明。另一方面，对于网络传播中的干预策略问题,由于其本质上需要考虑所有可能的干预组合来判断其是否有效，这与模型检测的思想相吻合。因此可以考虑采用模型检测方法来解决干预策略问题。基本思路是：采用状态迁移系统来描述由于传播造成的网络节点的状态变化，同时将干预策略的控制目标用时序逻辑描述，然后采用模型检测方法判断并找出有效的干预策略。由于模型检测已经在实际中获得广泛应用，因此我们期望可以借助成功的模型检测技术来解决网络传播干预策略问题。

2.1模型检测工具实际中开发了很多模型检测器，NuSMV和SPIN就是其中应用最为广泛的两种。它们代表了模型检测的两种不同理念，即符号化计算和显式的状态搜索。

2.1.1NuSMVNuSMV是一个针对有限状态系统的符号化验证工具,其基本思想是用二叉决策图（BDD）表示布尔公式，进而用布尔逻辑公式表示迁移关系和状态集合，能够降低模型检测所使用的存储空间，解决状态空间爆炸问题。NuSMV能够验证多种时序逻辑公式表达的性质，如CTL和LTL等，在电路设计和安全协议的验证方面得到广泛应用。

2.1.2SPINSPIN采用自动机表示模型，主要针对由LTL时序公式表达的属性。它采用了on-the-fly技术，不需要构建一个完整的状态空间，而是根据属性动态展开搜索路径的状态。SPIN采用了多重优化技术，比如偏序规约以及状态压缩等。这些优化使SP其具有极高的检测效率和较低的内存需求。它以进程作为建模的基本单位，模型中的多个进程之间可以交错并发，更加适合对并发系统的验证。

2.2干预策略问题分析采用图对网络传播进行建模是一种直观有效的方法。图中的节点对应于网络中的实体。图中的边对应网络中的连接关系。图中每个节点添加一个状态，即感染状态（infected），或者易感状态（open）或者保护状态（protected）。这样通过图就可以表示出对应网络的整体状态。根据传递函数f和局部更新函数g，不同时刻图中节点对应的状态会发生变化。虽然图的拓扑结构未改变，但由于节点状态的变化，图的整体状态也发生了变化。为了避免和节点的状态混淆，在本文我们用“形态”表示图的整体状态。图随着时间的形态变化构成了网络传播的形态迁移系统。第1节中所提出的四类问题可以通过分析网络传播所对应的形态迁移系统，将干预策略目标采用对应的网络形态来刻画，通过检测所期望的形态是否可以到达来判断是否存在有效干预策略。为了验证是否存在从某个初始形态出发能够到达期望的形态，需要考虑所有可能的初始形态。为了利用模型检测方法来解决这个问题，最重要的是将干预策略作用下的网络传播的形态迁移系统转化为模型检测所需要的状态迁移系统。其基本方法是将传播模型的初始形态定义为模型检测中状态迁移系统的状态，并且进一步将传播模型形态间的迁移通过状态迁移表示出来;这样就可以模拟从所有初始形态开始的形态迁移变化；然后采用时序逻辑表示出目标，从而可利用模型检测进行分析验证。

2.2.1网络干预问题的形态迁移模型网络干预问题的模型可以用Kripke结构表示。定义1：设错误！不能通过编辑域代码创建对象。是一个原子命题集合。AP上的Kripke结构是一个四元组0M=(S,S,T,L)，其中：与静态问题不同，动态保护问题中由于对节点的选取和保护与传播过程交替进行，所以相应的Kripke结构更复杂。状态集合0S对应于初始网络形态，即初始感染节点的集合，所以。整个建模过程集中于迁移关系上，它不是单纯与传递函数f和局部更新函数g有关，而是分为选取保护节点和网络传播两个过程，即将选取保护节点作为迁移关系的一部分来定义。选取保护节点，即选择不多于固定数量（比如d个）的节点进行保护

2.2.2干预策略问题的LTL描述建立了上述模型之后，需要给出干预策略问题所对应的行为属性描述。我们用LTL属性表示相应的四类干预策略问题。LTL是一种线性时态逻辑，用于描述与模型中所有可能的路径集合所对应的行为属性。LTL公式由表示时序的连接词组成，例如F，U，G等。其中F连接词表示“未来某个状态”，G连接词表示“所有未来状态”。另外LTL还会出现一些组合连接词，例如GF组合表示”在每一个路径上，某个状态能够无限多次出现“，而FG则表示”一个特定过程最终会被永久保持“。接下来探讨如何使用时序公式表示本文的四类问题。我们首先介绍文献对于静态保护问题的分析,然后介绍我们所提出的对于动态保护问题的分析。为了便于描述，我们用total表示当前感染节点的总数量，maxaffectedNum表示最大允许感染的节点数量。在不可恢复的静态保护问题中，由于节点被感染后不能恢复，所以total是单调非递减的。为了能够找到一个使感染节点数量控制在maxaffectedNum之内的干预策略,使用LTL公式φ:F(total>maxaffectedNum);如果系统满足φ，则对于系统中的所有路径，最终都将达到一个使得total>maxaffectedNum成立的状态,即对于给定的初始条件，不存在有效的干预策略。反之，则意味着存在某条满足初始条件的路径，并且total≤maxaffectedNum在该路径上一直满足，即路径上的所有状态都满足total≤maxaffectedNum；在这种情况下，模型检测器将返回相应的初始状态)(),...,(ins=〈σvσv〉，从中可得到对应的干预策略。另一方面，在可恢复的静态保护问题中，由于节点被感染后又会恢复到易感状态，所以total可能不是单调非递增的。为了达到将感染节点数量控制在maxaffectedNum之内的目的，策略制定者需要设法使感染节点的数量最终达到一种“平稳态”，即经过一段时间后，感染节点的数量总是能够控制在maxaffectedNum之内。为此，可采用LTL公式φ'''':GF(total>maxaffectedNum)来描述。如果系统满足φ'''',也就是说从所有初始路径出发，total>maxaffectedNum将反复出现。反之，则表示存在某条路径满足FG(total≤maxaffectedNum)，即存在某条路径，从某个时刻开始满足“平稳态”且一直满足total≤maxaffectedNum;相应地，从反例的初始状态可以推出对应的有效干预策略。动态保护问题属性描述更为复杂，这主要是因为模型中需要添加是否继续保护易感节点的判断。当传播过程中感染节点的数量不再增加时，也就是说不会有新的节点被感染，此时停止保护节点，感染节点数量达到最大值，只需判断total是否大于maxaffectedNum即可。为此，我们定义一个变量newNodeInfected作为停止保护的标识，初始为TRUE，当它变为FALSE时，停止保护节点。因此，问题的时序属性描述为ψ:G((newNodeInfected=FALSE)→(total>maxaffectedNum))。若上述公式ψ成立，则从系统的所有路径出发，到达停止保护状态时，total>maxaffectedNum成立，亦即不存在有效的干预策略。反之，如果公式ψ不成立，则表示存在某条路径，到达停止时刻时，total≤maxaffectedNum并将一直持续下去，即对于某条路径，从停止保护时刻开始，之后所有的状态均满足total≤maxaffectedNum，从反例的状态数组能够分析出每次采取的干预策略。

对于可恢复的动态问题，由于感染的节点经过一段时间可以恢复到易感状态，即相应的局部更新函数g不是单调函数，所以total也不一定是单调非递减的，其值可能会时高时低，这取决于感染和恢复的速率。所以停止保护时，感染节点数量不一定对应于最大值，因此按照上述ψ中以此时的total来衡量是否大于maxaffectedNum是不恰当的，这时需要衡量模型未来时刻属性的时序连接词。与静态恢复的情况类似，我们也希望达到相应的“平稳态”，因此可以采用时序逻辑公式ψ'''':G((newNodeInfected=FALSE)→GF(total>maxaffectedNum))。如果上述公式ψ''''成立，即表示在停止保护后total>maxaffectedNum不断反复出现。反之，则表示存在某条路径，停止保护后的某个时刻开始，之后能够达到“平稳态”，即total≤maxaffectedNum一直持续下去，从反例中可以逐步推出对应的干预策略，即找出变为保护状态的节点。

3.问题分析建模

在这一节我们分别针对上述四类问题，给出采用NuSMV和SPIN寻找有效的干预策略的分析模型。为了便于说明，我们将传播模型中f函数的参数k设为1，可恢复情况下的g函数中r参数设为2。为了便于描述，下文用protectedNum表示需要保护的节点数量，maxaffectedNum表示系统允许的最大感染节点的数量，N表示节点的总数量，变量total表示任意时间被感染节点的总数量,数组s[N]表示网络中所有个体的状态。

3.1不可恢复的静态保护问题NuSMV：使用NuSMV解决此类问题时,首先需要考虑的是将节点的状态通过映射反映到采用NuSMV语言所描述的验证模型中。这可以通过采用枚举方式进行定义,比如将节点状态映射到整数上，感染状态对应于整数1，保护状态对应于-1，易感状态对应于0。NuSMV程序主要分为两部分：初始化部分和迁移变化部分。初始化部分主要完成系统的初始环境赋值。迁移变化过程则是表示所有变量的状态迁移及其变量间的相互关系。我们的初始化部分主要完成对感染节点的初始表示和保护节点的选择。根据映射，将节点的初始状态赋对应的值即可。然后重点是对传播过程中节点的迁移变化进行描述。节点的状态变化由f函数以及对应的邻接点决定。对应的验证模型则需要用状态变量的变化，即用next语句表示出节点状态的变化过程。根据我们的模型，对应于每个状态为0的节点v，如果存在状态为1的邻接点，则它的状态由0变为1，其它情况下它的状态保持不变。SPIN：使用SPIN解决此类问题的重点是选取保护节点。选取节点进行保护可以利用一个do循环实现，每次选取一个节点进行保护；当被保护的节点数目达到protectedNum时即终止循环。这可以采用SPIN中条件结构的不确定性(non-deterministic)来实现。我们可以采用非负整数，比如2表示保护状态。对应的程序如下所示，其中SelectNum表示当前选择的保护节点数量。

3.2可恢复的静态保护问题NuSMV：此类问题的NuSMV模型的建模思路与上述不可恢复问题的NuSMV模型相同。但根据局部更新函数g，感染状态可细分为infected1，infected2，..，infectedr-1，并且在状态infectedr-1后恢复为open状态。在本文的实验中，我们将r取3，并在模型中分别采用1和2表示infected1和infected2。这样感染后的节点的下一状态会有1-2,2->0的变迁，分别表示SPIN：此类问题建模思路类似不可恢复情形的SPIN建模，所以不再介绍。

3.3不可恢复的动态保护问题NuSMV：动态问题属于动态规划问题，因此验证模型较两类静态保护问题复杂，并且由于NuSMV语言的特性给建立模型带来了困扰。对于动态保护问题，采用NuSMV建立模型有如下难点：(i)如何表示可供选择的易感节点的集合(ii)判断何时停止选取节点进行保护(iii)如何表示选取保护节点与网络传播两个过程的交替进行由于不断有节点被感染和被选择保护，所以易感节点的集合是动态变化的。如何表示易感节点的集合是NuSMV程序的第一个难点。为此，我们采用如下的策略：如果节点状态为易感状态，则返回节点标号，否则返回空集。由于NuSMV语言本身没有设置空集概念，所以另外设值（比如-1）代替。接着使用内置union函数，将易感节点标号连接成一个集合。这样就得到了供选择的易感节点的集合，并且它是动态变化的。对于静态问题，由于保护节点只是在初始时刻实施，故仅在初始化部分即可完成相应的干预策略表示。动态问题的选取节点过程则是不断重复的，所以只能在迁移变化过程中表示。另一方面，由于NuSMV没有随机集合的类型，故一次选择保护节点过程中同时选择多个节点比较困难，所以我们分多步进行，即每步选择一个节点进行保护，用Turnprotected表示这样的步数。为了表示每步选取的易感节点的编号，模型定义了selector变量。selector可以是供选择的易感节点标号集合中的一个随机数。如果网络中没有新的节点被感染，这时再投入保护资源显然是没有意义的。为了避免保护资源的浪费，需要对停止保护的时刻进行判定。为此模型中设置一个结束保护的标识变量newNodeInfected。它初始为TRUE，只有当没有易感节点候选或者在传播过程没有新的节点被感染，newNodeInfected才变为FALSE。当此变量发生变化时，我们就停止对节点的保护。next(newNodeInfected):=case(total=Turnprotected*turn&(next(affectedNum)-affectedNum=0))|(total+affectedNum=N):FALSE;TRUE:newNodeInfected;esac;动态问题的状态迁移变化分为两部分：选取保护节点和传播变化过程，并且这两个过程交替进行，我们用turn变量来表示选取节点过程执行的次数。选择节点过程中只有当selector的值等于节点标号时，当前节点才能被变更为保护状态。当选取节点过程中选择的节点数量达到Turnprotected*turn或者无易感节点可被保护时，执行传播过程。假设传播网络中节点0只与节点1,3相邻，下面的程序是以节点0为例的迁移变化过程。SPIN：动态问题与静态问题不同之处是添加了不断重复选取节点和传播的过程，直到不再进行保护。我们为此添加变量PreAffectednodeNum用来表示前一时刻感染节点的总数量。如果程序前后两个时刻感染节点的总数量未发生变化即PreAffectednodeNum==AffectednodeNum，则终止。

3.4可恢复的动态保护问题NuSMV：此类问题的NuSMV模型类似不可恢复的动态保护问题的NuSMV模型，只是在一些地方有修改，比如不能继续用感染节点数量不增加作为停止保护的条件。这是动态保护问题与静态保护问题的最大不同点，也是设计模型的最大难点。感染节点数量不增加并不表示没有新的节点被感染。当感染和恢复同时存在且两者的速率相同，就会造成total不变化，但这并不意味着感染不会扩散到新节点以及之后不会造成大范围的扩散。对此，我们的思路是比较前后两个时刻曾经感染过的节点数量。若不相等，继续保护节点；否则，停止保护。SPIN：结合此类问题的NuSMV建模思路即可完成对应的建模。

4.实验结果与分析

我们选用随机和NW小世界网络两种拓扑结构的网络进行实验。由于问题的复杂性，选用的随机网络规定每个节点的度不大于5。动态保护问题由于干预模型足够复杂，限定随机网络中每个节点的度不大于4。小世界网络是一类特殊的复杂网络结构，在这种网络中大部份的节点彼此并不相连，但绝大部份节点之间经过少数几步就可到达。在社会关系网络、互联网络、生物工程等众多领域，小世界网络得到了广泛的应用。NW小世界网络是一种改进了的小世界网络模型，它避免了产生孤立点的可能。实验的NW小世界网络选取K=1，P=0.1表示构造环状规则网络时每个节点与它最邻近的K个节点各连出1条边接。P表示以概率P在随机选取的一对节点之间加上一条边。我们按一定规律（如节点个数增加）产生一系列系列数据并分别进行实验。这样就能很大程度上反映随着节点数增加，模型检测器所消耗的最大内存和CPU时间的一般性规律。为了提高实验的准确性，本文对所总结的每一类问题都产生四组数据并分别实验。鉴于篇幅原因，我们仅列出部分实验数据。此外实验采用2.5.4版本的NuSMV和6.2.3版本的SPIN，在Inteli52.5GHz处理器以及32位ubuntu平台进行。

4.1随机网络实验结果不可恢复的静态保护问题：图2为静态不可恢复问题的实验数据对应的趋势图。图中间断点表示NuSMV超时或者SPIN内存超出。实验中设置系统允许的最长运行时间为2小时及最大可用内存为3G。另外图表中出现的运行时间均为CPU时间。从实验结果我们得到了如下的基本结论：对于不可恢复的静态保护问题，SPIN需要的运行时间明显小于NuSMV，使用的最大内存大于NuSMV。另外在最坏情况下，即对于给定问题不存在有效的干预策略时，SPIN需要的最大内存可能出现超出范围的情况。比如图2在节点数为45时，SPIN的内存可达到3G以上，无法完全搜索。对于这种情况可通过状态压缩技术进行处理，这时的最大内存略小于NuSMV，但运行时间则超过了NuSMV。可恢复的静态保护问题：由于两类静态问题的实验结果大致相同，所以此类问题的实验数据及结论不再重复。不可恢复的动态保护问题：不可恢复的动态问题的实验结果对应于图3。存在有效的干预策略情况下，SPIN较NuSMV运行时间少，需要的最大内存较多，但运行时间和需要的最大内存波动较小；NuSMV随着节点的增大，在运行时间和需要的最大内存上都存在较大波动，虽然有时随着节点数的增加需要的最大内存反而减少，但是运行时间可能在最某点急剧增大。最坏情况下，SPIN内存消耗巨大，例如图3中的节点数为20时，SPIN需要的最大内存急剧增加。可恢复的动态保护问题：表1是可恢复的动态保护问题的数据。表中“—”表示NuSMV超时或者SPIN内存超出。它的变化趋势基本和静态问题相同。但实验中NuSMV出现了较多的超时现象，例如表1中NuSMV在节点数为13,14,15时均超时。

4.2小世界网络实验结果小世界网络的分析问题比随机网络的情况更为复杂；即使是随机连接概率较小（比如0.1）的小世界也可能具有复杂的网络结构并且包含许多连接度较大的节点。表2是小世界网络的静态不可恢复问题的实验结果。小世界问题中的运行时间和内存使用趋势基本与随机网络的情况一致。但NuSMV在节点个数大于35之后，运行超时。SPIN在节点个数35之后，内存超出了范围。小世界的其他问题虽然运行时间或内存更大，但结论和随机网络基本相同，所以不再重复。

4.3实验结果分析产生上述现象的原因与两种模型检测器的原理有关。一方面，NuSMV采用高效的BDD结构表示状态及迁移关系，可以极大地减少内存的使用量；另一方面，SPIN采用动态搜索的方式，只需要构造部分路径就可以开始搜索，只有当前的路径没有找到反例，才需构造新的路径，而一旦找到反例就停止搜索，这样很大可能不需要构造整个状态空间。据实验观察，NuSMV构造整个状态空间的BDD图所花的时间占运行时间的50%以上。为了解决时间超时或者内存超出问题，最根本的方法是采用抽象方法对网络进行化简。具体地，可以根据网络的特征，将一些节点进行合并，这样就能在一定程度上降低网络的规模，从而提高模型检测的效率。

5.相关工作

网络传播问题一直是数学、物理和计算机领域共同关注的焦点。众多学者对控制网络传播做了大量的研究，其目标都是通过对部分个体进行保护而有效地控制传播。部分工作研究在感染爆发之前如何采取防护措施，比如随机免疫,目标免疫等。随机免疫是完全随机地选取网络中的一部分节点进行免疫。很容易看出，它的效率比较低下，代价较大。目标免疫是根据网络特性，选取少量度值较大的点进行免疫。网络结构已知的情况下，目标免疫的效果远远好于随机免疫。文献论证了目标免疫措施能够有效地控制有害传播。另外，大量研究工作关注的是在感染已存在情况下所采取的干预策略。上文提到的消防员问题及其变种是这样一类问题。很多文献针对的是特定结构网络的消防员问题,比如网格结构的消防员问题和树结构的消防员问题。文献考虑的是消防员问题的较一般情形，即每个时刻投入的消防员数量大于1。与上述众多研究不同，本文考虑的是通过模型检测方法找出一种有效的干预策略。我们研究的是更一般的情形，不仅网络结构更为复杂，而且考虑了着火点和消防员数量多个的情况。不仅如此，本文还同时考虑了更为复杂的感染节点可恢复情形。状态爆炸是限制模型检测在实际应用中发展的一个重要问题。上述的实验中出现的超时或者超出内存都是状态爆炸的表现。针对大规模传播模型，文献提出了的两种解决状态爆炸的机制。第一种减少机制旨在减少不必要的状态变化。比如感染节点之间的相互影响是不可以忽略的，可以删除这部分状态迁移。第二种机制针对的是有向传播的网络。根据距离将图中的易感节点进行有效的等价类划分。这样一定程度减少了网络中节点的个数，降低了模型的复杂度。

6.总结

通过保护个体进而破坏网络结构的连通性是控制网络传播的一种的干预策略。本文在已有的静态保护问题工作的基础上，针对感染节点不可恢复与可恢复两种情形总结了四类干预策略问题，并且重点分析了多次保护节点的动态保护问题。给出了这四类问题对应的形式化模型及相关的时序逻辑描述方法，通过模型检测方法找出有效的干预策略。最后，使用NuSMV和SPIN两种模型检测工具对四类问题建模和验证。实验采用了随机和小世界两种网络，依据实验结果分析了NuSMV和SPIN两种模型检测器在具体问题中的优缺点。本文考虑了一种受时间和邻接点影响的简单的网络传播模型。但从实验结果可以看出，随着问题规模的增加，模型检测所花的时间或内存空间较大。实验中当节点的度或节点数增加到一定程度时，极易造成状态的爆炸式增长，最终由于时间或者内存的限制，模型检测器无法正常解决问题。因此，若能根据传播网络的结构特征，将模型检测的对称化简和组合化简思想应用到文中提到的问题上，并结合文献中提出的两种机制，有可能实现具有针对性的解决状态爆炸的方法，在提高模型检测的效率的同时也能使模型检测应用到大规模的传播网络问题中。现实世界中的传播模型掺杂着概率因素。文献中建立了离散的邮件病毒传播模型，其中病毒在相邻节点之间传播和节点被感染是有一定概率的。文献应用概率模型检测方法对生化网络进行了分析。类似地，将概率模型检测方法应用到网络干预问题中，将是一个十分有意义的问题。

作者：余鹏魏欧 韩兰胜牛耘单位：苏州大学凤凰传媒学院