Bayes-optimal inference for spreading processes on random networks

Abstract

We consider a class of spreading processes on networks, which generalize commonly used epidemic models such as the SIR model or the SIS model with a bounded number of re-infections. We analyse the related problem of inference of the dynamics based on its partial observations. We analyse these inference problems on random networks via a message-passing inference algorithm derived from the Belief Propagation (BP) equations. We investigate whether said algorithm solves the problems in a Bayes-optimal way, i.e. no other algorithm can reach a better performance. For this, we leverage the so-called Nishimori conditions that must be satisfied by a Bayes-optimal algorithm. We also probe for phase transitions by considering the convergence time and by initializing the algorithm in both a random and an informed way and comparing the resulting fixed points. We present the corresponding phase diagrams. We find large regions of parameters where even for moderate system sizes the BP algorithm converges and satisfies closely the Nishimori conditions, and the problem is thus conjectured to be solved optimally in those regions. In other limited areas of the space of parameters, the Nishimori conditions are no longer satisfied and the BP algorithm struggles to converge. No sign of a phase transition is detected, however, and we attribute this failure of optimality to finite-size effects. The article is accompanied by a Python implementation of the algorithm that is easy to use or adapt.

arXiv comment25 pages, 12 figures

References in corpus (11)

• Array Programming with NumPy
• Epidemic processes in complex networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Statistical physics of inference: Thresholds and algorithms
• Locating the Source of Diffusion in Large-Scale Networks
• Inferring the origin of an epidemic with a dynamic message-passing algorithm
• Bayesian inference of epidemics on networks via Belief Propagation
• The zero-patient problem with noisy observations
• Epidemic mitigation by statistical inference from contact tracing data
• Network reconstruction from infection cascades
• A Bayesian generative neural network framework for epidemic inference problems

Cited by in corpus (6)

• Equilibrium in the Computing Continuum through Active Inference
• Statistical Mechanics of Inference in Epidemic Spreading
• Small-Coupling Dynamic Cavity: a Bayesian mean-field framework for epidemic inference
• Evidence of Replica Symmetry Breaking under the Nishimori conditions in epidemic inference on graphs
• Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm
• Inference in Spreading Processes with Neural-Network Priors