Optimizing testing strategies for early detection of disease outbreaks in animal trade networks via MCMC.

The animal trades between farms and other livestock holdings form a complex livestock trade network. The movement of animals between trade actors plays an important role in the spread of infectious diseases among premises. Particularly, the outbreak of silent diseases that have no clinically obvious symptoms in the animal trade system should be diagnosed by taking special tests. In practice, the authorities regularly conduct examinations on a random number of farms to make sure that there was no outbreak in the system. However, these actions, which aim to discover and block a disease cascade, are yet far from the effective and optimum solution and often fail to prevent epidemics. A testing strategy is defined as making decisions about distributing the fixed testing budget N between farms/nodes in the network. In this paper, first, we apply different heuristics for selecting sentinel farms on real and synthetic pig-trade networks and evaluate them by simulating disease spreading via the SI epidemic model. Later, we propose a Markov chain Monte Carlo (MCMC) based testing strategy with the aim of early detection of outbreaks. The experimental results show that the proposed method can reasonably well decrease the size of the outbreak on both the realistic synthetic and real trade data. A targeted selection of an N/52 fraction of nodes in the real pig-trade network based on the MCMC or simulated annealing can improve the performance of a baseline strategy by 89%. The best heuristic-based testing strategy results in a 75% reduction in the average size of the outbreak compared to that of the baseline testing strategy.