Inferring Full Diffusion History from Partial Timestamps

Understanding diffusion processes in networks has emerged as an important research topic because of its wide range of applications. Analysis of diffusion traces can help us answer important questions such as the source(s) of diffusion and the role of each node during the diffusion process. However, in large-scale networks, due to the cost and privacy concerns, it is almost impossible to monitor the entire network and collect the complete diffusion trace. In this paper, we tackle the problem of reconstructing the diffusion history from a partial observation. We formulate the diffusion history reconstruction problem as a maximum a posteriori (MAP) problem and prove the problem is NP-hard. Then, we propose a step-by-step reconstruction algorithm, which can always produce a diffusion history that is consistent with the partial observation. Our experimental results based on synthetic and real networks show that the algorithm significantly outperforms some existing methods.