论文标题
基于Dijkstra算法模拟流行病的低复杂度方法
Low Complexity Method for Simulation of Epidemics Based on Dijkstra's Algorithm
论文作者
论文摘要
网络上的流行病模型已经流行，因为它们描述了个体行为对感染传播的影响。但是，它们具有很高的计算复杂性，如果考虑大规模方案，这构成了问题。本文提出了一个离散的多代理SIR（易感，感染，恢复）模型，该模型扩展了文献中的已知结果。基于此，使用新颖的传染图概念，它提出了一种基于图形的方法，该方法衍生自Dijkstra的算法，允许降低模拟的计算复杂性。传染图还可以用作近似方案，该方案描述了网络上流行病的“平均行为”，并且需要低计算能力。理论发现通过随机大规模模拟证实。
Models of epidemics over networks have become popular, as they describe the impact of individual behavior on infection spread. However, they come with high computational complexity, which constitutes a problem in case large-scale scenarios are considered. This paper presents a discrete-time multi-agent SIR (Susceptible, Infected, Recovered) model that extends known results in literature. Based on that, using the novel notion of Contagion Graph, it proposes a graphbased method derived from Dijkstra's algorithm that allows to decrease the computational complexity of a simulation. The Contagion Graph can be also employed as an approximation scheme describing the "mean behavior" of an epidemic over a network and requiring low computational power. Theoretical findings are confirmed by randomized large-scale simulation.
