基于元胞自动机的改进流言模型
(系统工程课程论文)
姓名:高寒冰
学号:1210503
专业:管理科学与工程
中国人民解放军后勤工程学院
二〇一三年一月
基于元胞自动机的改进流言模型
1.引言
流言的传播是一个典型的社会现象。流言的传播是由相信者将流言传播给非相信者,非相信者转变为相信者,将流言传播给其他非相信者的过程。在模拟流言传播过程时,对于模型中每一个人我们需要考虑四个问题:一是流言是否由相信者传播给非相信者?二是非相信者是否相信流言?三是相信者是否遗忘流言?四是周围环境的影响?
现有的流言模型大多数是基于元胞自动机的原理建立的,主要有四个流言模型,分别是:基本的流言模型、概率规则的流言模型、带遗忘的流言模型以及多数流言模型。在基本的流言模型中,假定相信者一定向周围的人传播流言,且所有传入流言者,一定相信流言且传出流言。在概率规则的流言模型中,将相信者一定向周围的人传播流言,改变为相信者按一定概率向周围的人传播流言。而在带遗忘流言模型中不仅考虑了相信者按一定概率向周围的人传播流言,而且考虑了存在一定的概率相信者遗忘流言,转变为非相信者。多数模型主要考虑了周围环境对相信者或者非相信者的影响。笔者认为以上四个模型都在一定程度上模拟了流言的传播过程,但并没有完全解决上文中提到的四个问题。在四个模型的基础上,笔者提出了一个改进流言模型,具体的规则有以下四点:一、认为基于相信者的类型不同,流言传播的效率不同。二、认为非相信者相信流言是服从一定概率的。三、认为相信者遗忘流言是服从一定的概率。四、因为考虑到人是社会动物,都或多或少受到外界环境的影响,所以在流言传播过程中,认为周围人对流言的态度确实对流言的传播产生了影响。另外,考虑到了流言的属性,如流言的类型和置信度对流言传播的影响。将流言的类型分为过失流言和蓄意流言,过失流言只有一个传播源,而蓄意流言有多个传播源,并设置了流言的置信度。表1将笔者建立的改进模型与现有的四个流言模型做了比较。
表1改进模型与现有模型的对比
2.元胞自动机
元胞自动机是一种空间、时间、状态完全离散的非线性系统模型。它有简单的演化规则确定,能在较大程度上模拟复杂的系统。正是鉴于元胞自动机对复杂系统的建模能力,在流言传播研究领域,我们多采用元胞自动机来模拟流言传播的过程。元胞自动机可以定义为如下四元组:
()f T S
,
=
A,
,
Ld
其中,A表示一个元胞自动机系统,Ld表示d维的元胞空间,d为正整数,
是元胞状态的离散有限集,N 表示单个元胞的邻域内元胞状态的组合(包括中心的元胞),表示将N S 映射到S 上的一个局部转换函数,演化规则可表示为
()
()1,1,,1
,+-∈=+i i r S f S t
v r t j i 且()1,1+-∈j j v
其中,1+t i S 为第i 个元胞在1+t 时刻的状态,t v r S ,为所有邻元的集合。
3.建模
流言模型构架如下:
(1)元胞及元胞空间(Ld ):
每个人为一个元胞。假设用n n N ?=的二维网格来表示该空间的所有人群,则其中每个格点代表一个人,
即一个元胞。 (2)状态(S ):状态S 表示对待流言的态度,1=S 表示此人相信流言,即此人是流言的相信者;0=C 流言,即此人是流言的非相信者。
(3):邻居(T ):邻居半径为1的more 型(见图1),其 中灰色部分代表一个元胞和他的八个邻居。
(4):转换规则(f ):不同的流言模型转换规则不同。 1)基本的流言模型的转换规则
假设1,+t j i S 的邻居矩阵为()()()()j i j j i i M ,1,1,1,1-+-+-=。
()
()M v r S f S t
v r t j i ∈==+,,1,11
,,1
,+t j i S 表示第i 列、第j 列个元胞, 1+t 时刻的状
态。且该式在
∑∑+-=+-=≠111
1
,0i i r j j v t
v
r S
,即t v r S ,只要有一个为1,则11
,=+t j i S 。
2)设流言的传播概率为5.0,概率的流言模型的转换规则
()
()M v r S f S t
v r t j i ∈==+,,1,21
,,满足且
∑∑+-=+-=≠1
11
1
,0i i r j j v t v
r S
()5.0>x rand ,其中[]1,0∈x ,()x rand 表示取0和1间的随机数。
3)又设流言遗忘概率为1.0,则带遗忘的流言模型的转换规则:
()
()M v r S f S t
v r t j i ∈==+,,1,31
,
..t s ()[]
?????∈<=1,0,5.00,x x rand S t
j i
或01,=+t j i S
图1 more 型领域
..t s ()[]
????
?∈<=1,0,1.01
,x x rand S t j i 4)我们假设一个元胞为相信者,如果它的邻居中有大于4个为非相信者,
则该元胞转变为非相信者,否则保持不变。若一个元胞为非相信者,如果它的邻居中有大于4个为相信者,则该元胞转变为相信者,否则保持不变。据此,可以列出多数模型的转换规则:
()
()M v r S f S t
v r t j i ∈==+,,1,41
,
..t s ???
??>=∑∑+-=+-=111
1
,,40i i r j j v t
v r t j i S S 或()()M v r S f S t v r t j i ∈==+,,0,41,
..t s ???
??<=∑∑+-=+-=111
1
,,41i i r j j v t
v r t j i S S 5)在改进流言模型中,因为考虑了比较多的因素,所以它的转换规则也相对复杂一些。
首先,我们考虑人们对不同的流言相信程度不同,通常情况下将流言的置信度l 取为5.0。
其次,相信者传播流言的效率是不同的,我们认为人群中有积极的流言传播者、普通的流言传播者以及消极的流言传播者,假设积极的流言传播者效率为1,普通的流言传播者效率为5.0,消极的流言传播者效率为0,通常情况下,我们认为人群中积极的流言传播者、普通的流言传播者、消极的流言传播者的比例为2.0:6.0:2.0,则流言传播的效率5.05.06.012.0=?+?=w 。
再次在考虑相信流言的概率时,我们借鉴了部分概率的流言模型的思想,但是并不认为某元胞相信流言的概率是固定的,而是认为这一概率和向该元胞传播流言的元胞数成正相关,我们假设相信流言的概率()8/r r U =,r 为向该元胞传播流言的元胞数(注意向传播流言给该元胞的邻居数与该元胞中邻居中相信者数不同,因为考虑了相信者的类型,有写相信者相信流言但不会传播流言)。
最后在考虑遗忘流言的概率时,我们借鉴了部分带遗忘的流言模型的思想,但同样我们不认为某元胞遗忘流言的概率是固定的,而是认为这一概率和周围非相信者的数目成正相关,我们假设遗忘流言的概率()8/k k P =,k 为该元胞邻居中非相信者的数目。
另外为了更好的表达改进的流言模型的转换规则,我们引入一个新的函数
()??
?≥<=t
s t
s t s R ,0,1,
据此,可以列出改进的流言模型的转换规则:
()
()M v r S f S t
v r t j i ∈==+,,1,51
,
..t s ()()()??
??
??<=∑∑+-=+-=111
1
,,8
/25.0,0i i r j j v t v
r t j i y rand R S
x rand S
其中25.0为流言的置信度和流言传播效率的乘积,()()25.0,,y rand R S t v r ?表示
第i 列、第j 列个元胞, t 时刻传播流言给邻居的概率,()()
∑∑+-=+-=?1
11
1
,25.0,i i r j j v t v
r y rand R S
表示传播流言给该元胞的邻居个数。
或()()M v r S f S t v r t j i ∈==+,,0,51,
..t s ()??
??
????
?
?
?-<=∑∑+-=+-=5/8/81
111
1
,,i i r j j v t v
r t j i S
x rand S 其中∑∑+-=+-=-
1
11
1
,8i i r j j v t v
r S 表示该邻居中非相信者数。
多除一个5是为了降低遗忘率,方便运算。
4.模型的模拟及分析
令5050?=N 的二维空间,利用Matlab 软件编程求解,得到以下结果。
4.1流言模型的传播图
(1)基本的流言模型传播图
其中深色表示非相信者,浅色代表相信者(下同)。
t=21
(4)多数流言模型传播图
多数模型的流言模型传播与初始传播源m 的个数有关。 这表示初始传播源过少,流言没有传播开来。
这表示由于初始传播源少,流言只在一定范围内传播。
1200=m
t=21
t=21
t=21
这表示在初始传播源足够多的情况下,流言被传播开来。
(5)改进的流言模型传播图
假设流言的置信度l 取为5.0,流言传播者效率为5.0。
比较图8和图9,可以清晰地看出蓄意流言比过失流言具有更大的破坏性。
4.2改进模型与现有模型比较
图10反应了随着时间的推移,现有的四个模型相信人数的变化规律。其中“*”表示基本的流言模型,“.”表示概率的流言模型,“^”表示带遗忘的流言模型,“-”表示多数流言模型。对比基本的流言模型、概率的流言模型、带遗忘的流言模型,可以看出同一时刻,基本的流言模型中相信人数最多,概率的流言模型相信人数次之,而带遗忘的流言模型相信人数最少,这与实际是符合的。而多数模型可以反应流言传播到一定程度后的情况,却无法反应流言初始传播的情况。
图11反应了随着时间的推移,改进模型相信数的变化规律。对比图11和图10中的曲线,可以看出,改进模型的曲线较之四个现有模型的曲线有更好的凹凸性,能够反应出随着相信人数的增多,流言的传播速率加快的趋势。
t=1t=101 t=201
t=1t=101 t=201
4.3对改进模型的分析
我们给流言的置信度赋予不同的值,令置信度l 分别取6.0、5.0、4.0、3.0,得到相信人数随时间的变化如图12。
从图中我们可以看出,随着置信度的降低,流言传播的速率不断减小,当置信度小到一定程度,流言的传播就可以被忽略,这与实际是吻合的。
5.结论
(1)本文基于元胞自动机的原理,对现有的流言模型进行了改进和优化,得到了相对于现有的流言模型更能真实的反应流言传播的改进模型,并从理论和实际两方面证明了改进模型的优越性,说明对流言模型的改进和优化是合理和有效的。
(2)本文中的部分数据只是作为一个算例,(并没有查询实际的数据如积极
图10 现有四个流言模型相信人数随时间的变化 图11 改进流言模型相信人数随时间的变化
图12 不同的置信度下相信人数随时间的变化
流言传播者、普通流言传播者、消极流言传播者的比例),以后在实际的运用中,需要根据实际的情况作修正。
(3)本文所提出的改进模型,笔者认为有三个方面可以继续深化研究:一、并不是模拟一定要从头开始,可以通过一些中间变量来得出最后的结果。二、我们可以给改进模型增加一个消除流言因子,也就是在某种情况下,会采取一定的手段来控制流言的传播,这更符合实际的情况。三、因为不同的人交际程度不同,有的人可以联系很多人,那么他就可以向很多人传播流言;而另外一些人交际圈小,就只能向少数人传播流言。换句话说,并不是每个元胞的邻居都有8个,有的可能多于8个,或者有的少于8个。我们可以把图论的思想引入到流言模型中来解决这个问题。