Eur. Phys. J. B (2021) 94: 15
https://doi.org/10.1140/epjb/s10051-020-00029-z

Regular Article - Statistical and Nonlinear Physics

Combinatorial approach to spreading processes on networks

Center for Complex Networks and Systems Research, Luddy School of Informatics, Computing, and Engineering, Indiana University, 47408, Bloomington, IN, USA

^b filiradi@indiana.edu

Received: 17 August 2020
Accepted: 30 November 2020
Published online: 11 January 2021

Abstract

Stochastic spreading models defined on complex network topologies are used to mimic the diffusion of diseases, information, and opinions in real-world systems. Existing theoretical approaches to the characterization of the models in terms of microscopic configurations rely on some approximation of independence among dynamical variables, thus introducing a systematic bias in the prediction of the ground-truth dynamics. Here, we develop a combinatorial framework based on the approximation that spreading may occur only along the shortest paths connecting pairs of nodes. The approximation overestimates dynamical correlations among node states and leads to biased predictions. Systematic bias is, however, pointing in the opposite direction of existing approximations. We show that the combination of the two biased approaches generates predictions of the ground-truth dynamics that are more accurate than the ones given by the two approximations if used in isolation. We further take advantage of the combinatorial approximation to characterize theoretical properties of some inference problems, and show that the reconstruction of microscopic configurations is very sensitive to both the place where and the time when partial knowledge of the system is acquired.