基于图模型的传染病传播模拟算法研究

发布时间：2017-03-31 08:01

  本文关键词：基于图模型的传染病传播模拟算法研究，由笔耕文化传播整理发布。

【摘要】：人类社会进入21世纪以来,各种传染病频发。传染病的流行带走了无数的生命,夺走了无数家庭的幸福。利用计算机对传染病的传播过程进行模拟是研究传染病传播的有效手段。图模型能表达丰富语义,利用图模型能很好的表达传染病的传播过程。本文研究了如何利用图来建立简洁有效的传播模型并进行快速的模拟计算,同时大规模数据下的模拟计算也是本文研究的内容之一。为了提高模拟计算的运行速度,本文首先提出了基于EpiSimdemics算法的改进算法。改进后的算法不用事先对各种事件进行排序,避免了对一次有效接触的多次划分计算,可大幅提高模拟过程的运行速度。实验证明,改进后的算法能在获得和原有算法一样效果的前提下,显著加快运行速度。为了准确高效地表达由个体问接触引发的传播过程,本文采用了二部图结构。图的一侧是健康个体,另一侧是染病个体,边上记录接触的时间地点。本模型去除了不必要的元素,更清晰地表示了有效的传播接触。直接表达人与人间的接触,省掉了”人与地点”模型的中间转换过程,很好地提高了模拟速度。实验证明,利用本文建立的模型进行模拟计算具有相当的可行性,并且算法具有更优的性能。针对大规模区域、大数据量的模拟计算,本文首先采用了分布式计算方式,采用Metis算法对模型进行分割。分割算法保证分割后子图的边数相当,也就是保证了计算的负载均衡,同时连接子图间的边数最少,通信代价也就很低。相对于其它算法采用的round-robin分割方式能极大地提高效率。一台Master机凭借给定的代价计算模型动态确定分割方案,并负责任务的分发和最后结果的汇总。Slave机收到子图模拟任务后,采用集中式算法进行计算,最后报告计算结果。实验证明,本文的分布式模拟计算算法能处理大规模数据的模拟,运行高效,通信代价也较低。MapReduce编程模型是大数据计算的有效方法,能以简单明了的方式解决复杂的问题。实现MapReduce的开源工具很多,像Hadoop、Spark均已被广泛的应用。它们在节点容错、资源分配等方面有很大的优势。本文设计实现了传染病传播模拟算法的MapReduce版本,以保障在真实部署模拟时程序的健壮性和高效性。实验表明,本文基于MapReduce的模拟算法能达到很高的精确度和很好的性能。
【关键词】：传染病 模拟 图模型 分布式 MapReduce
【学位授予单位】：东南大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：R51;O157.5
【目录】：

• 摘要4-5
• Abstract5-8
• 第1章 绪论8-12
• 1.1 研究背景8-9
• 1.2 研究内容9-10
• 1.3 本文组织结构10-12
• 第2章 相关技术概述12-21
• 2.1 基本概念12
• 2.2 传染病传播模拟算法12-17
• 2.2.1 传统的传染病模拟方案12-13
• 2.2.2 图模型下的传染病仿真13-17
• 2.3 图分割算法17
• 2.4 大数据处理技术17-20
• 2.4.1 分布式计算18-19
• 2.4.2 MapReduce编程模型19-20
• 2.5 本章小结20-21
• 第3章 基于图模型的传染病传播模拟算法21-35
• 3.1 引言21-22
• 3.1.1 健康状态划分21
• 3.1.2 健康状态转换方式21-22
• 3.2 改进的EpiSimdemics算法22-26
• 3.2.1 EpiSimdemics算法的不足22-23
• 3.2.2 本文的改进方案23-25
• 3.2.3 EpiSimdemics-Pro算法正确性分析25
• 3.2.4 EpiSimdemics-Pro算法复杂度分析25-26
• 3.3 基于个体接触二部图模型的传染病模拟算法26-28
• 3.3.1 HAI模型描述26-27
• 3.3.2 HAI算法框架27-28
• 3.3.3 HAI算法分析28
• 3.4 传染病模拟算法的应用策略28-29
• 3.5 实验结果与分析29-34
• 3.6 本章小结34-35
• 第4章 大规模数据下的传染病传播模拟算法35-54
• 4.1 引言35
• 4.2 分布式下的传染病传播模拟算法35-46
• 4.2.1 分布式计算架构35-36
• 4.2.2 基于Metis算法的图模型分割方案36-37
• 4.2.3 代价模型37-38
• 4.2.4 代价模型的应用策略38-39
• 4.2.5 分布式HAI算法描述39-40
• 4.2.6 实验结果与分析40-46
• 4.3 基于MapReduce的传染病传播模拟算法46-53
• 4.3.1 基于MapReduce的EpiSimdemics算法46-48
• 4.3.2 基于MapReduce的HAI算法48-49
• 4.3.3 实验结果与分析49-53
• 4.4 本章小结53-54
• 第5章 总结与展望54-55
• 致谢55-56
• 参考文献56-58

【相似文献】

中国期刊全文数据库 前10条

1 王莉;秦勇;徐杰;豆飞;贾利民;;植物多向生长模拟算法[J];系统工程理论与实践;2014年04期

2 吕丽华;;五种互连快速模拟算法比较研究[J];科技信息;2010年11期

3 张凌晓;闫朝华;;基于矩阵模型的花色线模拟算法[J];科技资讯;2007年15期

4 顾大权;范茵;许屏;龚琳;;建立天空场景的模拟算法[J];气象科技;2007年02期

5 谢剑斌,郝建新,蔡宣平,孙茂印;基于混合建模方法的三维彩色树木快速模拟算法[J];国防科技大学学报;1999年06期

6 林阿龙;;一种新的定性模拟算法QSIM[J];东南大学学报;1990年06期

7 顾大权;范茵;许屏;龚琳;阮鲲;;运动云彩的模拟算法[J];气象科技;2006年02期

8 庞园园;陈长波;;基于简化流场的实时爆炸模拟算法[J];测绘技术装备;2011年01期

9 冯三营;裴丽芳;;复杂系统可靠性的模拟算法研究[J];洛阳师范学院学报;2009年02期

10 邱建英;;基于约束神经网络的三维织物模拟算法[J];科技通报;2013年10期

中国重要会议论文全文数据库 前3条

1 张建忠;刘二莉;张君琦;;一种快速而有效的布模拟算法[A];全国第十五届计算机科学与技术应用学术会议论文集[C];2003年

2 王妍;王文永;钟绍春;艾亭;任月欧;;基于“黄金分割点细分内插法”的海岸线模拟算法[A];第十四届全国图象图形学学术会议论文集[C];2008年

3 何其昌;范秀敏;马登哲;付百川;;交互式自行车模拟器体感模拟研究[A];系统仿真技术及其应用（第7卷）——'2005系统仿真技术及其应用学术交流会论文选编[C];2005年

中国硕士学位论文全文数据库 前10条

1 陈坤;基于图模型的传染病传播模拟算法研究[D];东南大学;2015年

2 王志东;提花织物外观计算机模拟算法研究[D];浙江大学;2004年

3 苏航;数字系统并行模拟算法的研究[D];太原理工大学;2004年

4 余静;海面实时航迹模拟算法的研究与实现[D];浙江大学;2013年

5 张艳玲;基于随机Petri网的随机生物过程的模拟算法研究[D];哈尔滨工业大学;2007年

6 林琢;基于L系统的三维树木枝条弯曲与运动模拟算法的研究[D];燕山大学;2007年

7 刘博;周期结构材料中的衍射电磁波的场模拟算法研究[D];电子科技大学;2011年

8 陈光华;统计模拟算法研究及其在金融分析中的应用[D];暨南大学;2011年

9 童静;多层周期结构光栅衍射模拟算法的GPU加速研究[D];电子科技大学;2013年

10 孙志嘉;VIS中电路模拟算法的GPU实现[D];电子科技大学;2010年

  本文关键词：基于图模型的传染病传播模拟算法研究，，由笔耕文化传播整理发布。

本文编号：279202