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