Network Reconstruction from Noisy and Incomplete Spreading Dynamics

Long distance connections in modern interconnected world play an important role in many areas of life, such as information spreading, epidemics, financial contagion or opinion dynamics. This drives the need for proper understanding of diffusion and spreading processes on networks. Another unprecedented feature of current era is the data availability, which, together with rapid development of machine learning tools, allow to learn and predict models from observed processes. In reality, however, these large amounts of data are often incomplete, noisy or biased. We address this problem in the case of spreading processes on networks and propose a general framework, which allow to learn spreading models from data, when the latter is incomplete or subject to uncertainty.

We introduce a computationally efficient algorithm, which allows to learn spreading parameters, together with the network structure, when not only part of the nodes is unobserved, but there is an additional uncertainty regarding the observed part. Since the algorithm is based on a dynamics-message-passing inference method, it is particularly useful in the case of locally tree-like graphs, but we also suggest approaches for a loopy regime. Additionally, we present an effective implementation of the algorithm, which assures linear complexity even for heterogeneous networks and show how the procedure can be improved when an additional information about the process is known.