学会杯数模论文
关 键 词 :社交网络,信息传播,微分方程,传染病模型,龙格-库塔法 摘 要:
本文以各大社交网站的用户关系数据为基础,并着重研究了在新浪微博用 户之间的链接关系数据,通过合理估计,数据整理,概率平均等方法 得到所需各个参数。
我们构造了一个基于在线社交网络的信息传播模型。该模型考虑了节点和传播机理
的影响,结合复杂网络和传染病动力学理论,进一步建立了动力学演化方程组。该方程
组刻画了不同类型节点随着时间的演化关系,反映了传播动力学过程受到网络拓扑结构
和传播机理的影响。本文模拟了在线社交网络中的信息传播过程,并得出了使微博影响最大化的重要因子和最优方案。 关键词:传染病模型 推广节点 传播节点
一:问题重述:
微博,是一个基于用户关系的信息分享、传播以及获取平台;它的出现开辟了自媒体时代。时下很多信息是通过微博获取,短短140字可以传播非常多的信息。 随着微博的发展,微博营销也成为了很多企业进行宣传的一种手段。微博粉丝数量的多少、微博转发量和评论量是衡量一个微博好坏的重要标准。
一家公司想把自己的产品,通过一个100粉丝的账号,在3天内,传播给最多的受众。请查阅资料,建立数学模型,用最优方式实现。
二:问题分析
在微博传播过程中,公司推广账号发出微博后,其粉丝中会有一定部分转发或评论,而粉丝的粉丝也有可能转发或评论该微博。经过分析,我们认为,微博传播模型类似于传染病传播模型。
在SNS 网络中,一个人发布的消息会被其好友看到,并以一定的概率分享、传播。
同时,若其好友对其内容不感兴趣则成为“免疫者”且不会传播。本文把SNS 网络上的
用户定义为节点,个体之间的好友关系则可以抽象地用节点之间的边来表示,信息只沿 着边传播。
三:建立的模型
根据信息在SNS 网络中的传播规律,我们把网络中的节点分为三类:传播节点、未
感染节点、免疫节点。传播节点表示该节点接受了来自其邻居节点的信息,并具有传播
该信息的能力。未感染节点表示该节点没有接受过来自其邻居节点的信息,并有
机会接
受信息,即有概率被感染。免疫节点表示该节点已经接受了其邻居节点的信息,但是不
具有传播能力。节点在传播状态、未感染状态和免疫状态之间的转移不仅依赖于节点自
身的状态,还与它的邻居节点的状态相关,定义以下传播规则: 1) 如果一个传播节点与一个未感染节点接触,则未感染节点会以概率P1成为传播节点。
2) 如果一个传播节点与一个免疫节点接触,则传播节点会以概率P2成为免疫节点。
3) 传播节点不会无休止地传播下去,会以一定的速度v 停止传播而变为免疫节点,且
无需与其他节点接触。
二:模型的建立
假设一个节点j 在t 时刻处于未感染状态,则有:
p ii j
(1-p 1∆t )=
g
(1)
式中,g=g(t)表示在t 时刻节点j 的邻居中传播节点的数量。假设节点j 含有k 条边, g 是具有二项分布的随机变量:
∏(g , t )=(k g )w (k , t )(1-w (k , t ))
g
t -g
式中,w (k , t ) 表示在t 时刻从具有k 条边的未感染节点连接到一个传播节点的概率.
w (k , t ) 可写为如下形式:
w (k , t ) =
∑p (k |k )p (s
'
k '
k
'
|i k ) ≈∑p (k ' |k )p s (k ' |t )
k '
, (3)
ii (k , t )
度为k 的节点在[t , t +∆t ]时间段内从传播状态转移到免疫状态的概率
ii (k , t ) =∑(k g )(1-p 1∆t )w (k , t )⨯(1-w (k , t ))
g
g
k =0k
t -g
=(1-p 1∆tw (k , t ))
k
k
⎛⎫
ii (k , t ) = 1-p 1∆t ∑p (k ' |k )p s (k ' , t )⎪
k ' ⎝⎭ ,(4) 将(3)式带入得到
同理,假设概率,
p ss j
p sr j
表示节点j 在时间段[t , t +∆t ]内从传播状态转移到免疫状态的
p ss j =(1-∆tp 2)(1-v ∆t )
g
表示节点j 保持传播状态的该概率且. 于是, 如
得到度为k 的节点在[t , t +∆t ]时段内处于感染状态的平均转移概率下:
k
ss (k , t )
⎛⎫
ss (k , t )= 1-∆tp 2∑p (k ' |k )p r (k ' , t )⎪⨯(1-v ∆t )
k ' ⎝⎭ 。 (5)
则节点从传播状态到免疫状态的转移概率为由于
sr (k , t )=1-ss (k , t )
。
N (k , t )
为t 时刻网络中度为k 的节点总数量,
I (k , t )S (k , t )R (k , t )、、
分别为在t 时刻网络中度为k 的未感染节点、传播节点的免疫节点数量,则
I (k , t )
+
S (k , t )
+
R (k , t )
= N (k , t ) , (6)
于是,网络中度为k 的未感染节点的数量在 [t , t +∆t ] 时间段内的变化情况如下:
⎡⎛k ⎫⎤I (k , t +∆t )=I (k , t )-I (k , t )(1-ii (k , t ) )=I (k , t )-I (k , t )⨯⎢1- 1-p 1∆t ∑p s (k ' , t )p (k ' |k )⎪⎥
k ' ⎭⎦⎣⎝
(7)
同理,可相应得到度为k 的传播节点和免疫节点的数量在[t , t +∆t ]时间段内的变化情况如下
S (k , t +∆t )=S (k , t )+I (k , t )(1-ii (k , t ) )-S (k , t )(1-ss (k , t ))=S (k , t )+I (k , t )
⎡⎛⎡⎛k ⎫⎤k ⎫⎤
⨯⎢1- 1-p 1∆t ∑p s (k ' , t )p (k ' |k )⎪⎥-S (k , t )⨯⎢1- 1-p 2∆t ∑p s (k ' , t )p (k ' |k )(1-v ∆t )⎪⎥
k ' k ' ⎭⎦⎭⎦⎣⎝⎣⎝
(8)
R (k , t +∆t )=R (k , t )+S (k , t )(1-ss (k , t ))=S (k , t )⨯
⎡⎛k ⎫⎤r ' '
⎢1- 1-p 2∆t ∑p (k , t )p (k |k )(1-v ∆t )⎪⎥+R (k , t )
k ' ⎭⎦⎣⎝ , (9)
由(6)、(7)是可以得到
k ⎤I (k , t )⎡⎛⎫' s '
=-⎢1- p 1∆t ∑p (k |k )p (k , t )⎪⎥
N k , t ∆t N k , t ∆t ⎢⎝k ' ⎭⎥⎣⎦
假设刚开始仅存在一个推广节点作为传播节点,其余节点全部为未感染节点。假设网络中除推广节点外均视为普通节点;
假设先将推广节点包含在普通节点中,由于网络中的节点数量很庞大,单
I (k , t +∆t )-I (k , t )
个推广节点对整体 和 p (k ) 的影响可以忽略。
k Ai =k Ai +500∆t k =k +20∆t
; (11)
; (12)
当 ∆t →0 时,对(10)式右侧进行泰勒展开得到
b ∂ρi (k , t )∂t
=-kp 1ρi (k , t )∑p s (k ' , t )p (k ' |k )
k '
(13)
同理,由(8)式可以得到
b ∂ρs (k , t )∂t
=-kp 1ρi (k , t )∑p s (k ' , t )p (k ' |k )-kp 2ρs (k , t )∑p r (k ' , t )p (k ' |k )-v ρs (k , t )
k '
k '
(12)
由(9)式可以得到:
b ∂ρr (k , t )∂t
=kp 2ρs (k , t )∑p r (k ' , t )p (k ' |k )+v ρs (k , t )
k '
(14)
由于推广至节点与普通节点的度的增长率不同,将推广节点的微分方程单独列出,如下:
p 1=1; a
=-kp 1ρi (k , t )∑p s (k ' , t )p (k ' |k )
k '
∂ρi (k , t )∂t
∂ρs (k , t )∂t
(15)
a
=-kp 1ρi (k , t )∑p s (k ' , t )p (k ' |k )-kp 2ρs (k , t )∑p r (k ' , t )p (k ' |k )-v ρs (k , t )
k '
k '
(16)
a ∂ρr (k , t )∂t
=kp 2ρs (k , t )∑p r (k ' , t )p (k ' |k )+v ρs (k , t )
k '
(17)
由(11)、(12)、(13)与(14)、(15)、(16)式连理得到信息传播的动力学演化方程组,用于刻画传播节点、未感染节点和免疫节点的密度随着时间的变化关系,传播动力学过程同时受到网络拓扑结构和传播机理的影响。
根据文献1可得网络中节点的度相关性被用来描述不同网络结构之间的差异。 节点的度相关性,也称为网络选型连接性,指的是网络中与高度数( 或低度数) 节点相连接的节点的度数偏向于高还是低。 若连接度大的节点趋向于和其他连接度大的节点连接, 则认网络呈现协调混合; 若连接度大的节点趋向于和其他连接度小的节点连接,则认为网络非呈现协调混合。实际的网络的选型连接性有一些呈现协调合一些呈现非协调混合。 如社会网络( 电影演员合作网络、科学家合作网络) 中节点具有正的度的相关性, 其他类型的网络( 信息网络、技术网络、生物网络) 则相反. 根据文献,SNS 网络的度相关性一般小于零。 所以,本文( 3 ) 式中的度相关函数可以写为
p (k |k )=
'
k ' p (k ' ),
(18)
N (t )=∑(ρs (k i , t )+ρs (k i , t ))N (k i , t )
k i
, (19)
根据Matlab 算法解出N(t) (t 100) II 问题二模型的建立:
假设初始时刻网络中仅企业雇佣的推广者节点为传播节点,其余节点均为未感染节点;
假设所有推广者节点初始时刻的度为相同值(即拥有相同数量的粉丝); 假设企业雇佣的推广者数目有限,且不足以影响整个网络中的 k 和 p(k)。 在问题二中,N(t)已知(20) 假设至少需要推广者n 名;
将问题一中的模型的(14),(15),(16)改为:
na ∂ρi (k , t )∂t
=-kp 1ρi (k , t )∑p s (k ' , t )p (k ' |k )
k '
na
(21)
∂ρs (k , t )∂t
=-kp 1ρi (k , t )∑p s (k ' , t )p (k ' |k )-kp 2ρs (k , t )∑p r (k ' , t )p (k ' |k )-v ρs (k , t )
k '
k '
(22)
na ∂ρr (k , t )∂t
=kp 2ρs (k , t )∑p r (k ' , t )p (k ' |k )+v ρs (k , t )
k '
(23)
其余方程与问题一中建立的模型相同; 根据Matlab 算法解出n ;
假设初始时刻网络中仅企业雇佣的推广者节点与兼职宣传者节点为传播节点,其余节点
均为未感染节点;
假设所有推广者节点初始时刻的度为相同值(即拥有相同数量的粉丝);
假设所有兼职宣传者节点初始时刻的度为相同值(即拥有相同数量的粉丝); 假设企业雇佣的推广者数目与兼职宣传者节点有限,且不足以影响整个网络中的 k 和 p(k)。
问题二中的模型为优化问题;
即求min z
z =500N Ai +50N Bi
(24)
假设企业要宣传覆盖人群数目固定;
将问题一中的模型的(14),(15),(16)改为:
N Ai a
∂ρi (k , t )∂t
∂ρs (k , t )∂t
=-kp 1ρi (k , t )∑p s (k ' , t )p (k ' |k )
k '
(25)
N Ai a
=-kp 1ρi (k , t )∑p s (k ' , t )p (k ' |k )-kp 2ρs (k , t )∑p r (k ' , t )p (k ' |k )-v ρs (k , t )
k '
k '
(26)
N Ai a
∂ρr (k , t )∂t ∂ρi (k , t )∂t
=kp 2ρs (k , t )∑p r (k ' , t )p (k ' |k )+v ρs (k , t )
k '
(27)
N Bi a
=-kp 1ρi (k , t )∑p s (k ' , t )p (k ' |k )
k '
(28)
N Bi a
∂ρs (k , t )∂t
=-kp 1ρi (k , t )∑p s (k ' , t )p (k ' |k )-kp 2ρs (k , t )∑p r (k ' , t )p (k ' |k )-v ρs (k , t )
k '
k '
(29)
N Bi a
∂ρr (k , t )∂t
=kp 2ρs (k , t )∑p r (k ' , t )p (k ' |k )+v ρs (k , t )
k '
(30)
约束条件:
N Ai , N Bi ≥0
N Ai , N Bi
其余方程与问题一中建立的模型相同;
根据Matlab 算法解出,
;
七.模型的求解
问题一模型求解:
a=500,b= 20; 由Twitter 社交网站用户之间的链接关系(follow 关系)数据可得其次设置模型如下:P1=0.3,P2=0.1,v=0.05;迭代次数T=1000;
N (t )=∑(ρs (k i , t )+ρs (k i , t ))N (k i , t )
k i
由mathlab 求解得出人(mathlab 程序见附录1);
N (100)=
6.34⨯10e6人
即奥运会开始后,一条含有企业广告的奥运会新闻可以被6340000人观看到 问题二模型求解: 〈一〉
已知N(t) =2亿 40%, (t 100) 以及问题一中的全部数据;
将初始值带入模型微分方程中,用mathlab 求解(mathlab 程序见附录) =13 n
即企业为达到传播效果,至少需要13名专业推广者 〈二〉
z =500N Ai +50N Bi
N Ai , N Bi
根据Matlab 算法解出(mathlab 程序见附录)
即企业要聘请8个专业推广者和20个兼职宣传者可以达到宣传效果且成本最低 八.模型改进及推广
在六. 模型建立中所有普通节点都默认为一致的,而实际上节点和节点之间的关系可
划分为强关系和弱关系,其中两个节点之间的关系强度是通过一个人从好友那里获得的
评论数来衡量的。若想提高模型精确度,节点关系的强弱要考虑进去。本模型还可以推
广到谣言传播模型中去。
模型优缺点分析
优点:
1. 本模型适用于大型且关系复杂的社交网络(用户数目在6 10 级以上)。 2.本模型考虑到免疫节点的存在,信息不能无限传播下去,会以一定速度衰减成免疫 节点。
3. 本模型考虑到节点度的增长,更切合实际情况。
4.本模型是鉴于网状复杂关系建立的,相比一般传播模型更符合实际。 缺点:
本模型只适用于大型社交网络(用户数目在6 10 级以上),对于用户较少的社交网络适用 性不强。