Diffusion Archaeology: Peering into the Past of Network Spreads

TL;DR

Diffusion processes—whether they are viral memes, water contaminants, or infectious diseases—rarely leave a full paper trail. Most of the time, we only catch a "snapshot" of the current state. This paper introduces a mathematically rigorous way to perform Diffusion Archaeology: reconstructing the entire timeline from start to finish using submodular optimization and novel vertex cover relaxations.

The Motivation: Why History Matters

Identifying "Patient Zero" is a classic problem, but knowing how the infection reached the current state is equally critical for forensic analysis and future prevention. Existing methods like Rumor Centrality or Keffectors are often "blind" to the intermediate path or require knowing exactly how many sources started the spread.

The authors argue that we shouldn't just guess the source; we should find the most likely sequence of events that satisfies the biological or social "rules" of the network (modeled by SEIRS dynamics).

Methodology: Mining the Likelihood

The core innovation lies in treating the diffusion history as a Maximum Likelihood Estimate (MLE) problem.

1. The Submodularity Insight

The authors prove that the log-likelihood of a diffusion step (moving from state $X_j$ to $X_{j+1}$) is a non-monotone submodular function. In the world of optimization, submodularity is the "discrete equivalent of concavity." This property allows the authors to use greedy algorithms with provable approximation guarantees (specifically a $1/3$ ratio for normalized functions).

Figure: SEIRS state transitions (Susceptible $\to$ Exposed $\to$ Infected $\to$ Recovered $\to$ Susceptible).

2. Scaling Up: PCDSVC Relaxations

Submodular maximization is computationally expensive on large graphs. To solve this, the authors apply a First-order Taylor Expansion to the log-likelihood, transforming a complex non-linear problem into a combinatorial one: Prize Collecting Dominating Set Vertex Cover (PCDSVC).

• The "Prize": The likelihood of a node being in a specific state.
• The "Cover": Ensuring that every infected node must have had a source (inter-consistency).

Experiments & SOTA Results

The researchers tested their "Archaeology" on diverse datasets:

• Synthetic Data: Erdös-Reyni and Forest Fire models.
• Meme Diffusion: Tracking topics like "Fukushima" and "Arab Spring" across blog networks.
• Water Contamination: Real-world pipe networks (EPANET).

Performance Highlights

• History Accuracy: Using the Kendall Tau-b ($a{u}_B$) metric, the DHR-sub method consistently achieves scores near 0.8-0.9, significanly higher than simple forward-simulated heuristics.
• Scalability: While the DHR-sub algorithm takes over an hour on a 90k node grid, the DHR-pcdsvc relaxation finishes in about 10 minutes with only a minor dip in accuracy.

Figure: Reconstructing the speed and acceleration of meme spreads from just 3 snapshots.

Critical Analysis: The Limits of Archaeology

While the methods are robust, they still rely on knowing the underlying diffusion parameters ($p_{uv}$). The authors show that we can "borrow" parameters from semantically similar memes (e.g., using "Earthquake" data to reconstruct "Fukushima"), but if the underlying model is unknown, the reconstruction quality degrades.

Furthermore, while the relaxation methods are fast, the authors admit that million-node graphs still pose a challenge, suggesting a need for even more aggressive localized heuristics or distributed solvers.

Conclusion

"Diffusion Archaeology" proves that partial data isn't a dead-end. By leveraging the mathematical structure of the SEIRS model, we can reconstruct the "unseen" past with surprising precision. This has massive implications for public health (disease tracing), cybersecurity (virus origin), and social media analysis (meme evolution).