Low Complexity Method for Simulation of Epidemics Based on Dijkstra's Algorithm
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Simulation algorithms for Markovian and non-Markovian epidemics
Researchers have employed stochastic simulations to determine the validity of their theoretical findings and to study analytically intractable spreading dynamics. In both cases, the correctness and efficiency of the simu…
EpidemiologyNew Trends on the Systems Approach to Modeling SARS-CoV-2 Pandemics in a Globally Connected Planet
This paper presents a critical analysis of the literature and perspective research ideas for modeling the epidemics caused by the SARS-CoV-2 virus. It goes beyond deterministic population dynamics to consider several key…
Decision MakingAdapting Dijkstra for Buffers and Unlimited Transfers
In recent years, RAPTOR based algorithms have been considered the state-of-the-art for path-finding with unlimited transfers without preprocessing. However, this status largely stems from the evolution of routing researc…
Dijkstra-WSA: A Graph-Based Approach to Word Sense Alignment
In this paper, we present Dijkstra-WSA, a novel graph-based algorithm for word sense alignment. We evaluate it on four different pairs of lexical-semantic resources with different characteristics (WordNet-OmegaWiki, Word…
Semantic ParsingSemantic Role LabelingWord Sense DisambiguationEfficient Planning in Large-scale Systems Using Hierarchical Finite State Machines
We consider optimal planning in a large-scale system formalised as a hierarchical finite state machine (HFSM). A planning algorithm is proposed computing an optimal plan between any two states in the HFSM, consisting of …