Inferring Full Diffusion History from Partial Timestamps

Zhen Chen, Hanghang Tong, Lei Ying

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number8667709
Pages (from-to)1378-1392
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number7
StatePublished - Jul 1 2020
Externally publishedYes


  • Graph mining
  • diffusion

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Inferring Full Diffusion History from Partial Timestamps'. Together they form a unique fingerprint.

Cite this