Full diffusion history reconstruction in networks

Diffusion processes in networks can be used to model many real-world processes. Analysis of diffusion traces can help us answer important questions such as the source of diffusion and the role of each node in the diffusion process. However, in large-scale networks, it is very expensive if not impossible to monitor the entire network to collect the complete diffusion trace. This paper considers diffusion history reconstruction from a partial observation and develops a greedy, step-by-step reconstruction algorithm. It is proved that the algorithm always produces a diffusion history that is consistent with the partial observation. Our experimental results based on real networks and real diffusion data show that the algorithm significantly outperforms some existing methods.