微博网络消息传播模型与仿真;网络工程

安徽工业大学毕业设计（论文）说明书共56页第1页微博网络消息传播模型与仿真网络工程专业彭陶（099074368）指导教师郑啸教授摘要近年来，以微博为代表的社交网络得到了迅速的发展，例如国内的新浪微博和国外的Twitter。热点问题在很短的时间内就得到广泛传播。对于微博传播行为的分析和预测就可以探测热点话题，以及可以监测和防止垃圾信息。本文以微博用户间形成的复杂网络系统为研究对象，以现有的复杂网络的研究成果为基础，着重研究微博消息的传播行为。有趣的是：微博消息的传播和传染病病毒的传播行为是很相似的。病毒模型是医学领域的研究成果，基于这些模型可以预测未来的微博转发趋势。所以本文具体会研究三大基本传染病病毒模型SI(SusceptibleInfections)，SIS(SusceptibleInfectionsSusceptible)，SIR(SusceptibleInfectionsRecovery)。同时，对于不同的微博来说，每个博主的影响力是不同的，这个因素也会影响到微博的传播行为。文中对于两大影响力模型IC(IndependentCascade)和LT(LinearThreshold)模型也进行了一些研究。本文将仿真微博传播行为，可视化出微博的传播路径，可以更清晰的看到在不同的模型下，微博的传播行为的异同。具体的一些成果：1）根据现有的五大模型，实现算法2）对于影响力模型中的影响因素，对于影响概率计算提出自己的计算公式3）对复杂网络中的一些参数的计算4）对微博消息的传播过程进行可视化关键词：微博；复杂网络；病毒模型；SI；SIS；SIR；影响力模型；IC；LT安徽工业大学毕业设计（论文）说明书共56页第2页AbstractRecently,thesocialnetworksdevelopfastasarepresentativeofMicroBlog,likeSinamicrobloginChina,andTwitterinforeigncountries.Hottopicscurrentlybeingpropagatedcanquicklybecomepopularwithinaveryshorttime.Analyzingandpredictingthepropagationbehaviorcandetecthottopics,monitorandpreventspammessage.ThispaperstudiesuponthecomplexnetworksystemwhichisconsistoftheusersofSinamicroblog.Webaseontheexistingresearchresultsofcomplexnetwork.Weconcentrateonstudyingthepropagationbehaviorofmicroblog.Interestingly,thepropagationofmessagebearssomesimilaritytothespreadofinfectionsdiseases.Theepidemicistheresultsofmedicalfield.Onthebasisofthesemodels,futurepropagatingtrendscanbepredicted.Inthispaper,wewillstudythreeepidemicmodels,SI(SusceptibleInfections),SIS(SusceptibleInfectionsSusceptible),SIR(SusceptibleInfectionsRecovery).Atthesametime,todifferentmicroblog,everybloguserhasdifferentinfluencetoothers.Thisfactorcanalsoinfluencethepropagationbehaviorofmicroblog.So,wealsostudythetwoinfluencemodelsnamelyIC(IndependentCascade)andLT(LinearThreshold).Thispaperwillsimulatetheprocessofpropagationbehavior.Thepropagatepathcanbevisual.Wecanclearlyobservethedifferentpropagationbehaviorsindifferentmodels.Themainachievementwemadeasfollows:1.Achievetheplacementalgorithmbasingonthefivemodels.2.PutstheFormulaofinfluencefactorininfluencemodels.3.Computetheparametersofthecomplexnetworksystem.4.Visualizetheprocessofpropagationbehavior.Keywords:microblog;complexnetworks;epidemicmodel;SI;SIS;SIR;influencemodel;IC;LT安徽工业大学毕业设计（论文）说明书共56页第3页1绪论1.1微博简介微博，即WeiBo，又叫微博客，英文单词microblog。作为Web2.0的产物,微博属于博客的一种形式,但单篇的文本内容通常限制在一定范围内(通常为140个汉字),使用户能够通过微博融合的多种渠道(包括网页、手机、即时通讯、博客、SNS社区、论坛等)发布文字、图片、视频、音频等形式的信息,具有内容碎片化、微博与传统博客相比，以“短、灵、快”为特点。2006年3月，blogger的创始人埃文·威廉姆斯(EvanWilliams)首创了微博服务。Twitter的横空出世把世人引入了一个叫“微博”的世界。在国外大红大紫的Twitter也成为国内企业效仿的对象。王兴于2007年5月建立了饭否网，开启了中国的微博时代。随后不久，叽歪网、做啥网相继上线，拥有数亿用户的腾讯也于2007年8月13日推出了腾讯滔滔。2009年8月，新浪微博上线，并迅速成长为中国最具影响力的微博。截止2012年12月底，中国微博用户规模达到3.09亿（较2011年底的2.498亿增长了5873万），成世界第一大国。随着微博在网民中的日益火热，与微博相关的词汇也迅速走红网络，“微博效应”正在逐渐形成。本系统以新浪微博为例，新浪微博用户之间有两种关系，比如用户A关注了用户B，那么，A就是B的粉丝，而B就是A的好友。正是用户之间的这种关系，使得新浪微博用户间形成了一个复杂网络，本系统就是以该复杂为研究对象。1.2复杂网络研究现状1.2.1复杂网络介绍微博网络是复杂网络的一种，下面即先看看复杂网络的研究现状。复杂网络是复杂系统的抽象，网络中的节点是复杂系统中的个体，节点之间的边则是系统中个体之间按照某种规则而自然形成或人为构造的一种关系。现实世界中包含着各种类型的复杂网络，如社会网络（朋友关系网络及合作网络等，图1）、技术网络（万维网以及电力网等，图2）。近年来，复杂网络得到学术界学者的广泛研究。特别是，国际上有两项开创性工作掀起了一股不小的研究复杂网络的热潮：一是1998年Watts和Strogatz在Nature杂志上发表文章，引入了小世界（Small-World）网络模型，以描述从完全规则网络到完全随机网络的转变。小世界网络既具有与规则网络类似的聚类特性，又具有与随机网络类似的较小的平均路径长度；二是1999年Barabas和Albert在Science上发表文章指出，许多实际的复杂网络的连接度分布具有幂律形式。由于幂律分布没有明显的特征长度，该类网络又被称为无标度（Scale-Free）网络。总之：复杂网络（ComplexNetwork），具有自组织、自相似、吸引子、小世界、安徽工业大学毕业设计（论文）说明书共56页第4页无标度中部分或全部性质的网络称为复杂网络。图1朋友网图2万维网1.2.2传播模型研究现状常见的微博消息转发模型研究是基于传染病模型和影响力模型的。基本的传染病模型有SI模型，SIS模型，SIR模型，基本的影响力模型有IC和LT模型。自从20世纪以来，对于病毒传播模型的研究已经被关注的很多了。在1906年，Hamer为麻疹构建了离散时间模型。在1911年，Ross提出一种不同的模型区研究疟疾在蚊子和安徽工业大学毕业设计（论文）说明书共56页第5页人群中的传播。证明了如果蚊子数量控制在一个阈值下，疟疾是可以被控制的。这项研究成果使得它获得诺贝尔医学奖。在1927年，Kermack和Mckendrick提出了著名的SIR模型。M.E.J.Newman在《TheSpreadofEpidemicDiseaseonNetworks》[1]中对SIR模型进行了明确的分析和论证。使得SIR模型在复杂网络上转发微博消息的传播成为可能。清华大学WANGHao等发表论文《ReTweetingAnalysisandPredictioninMicroblogs--AnEpidemicInspiredApproach》[2]中提出两种改进的传染病模型SISe和SISe+模型。在基本的传染病模型中，前提是不变的人口数和固定的传播概率。他们在论文中采用了动态的传播概率，使得分析和预测的结果更加接近真实结果，错误率更低。实验的结果表明，传播概率是动态变化的，当转发数量大时候，SISe+比SISe预测得更好，但是当转发量渐小的时候，SISe比SISe+表现更好。但是总体来说，实验结果比基本模型的预测都更加准确。张发等《传染病传播模型综述》[3]中对各种传染病模型的特点进行总结比较。对于每种模型适用于那些领域，以及需要解决那些问题，怎样建模都进行了分析。丁玲芬的《几类传染病模型的定性分析》[4]中讨论一种传染病模型的变种SEIR模型，一类具有垂直传染非自治的SEIR传染病模型,以及一类具有垂直传染总人口数变化非自治的SEIR传染病模型。LukeDickens等《Learningstochasticmodelsofinformationflow》[5]中提出了一个可扩展的方法用于一个基于独立级联模型的网络中的信息传播学习模型和预测信息传播的可能路径。Ref[6]使用MACD(MovingAverageConvergence-Divergence)去预测趋势。Ref[7]在twitter上使用一种探测主题的方法，通过时间，关键字和关系等因素来建立模型。当然还有其他的一些模型例如：南京大学DeChunLiu发表的论文《RumorPropagationinOnlineSocialNetworksLikeTwitter--ASimulationStudy》[8]提出的RumorPropagation。对于网络中消息的传播也进行了分析与预测。并且取得了良好的结果。1.3本论文的组织结构第一部分：绪论主要介绍复杂网络的研究现状，同时介绍微博传播的一些理论模型。第二部分：介绍常见的几种模型这些模型包括，传染病模型，SI，SIS，SIR，影响力模型，IC和LT模型，介绍其基本理论，模型效果已经应用大微博传播的过程中的情况。第三部分：主要是介绍本仿真系统，包括系统的功能、模块划分、实现思路简介流程图等。第四部分：主要是介绍本系统的具体实现过程。第五部分：主要是介绍系统的测试用例及分析。第六部分：总结与展望。第七部分：致谢，参考文献以及附录。安徽工业大学毕业设计（论文）说明书共56页第6页2几种传染病模型和影响力模型2.1传染病模型描述一般扩散影响的地理单元或者感染体累积量变化过程的模型。传染病模型有很多变种，例如SI，SIS，SIR和ISRSE等。我们在这里主要分析SI，SIS和SIR三种模型。[2]同时需要知道的是，传染病模型已经非常成熟，在手机病毒传播[8]过程中