Network reconstruction from infection cascades

Abstract

Accessing the network through which a propagation dynamics diffuse is essential for understanding and controlling it. In a few cases, such information is available through direct experiments or thanks to the very nature of propagation data. In a majority of cases however, available information about the network is indirect and comes from partial observations of the dynamics, rendering the network reconstruction a fundamental inverse problem. Here we show that it is possible to reconstruct the whole structure of an interaction network and to simultaneously infer the complete time course of activation spreading, relying just on single epoch (i.e. snapshot) or time-scattered observations of a small number of activity cascades. The method that we present is built on a Belief Propagation approximation, that has shown impressive accuracy in a wide variety of relevant cases, and is able to infer interactions in presence of incomplete time-series data by providing a detailed modeling of the posterior distribution of trajectories conditioned to the observations. Furthermore, we show by experiments that the information content of full cascades is relatively smaller than that of sparse observations or single snapshots.

18 pages, 10 figures (main text: 13 pages, 9 figures; Appendix: 4 pages, 1 figure)

References in corpus (12)

• What's in a crowd? Analysis of face-to-face behavioral networks
• A message passing approach for general epidemic models
• Data Based Identification and Prediction of Nonlinear and Complex Dynamical Systems
• Information dynamics shape the networks of Internet-mediated prostitution
• Bayesian inference of epidemics on networks via Belief Propagation
• Reconstructing propagation networks with natural diversity and identifying hidden sources
• Revealing networks from dynamics: an introduction
• Model-free inference of direct network interactions from nonlinear collective dynamics
• Containing epidemic outbreaks by message-passing techniques
• Identifying spatial invasion of pandemics on metapopulation networks via anatomizing arrival history
• Large deviations of cascade processes on graphs
• The zero-patient problem with noisy observations

Cited by in corpus (9)

• Network reconstruction and community detection from dynamics
• A Bayesian generative neural network framework for epidemic inference problems
• Layer reconstruction and missing link prediction of multilayer network with a Maximum A Posteriori estimation
• Network reconstruction via the minimum description length principle
• Detecting Hidden Layers from Spreading Dynamics on Complex Networks
• Bayes-optimal inference for spreading processes on random networks
• Reconstruction of C&C Channel for P2P Botnet
• Discovering hidden layers in quantum graphs
• Social Diffusion Sources Can Escape Detection