Combinatorial approach to spreading processes on networks

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.

arXiv comment13 pages, 12 figures, 1 table

References in corpus (22)

• Statistical physics of social dynamics
• Epidemic processes in complex networks
• The spread of epidemic disease on networks
• The Product Space Conditions the Development of Nations
• Dynamics of Rumor Spreading in Complex Networks
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Thresholds for epidemic spreading in networks
• A message passing approach for general epidemic models
• Inferring the origin of an epidemic with a dynamic message-passing algorithm
• Percolation on sparse networks
• High-accuracy approximation of binary-state dynamics on networks
• Percolation in real interdependent networks
• Bayesian inference of epidemics on networks via Belief Propagation
• Identifying Infection Sources and Regions in Large Networks
• Non-equilibrium dynamics of language games on complex networks
• Obtaining statistics of cascading line outages spreading in an electric transmission network from standard utility data
• Dynamic message-passing equations for models with unidirectional dynamics
• Breaking of the site-bond percolation universality in networks
• Tight lower bound for percolation threshold on a quasi-regular graph
• Epidemics of Liquidity Shortages in Interbank Markets
• Exact solutions for social and biological contagion models on mixed directed and undirected, degree-correlated random networks
• Uncertainty Reduction for Stochastic Processes on Complex Networks