Diffusion archeology for diffusion progression history reconstruction.

Area of Science:

• Network Science
• Computational Epidemiology
• Data Science

Background:

• Diffusion processes (e.g., disease, meme spread) are common but often unobservable in real-time.
• Partial or delayed observation necessitates methods for reconstructing diffusion histories.
• Existing methods struggle with incomplete data for accurate historical reconstruction.

Purpose of the Study:

• To develop methods for reconstructing diffusion histories from partial diffusion state snapshots.
• To accurately identify initial spreaders and understand past diffusion dynamics.
• To overcome limitations of unobservable diffusion processes using limited data.

Main Methods:

• Formulation of diffusion history reconstruction as a maximum likelihood problem for discrete-time SEIRS-type models.
• Development of submodularity-based methods and a novel prize-collecting dominating-set vertex cover (PCDSVC) relaxation.
• Designing algorithms with provable performance guarantees for identifying diffusion steps.

Main Results:

• First methods capable of accurately reconstructing complete diffusion histories from real and simulated data.
• Improved identification of initial spreaders compared to existing techniques.
• Demonstrated ability to predict hidden temporal characteristics of diffusion from limited data.

Conclusions:

• Reconstructing diffusion histories from partial data is feasible with advanced modeling and algorithmic approaches.
• The developed methods offer accurate insights into past diffusion events and initial spreader identification.
• This work advances the understanding and prediction of complex diffusion phenomena in various real-world scenarios.