网络传播动力学

第7卷第2-3期复杂系统与复杂性科学Vol. 7 No. 2-3010年9月COMPLEX SYSTEMS AND COMPLEXITY SCIENCESep.2010文章编号:1672-3813(2010)02-03-0033-05网络传播动力学李翔,刘宗华2,汪秉宏31.复旦大学,上海200433;2.华东师范大学,上海200241;3.中国科学技术大学,合肥230026摘要:病毒的流行、谣言的散布、观点的传递都是在不同网络上的形形色色的传播现象,既存在着现象后的不同起因和特征,更存在着千丝万缕的联系和共通的演化机理。汇总了复旦大学、华东师范大学和中国科学技术大学的研究小组过去几年里在网络传播动力学的研究成果。关键词:复杂网络;传播动力学;网络中图分类号:N941文献标识码:AOn Spreading Dynamics on NetworksLIhua2. WANG(1. Fudan University, Shanghai 200433, China; 2. East China Normal University, Shanghai 230026, China3. University of Science and Technology of China, Hefei 230026, CIAbstract: The prevalence of epidemics, rumors, and opinions are various spreading phenomena on dif-ferent categories of networks, which not only exhibit specific features and backgrounds, but also sharesome mechanisms and extensive interconnections. This paper is a brief collection including the work andhinking on this topic from the research groups of Fudan Univeristy, East China Normal University, andUniversity of Science and Technology of China.Key words: complex networks; spreading dynamics; network网络传播研究涉及疾病扩散、輿论传播及其动力学等问题。(计算机或生物)病毒在网络上的流行与传播行为是复杂网络理论的主要研究内容之一,也是近年来人们在社会经济活动中最为密切关注的一个主题。SARS、禽流感、冲击波、震荡波、熊猫烧香、灰鸽子等生物和计算机病毒的肆虐给人们带来了以千亿美元计数的巨大经济损失,而且这一传播过程通常极为迅速。以2004年的“震荡波”蠕虫病毒为例,在短短的十余天内全球数千万台计算机遭受到它的攻击,其传播速度惊人。复杂网络传播动力学行为的研究还包括对谣言舆论、观点等主体在网络上扩散现象的探讨。本文主要汇总了复旦大学、华东师范大学和中国科学技术大学这几个研究小组在过去几年里对上述问题的若干思考。历史上流行病动力学的研究已经提出了几个代表性模型。伴随复杂网络研究的兴起,复旦大学研究小组-間°通过数值计算和理论分析研究网络上传播动力学的若干模型,在探索复杂网络的传播临界值理论基础上,结合非线性动力学分析了传播动态过程中存在的混沌、分叉等典型动力学行为特征,围绕小世界、无标收稿日期:2010-06-14中国煤化工基金项目:园家自然科学基金项目(10635040,10975126,60874089,91024026CNMH校博士点基金项目(20093402110032);教育部新世纪优秀人才计划项目(NCET-09-031知-^目(09QH1400200)作者简介:李(1975-),男,湖南人,教授博导,主要研究方向为复杂网络系统理论与应用。复杂系统与复杂性科学2010年9月度网络等典型模型分析了拓扑结构对于传播动力学的影响等。值得特别指出的是,研究小组发现在时延环境下小世界特性是网络系统中不可避免地存在震荡传播过程的特征结构0。这一系列的研究结果有助于分析相应控制策略的有效性,并提出抑制疾病在网上传播的对策6。针对人们社会活动的网络化特征,复旦大学研究小组还进一步分析人群与不同现实网络交互影响下的网络传播动力学性能分析及其防控策略,围绕人群的个体差异性,研究了在考虑不同类型的幂律和指数分布的易感性和传染能力时,移动的人群中爆发流行病的临界值条件,得到了个体差异性与病毒蔓延相关性等-24-。复杂网络上流行病传播可在更高级别上进行研究,比如一个节点对应一个城市或一个地区,因而单个节点上可以同时拥有大量的粒子或个体,以前的研究主要集中在个体扩散对流行病传播的影响,近年来, Vespignani小组开始考虑一个节点可以同时被多个粒子占据的反应-扩散模型。以此为契机,华东师范大学的研究小组探讨了个体迁移模式对于无标度网络上流行病传播的影响,着重考虑了人类活动的两个特点:目的性与集聚性对流行病传播的影响:23)。因为人类的旅行活动具有目的性,是不能严格当做随机扩散的;另外,人类的活动容易导致在公共场所的集聚现象,这种活动会加剧流行病的传播。1华东师范大学课题组的研究目前复杂网络上的流行病传播模型与真实发生的过程还有相当大的距离,比如人类活动不能简单等同于复杂网络上的随机行走,而是具有其自身的独特特征,如社区性旅行目的性及对场所的时间段占据特性等。这些显著的特征是如何影响流行病的传播是一个亟待研究的问题。鉴于此,我们在以前工作的基础上1-121,对复杂网络上流行病的传播做了较系统的研究。基于真实的社会总是以社区为单位的,我们首先讨论了社区结构对流行病传播带来的影响构造了一个社区网模型来研究其上的流行病传播-1,并用主方程得到了解析解。一个社区模型的典型例子是曼谷与周围72个省之间的登革热传播呈时间与空间的双周期行为,其机制可通过一个分立的映像得到说明。社区特征也是疾病预防与控制中必须考虑的因数。由于城市依赖于外部的给养而生存,无法做到与外界的完全隔绝,因此貌似安全的城市间的接触也存在着间接传播疾病的隐患。我们发现人员的迁移可导致流行病的间接传播,且社区结构有利于病毒的存活。然后,考虑到人们容易在公共场所聚集的特点侧重研究了公共场所的人员聚集对流行病传播的影响,并发现了加速传播效应。接着考虑到现实中人类的迁移活动往往是一个较长时间的旅行,且带有确定性倾向,比如我们国家的春运,在迁移过程中,病毒携带者可以与固定邻居进行长时间接触,也可以与不同站台、不同车厢的人员进行依次接触。这与随机行走是根本不同的,随机行走的下一个节点或下一站总是随机选取的,而倾向性旅行者的下一站是预先选好的、是固定了的。考虑到人类活动的这种目的性特征,我们首次讨论了病毒携带者的非随机行走如通过飞机火车等长途旅行带来的加速传播后果”2。此外,我们还考虑了真实情况下社会网的结构总是动态变化的,一个人此时在甲处,下一时刻就可能在乙处;甲处此时有很多人,下一时刻可能是空的,如教室与食堂等;因此我们将固定的社会网络结构拓广成更实际的动态社会网,即讨论了人们对场所的部分时间占据导致的移动效应对流行病传播的影响,发现了感染人数在某一最优移动几率处达到极大(。另一方面,由于流行病的扩散特征,如何从扩散方面进行刻画2及将流行病模型用于研究谣言的传播也是我们感兴趣的问题。2中国科学技术大学课题组的研究2.1.疾病传播1)以性行为为例,虽然科学家通过研究发现性关系网具有无标度性质但是我们不能根据“无标度网络上没有疾病阈值”的结论肯定疾病一定会大范围的爆发。由中国煤化工虽然有的个体有CNMHG或者感染别人的兀呼八诞山一个修正的流行病传播模型,其中每一节点在每一时步被赋予相同的活跃接触能力A。通过平均场论得到与以前研究不同的解第7卷第2-3期李翔,等:网络传播动力学析结果,发现非零阈值为1/A,这表明阈值与所研究的网络的拓扑结构无关。模拟与解析结果一致。进步,研究了流行病传播的时间行为,发现一种具有3个平台的级联动力学。流行病感染一旦到达了高连接性的网络中心结点,就会通过逐步向较小度类结点传播的级连过程遍布几乎整个网络。于是,在以前感染的网络中心结点得以恢复之后,疾病只能够传播到较小度类的结点,直至所感染的个体全部恢复。这一结果对于动力学控制策略的确立可能具有实际的重要性26-2)不同的传播过程可以看作是接触过程( contact process)的一个特例,如疾病传播、信息传播等。因此杨锐等人通过假定个体的接触过程存在偏爱性,即W(k):A,当B>0表示个体偏向接触度大的结点,反之表示接触度小的结点,当B=0,表示无偏爱的接触过程。通过数值模拟和理论证明发现存在一个最优值B=-1,使传播范围达到最大化。这一结果和复杂网络上的最优同步能力的结论一致1。3)当某种传染病爆发的时候,必然会引起一些外界因素的变化,如个体采取自我保护措施,政府采取预警机制等。张海峰等人研究自我接种机制对疾病传播行为的影响。由于接种或不接种都面临一定的风险和代价,因此个体通过比较自我被感染的风险和代价决定是否采取接种。研究发现,之前的结果表明由于无标度网络中有很多度大的结点,使疾病很容易爆发;而在自我接种机制下度大结点同时面临着更大的风险,因此他们更愿意采取接种行为。此结果表明在自我接种机制下,即使在无标度网络上的疾病也很容易控制)。由于当前各种媒介的存在使人们可以很快地了解不同区域的发病情况,因而采取相应的措施。当人们了解到某个区域的感染情况比较严重时,个体会采取断开与高发区的联系或者重新建立其他的联系。韩筱璞通过引入预警机制,研究小世界网络上的SI模型,发现预警机制可以降低疾病的传播范围。4)以前对网络上的疾病控制策略往往考虑免疫结点,如随机免疫、目标免疫、熟识者免疫等。虽然这些方法在特定的条件下证明是有效的,但是免疫结点的方式破坏了网络的连通性,在有些条件下保证网络的连通性是非常有必要的,比如 Internet网络中,如果关闭那些度大的路由,会严重制约 Internet网络的作用。所以张海峰等人提出了一种删边的控制策略:删除两端结点度都比较大的连线。通过模拟发现,这种方法可以有效地控制疾病的传播,并且可以很好地保证网络的连通性。5)网络上不同边的权重往往不同,权重可能导致不同的传播行为,因此严刚等人研究含权网络上的疾病传播行为,通过与无权网络比较发现,含权网络上的疾病传播速度首先增加到一个峰值,然后以幂率形式下降,同时,不同于无权网络,含权网络上疾病传播的分层现象不明显。此外,他们发现,权重分布越分散越不利于疾病的传播。212.2舆论传播1)姜罗罗等人研究了自我主张对于一个有向小世界社会网络中的公众奥论形成的影响。系统呈现出一个从公众舆情一致状态到多种观点并存的无序状态转变的非平衡相变。在有向小世界网络中,断边重连概率的大小表征了个体间有向长程联系的强弱。研究表明奥情动力学行为对于长程有向相互作用之密度及自我肯定之强度非常敏感。当个体间的有向长程联系很弱并且个体不坚持自己观点的时候,体系呈现出连续相变;相反,当个体间的有向长程联系和个体自我认同都很强的时候,体系不发生相变;当有向长程联系和个体自我认同介于两者之间的情况时,体系经历非连续相变2)在舆论传播中,不同度的人对别人的影响可能不同,因此,杨涵新等人通过假定个体i的观点被个体j接受的概率为式中,k,表示结点i的度。如果a>0,则度大的观点更容易被接受,反之度小的观点更容易被接受,通过研究发现,存在适当的a>0,使收敛时间最短M。中国煤化工3)在舆论传播过程中,如果两个个体的观点相差太大CNMHG基于此,郭强等人假定两个个体如果观点度差异大于一定的容忍度,个体就采灬栘啁。遇过及塊,心你度网络上舆论传播行为更容易达到一致,同时移动行为和增加个体密度可以提高收敛速度。复杂系统与复杂性科学2010年9月参考文献:[1]李翔,王林复杂网络病毒传播动力学与控制——个体异质与移动属性的影响[C].2010年中国物理年会秋季会议天津,2010:17-1Li Xiang, Wang Lin. Epidemics dynamics and control on complex networks: roles of individual heterogeneity and mobility [C]Autumn Conference of Chinese Physics Society. Tianjin, 2010: 17-1[2] Li X, Cao L, Cao G. Epidemic prevalence on random mobile dynamical networks: individual heterogeneity and correlation[J]European Physical Journal B, 2010, 75:319-326[3]李期.复杂动态网络传播动力学[刀].力学进展,2008,38(6):723-732Li Xiang Spreading dynamics on complex dynamical networks[ J]. Advances in Mechanics, 2008, 38(6):723-732[4]曹崀曹桂芳李翔移动多智能体系统的病毒传播研究[C].第七届全球智能控制与自动化大会.重庆,2008:18801884Cao Lang, Cao Guifang, Li Xiang. The study of epidemic spreading in a mobile multi-agent system[ C]. Proceedings of the 7thWorld Congress on Intelligent Control and Automation. Chongqing, 2008: 1880-1884[5]曹桂芳,曹遴,李翔具有感染显性率的移动多智能体系统病毒传播及其控制策略[].中国控制与决策2008年会议论文Cao Guifang, Cao Lang, Li Xiang. The study of epidemic spreading on a mobile multi-agent system with infective expressivity andits control stralegy[ C]. Proceedings of Chinese Control and Decision Conference. Yantai, 2008: 4001-4004[6]Xu D, Li X, Wang X F. An investigation on local area control of virus spreading in complex networks[J]. Acta Physica Sinica2007,56(3):1313-1317[7] Li X, Wang X F. On the stability of epidemic spreading in small-world networks: how prompt the recovery should be? [J.International Journal of Systems Science, 2007, 38(5): 400-407.[8] Guo W P, Li X, Wang X F. Epidemics and immunization on euclidean distance preferred small-world networks[ J]. Physica A[9] Li X,Wang X F. Controlling the spreading in small-world evolving networks: stability, oscillation, and topology[J].IEEETransactions on Automatic Control, 2006, 51(3): 534-540[10] Li X, Chen G R. Models, dynamics and control of spreading in complex networks: a survey[ J]. Dynamics of Continuous, Dis-crete and Impulsive Systems-B, 2006, 13(c): 109-116[11] Liu Z H, Lai Y C, Ye N. Propagation and immunization of infection on general networks with both homogeneous and heterogeneous components[J]. Phys Rev E, 2003, 67: 031911[12] Lai Y C, Liu Z H, Ye N. Infection dynamics on growing networks[ J]. International Joumal of Modern Physics B, 2003, 174045-4061[13] Liu Z H, Hu B. Epidemic spreading in community networks[ J]. Europhys Lett, 2005,72: 315.[14]Zhou Y Z, Liu Z H, Zhou J. Periodic wave of epidemic spreading in community networks[ J]. Chin Phys Lett, 2007, 24: 581[15] Wu X Y, Liu Z H. How community structure influences epidemic spread in social networks[J]. Physica A, 2008,387:623[16] Zhou ], Liu Z H. Epidemic spreading in communities with mobile agents[J]. Physica A, 2009, 388: 1228[17]Zhang H, Liu Z H, Ma W C. Epidemic propagation and microscopic structure of complex networks[ J]. Chin Phys Lett, 200623:105[18 Tang M, Liu L, Liu Z H. Influence of dynamical condensation on epidemic spreading in scale- free networks[ J].PRE, 2009,79016108[19] Tang M, Liu Z H, Li B W. Epidemic spreading by objective traveling[ J]. Europhys Lett, 2009, 87: 18005[20]唐明个体迁移模式对于无标度网络上流行病传播的影响[,2009年第五届全国复杂网络学术会议青岛,2009:14Tang Ming. Influence of individual mobility patterns on epidemic spreYH中国煤化工CNMHGConference on Complex Network. Qingdao, 2009: 14-17[21] Liu Z H. Effect of mobility in partially occupied complex networks[J]. Phys Rev E, 2010, 81: 016110第7卷第2-3期李翔,等:网络传播动力学37[22]wu X Y, Liu Z Hnie diffusion on complex networks[ J]. Chin Phys Lett, 2007, 24: 1118[ 23] Liu ZH, WuXYAn alternative approach to characterize the topology of complex networks and its application indemic spreading[ J]Comput Sci China, 2009(3): 324[24] Zhou J, Liu Z H. Epidemic spreading in complex networks[ J]. Front Phys China, 2008, (3): 331[25]Zhou J, Liu Z H, Li B W. Influence of network structure on rumor propagation[ J]. Phys Lett A, 2007, 368: 458[26] Zhou T, Liu J G, Bai W J, et al. Behaviors of susceptible-infected epidemics on scale-free networks with identical infective[27] Yang R, Wang B H, Ren J, et al. Epidemic spreading on heterogeneous networks with identical infectivity[ J]. Phys Lett A[28]Yang R, Zhou T, Xie Y B, et al. Optimal contact process on complex networks[ J]. Phys Rev E, 2008, 78: 06610929]Zhang H F, Zhang J, Zhou C S, et al. Hub nodes inhibit the outbreak of epidemic under voluntary vaccination[ J]. New JPhys,2010,12:023015[ 30] Han X P. Disease spreading with epidemic alert on small-world networks[ J]. Phys Lett A, 2007, 365:1[31] Zhang H F, Li K Z, Fu X C, et al. An efficient control strategy of epidemic spreading on scale-free networks[ J]. Chin PhysLett.2009,26:068901[32] Yan G, Zhou T, Wang J, et al. Epidemic spread in weighted scale-free networks[ J]. Chin Phys Lett, 2005, 22(2): 510[33]Jiang L L, Hua D Y, Zhu J F, et al. Opinion dynamics on directed small-world networks[ J]. EPJB, 2008, 65: 251[34] Yang H X, WuZ X, Zhou C S, et al. Effects of social diversity on the emergence of global consensus in opinion dyna-mics[ J]Phys Rev E,2009,80:046108[35] Guo Q, Liu JG, Wang B H, et al. Opinion spreading with mobility on scale-free networks[ J]. Chin Phys Lett, 2008, 25(2)中国煤化工CNMHG