Research On Graph-based Infectious Disease Spreading Simulation Algorithms

In the 21st century, a variety of infectious diseases outbreak. Infectious diseases took away countless lives and families’happiness. Using the computer to simulate its propagation is one effective means to study its spreading characteristics. Graph model can express the propagation of infectious diseases effectively. This thesis studies how to use the graph to build a simple and effective model and simulate fast, with large-scale simulation is also under the research of this thesis.Based on the existing models, this thesis proposes an advanced algorithm named EpiSimdemics-Pro, to improve the speed of the simulation. Without prior sorting for events, the improved algorithm (EpiSimdemics-Pro) avoids parting and repetitive computing an intact contact The experiments show that the EpiSimdemics-Pro algorithm improves the efficiency significantly.The thesis uses the bipartite graph to express diffusion process between individuals. One side of the model are healthy individuals, the other side are sick individuals. Time and place of the contact are recorded on its edges. This model eliminates redundant elements. The conversion process is needed in the "people and place" model to get the contact information. This "people and people" model expresses contact directly and avoids the conversion. The experiments show that, using the model established in this thesis is quite feasible, and the algorithm has a better performance.This thesis uses distributed computing as a solution to large-scale simulation. The classical Master-Slave structure is used. Master is responsible for distributing the task and collecting the final result. Slaves use the centralized algorithm to calculate and then report the results. Master uses Metis to segment the model, which is better than the round-robin manner other algorithm used. The experimental results show that the distributed algorithm can handle the large-scale simulation effectively.MapReduce programming model is a favourable way to solve the current Big Data calculation problem. A lot of tools achieve MapReduce model like Hadoop,Spark. They have a great advantage in terms of fault tolerance, resource allocation. This thesis implement a MapReduce vision of simulation algorithm for robustness and efficiency of the deployment. The experiments show that the algorithm based on MapReduce can obtain high accuracy and good performance.