Inferring the Origin of Network Cascades

27 concepts23 papers2 proposals

Imagine looking at a drop of food coloring fully dispersed in a glass of water and trying to guess exactly where it first hit the surface. In network science, we face a digital version of this problem every day. Whether it is a viral rumor spreading across social media, malware tearing through a corporate intranet, or a pathogen moving through a population, we often only observe the aftermath—a static snapshot of who is infected, or a sparse set of timestamps from a few monitoring stations.

The forward problem—modeling how an infection spreads from a known source—is well-understood. The inverse problem—backtracking from an observed state to find "Patient Zero"—is notoriously difficult. This field, known as epidemic source inference or source localization, develops mathematical and algorithmic frameworks to reverse the arrow of time on graphs.

The Core Challenge: Information Loss and Entropy

Why is finding the source so hard? The primary culprit is entropy. Diffusion processes are inherently stochastic and lossy. As a cascade propagates, different initial configurations can melt into identical final states.

As noted by Bo Zong et al. in Inferring the Underlying Structure of Information Cascades, most traditional cascade analysis tools assume the source is known, leaving a major gap when we only have incomplete observational data. If we only see a snapshot of infected nodes without directional or timing data, every node in the network is a potential candidate.

Mathematically, finding the minimal set of initial nodes (or "effectors") that explains a given network state is a daunting combinatorial problem. In The Complexity of Finding Effectors, Laurent Bulteau et al. formalize this complexity, demonstrating that finding these initial triggers is fundamentally constrained by the stochastic nature of the underlying spread.

Geometric Intuition: Graph Centers as Origins

To build intuition for how we can reverse this process, let's start with the simplest case: a deterministic spread on a tree. If an infection spreads at a constant rate along every edge, the source will naturally sit at the topological "center" of the infected subgraph.

One classic metric is the Jordan center, which minimizes the maximum distance to any other node in the infected set. But what happens as the network grows dynamically? Sarath Pattathil et al. provide a foundational insight in Persistence of the Jordan center in Random Growing Trees: in many random growing tree models, the Jordan center eventually stabilizes and stops moving, locking onto a specific node forever. This "persistence" means that even if we catch a cascade late in its lifecycle, the geometric center remains a highly reliable proxy for the true origin.

Expanding on this, Daniel R. Figueiredo et al. introduced the epicenter estimator in Epicenter of random epidemic spanning trees on finite graphs. By leveraging both the graph structure and the spanning tree of the infection, the epicenter locates origins on finite graphs with remarkable accuracy, even when timing information is completely absent.

Probabilistic Backtracking: Message Passing and Belief Propagation

Real-world networks are rarely clean trees, and transmission delays are highly variable. When the spread is stochastic, geometric centers lose accuracy. Instead, we must compute the posterior probability that a given node is the source, conditioned on the observed state.

Computing this directly requires summing over an exponential number of possible infection pathways. To make this tractable, researchers turn to Dynamic Message-Passing (DMP) and Belief Propagation (BP).

The core intuition behind DMP, as articulated by Lenka Zdeborova et al. in Dynamic message-passing equations for models with unidirectional dynamics, is to exploit the unidirectional (irreversible) nature of dynamics like the Susceptible-Infected-Recovered (SIR) model. Because nodes cannot pass from recovered back to susceptible, the correlations between neighbors are highly constrained. This allows the authors to map an exponentially hard problem into polynomial-time equations.

Further exploring this boundary, Davide Ghio et al. demonstrate in Bayes-optimal inference for spreading processes on random networks that Belief Propagation can achieve Bayes-optimal inference across large parameter regions, providing a tight theoretical bound on our fundamental ability to reconstruct patient zero from a single snapshot. Even under complex dynamics where individuals can relapse—such as the SIRI model—specialized state-space estimators like the HISS algorithm developed by Wee Peng Tay et al. in Network infection source identification under the SIRI model can successfully infer the source by tracking the statistical distribution of states over time.

Signal Processing: Graph Deconvolution and Sparse Recovery

Another powerful way to conceptualize source localization is through the lens of digital signal processing. Imagine the initial source configuration as a "spike"—a sparse signal where only the source node has a value of 1, and all others are 0. The diffusion process acts as a low-pass graph filter, blurring this spike across the network over time.

If we understand the filter, we can try to invert it. In Source Localization on Graphs via l1 Recovery and Spectral Graph Theory, Rodrigo C. G. Pena et al. combined spectral graph theory with $\ell_1$ regularization to solve this. Because we know the true source vector must be highly sparse, minimizing the $\ell_1$ norm allows us to simultaneously pinpoint the source and estimate unknown diffusion parameters from a single snapshot.

Taking this a step further, Chang Ye formulated the problem as a blind deconvolution on graphs in Blind Deconvolution on Graphs: Exact and Stable Recovery. By proving that certain diffusion filters are invertible, the author showed that a simple linear program can achieve exact recovery of both the initial sparse signal and the propagation mechanism without needing prior knowledge of the spread rules.

Active and Adaptive Sensing

What if we do not have a full snapshot, but instead have the budget to deploy a few "sensors" to watch the network? Traditional approaches place sensors statically and wait. However, Brunella Spinelli et al. introduced an online, adaptive approach in Back To The Source: An Online Approach for Sensor Placement and Source Localization. Instead of guessing where to look beforehand, their framework places sensors iteratively while the cascade is actively spreading. By dynamically choosing the most informative nodes based on real-time data, they show that the source can be pinpointed using roughly 3% of the network.

The power of this adaptivity is further detailed by Victor Lecomte et al. in The power of adaptivity in source identification with time queries on the path. They proved that by adaptively querying nodes based on previous arrival times, researchers can drastically mitigate the noise introduced by random edge delays, outperforming static sensor placement by orders of magnitude.

Complex Topologies and Adversarial Contexts

As the field matures, researchers are moving beyond single sources on simple graphs to tackle real-world complexities:

  • Multiple Sources: When an infection breaks out in multiple places at once, we must not only find the sources but also partition the network into "regions of responsibility." Wuqiong Luo et al. addressed this in Identifying Infection Sources and Regions in Large Networks with the Multiple Sources Estimation and Partitioning (MSEP) algorithm, which uses the combinatorial properties of infection sequences to segment the network without knowing the number of sources in advance.
  • Group Transmissions: Diseases like COVID-19 often spread within "social bubbles" (households, events) rather than simple pairwise links. In Social Bubbles and Superspreaders: Source Identification for Contagion Processes on Hypertrees, Sam Spencer modeled these dynamics using hypergraphs, deriving closed-form estimators that bypass expensive simulations to find patient zero in real-time.
  • Adversarial Contexts: In peer-to-peer networks like Bitcoin, source inference can be weaponized. In Deanonymization in the Bitcoin P2P Network, Giulia Fanti et al. demonstrated how an adversary with multiple connections can use relay timestamps to perform epidemic source inference, tracing a transaction back to a user's specific IP address.

Conversely, understanding these backtracking mechanisms allows for better privacy design and more robust attribution of viral events, marketing influence, or misinformation, as explored in work by Jing Tang et al. (Analysis of Influence Contribution in Social Advertising) and Han Xiao et al. (Robust Cascade Reconstruction by Steiner Tree Sampling).

Key Foundational Work

Inferring the Underlying Structure of Information Cascades (2012) — contributed 1 concept elements to this direction.
Information source detection in the SIR model: A sample path based approach (2013) — contributed 1 concept elements to this direction.
Identifying Infection Sources and Regions in Large Networks (2012) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_epidemic_source_inference_4492038c,
  title = {epidemic source inference},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/epidemic-source-inference/rdr_4492038c2bde443f8118051c83c45b3f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_epidemic_source_inference_4492038c_v1,
  title = {epidemic source inference},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/epidemic-source-inference/rdr_4492038c2bde443f8118051c83c45b3f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake