Introduction
Identifying the source of an epidemic—the "Patient Zero"—is a critical task in public health, cybersecurity, and social science. Whether tracking a biological virus, a computer worm, or the spread of misinformation, knowing where an outbreak began allows for targeted interventions and a better understanding of transmission dynamics. However, this task is complicated by the stochastic nature of spreading processes and the fact that observers often only have access to a partial "snapshot" of the network's state at a single point in time.
The Dynamic Message-Passing Approach
Traditional methods for source identification often rely on graph centrality measures, such as Jordan centrality, which identify the "geometric center" of the infected cluster. These heuristics frequently fail because they ignore the temporal dynamics of the infection and the valuable information provided by nodes that remain uninfected.
To address these limitations, researchers have developed a Dynamic Message-Passing (DMP) algorithm. This approach leverages the physics of the Susceptible-Infected-Recovered (SIR) model. Unlike standard Belief Propagation, which seeks a steady state, DMP equations track the actual time-steps of the epidemic. By calculating the marginal probability of each node being in a specific state at any given time, the algorithm can use Bayesian inference to rank every node in the network by the likelihood that it was the original source.
Experimental Results
The DMP algorithm was evaluated across various network topologies, including Random Regular, Erdős-Rényi, and Scale-Free graphs, as well as real-world data from the U.S. West-Coast Power Grid.
A key finding is the algorithm's robustness to incomplete data. Even when the health status of a large majority of the population is unknown, DMP effectively utilizes "negative information"—the presence of susceptible nodes—to narrow down the source's location. Furthermore, the algorithm can accurately estimate the time elapsed since the start of the outbreak by maximizing a partition function.
Discussion and Limitations
While DMP shows superior performance, it does encounter a "hard" regime. When the infection rate $\lambda$ is extremely high, the epidemic spreads so rapidly that the network effectively "forgets" its origin, making inference difficult for any method. Additionally, while highly effective on sparse networks, the algorithm's accuracy may decrease in "cliquey" networks where the assumption of uncorrelated marginals is less valid.
Conclusion
The Dynamic Message-Passing algorithm represents a significant advancement in epidemic source inference. By incorporating the underlying dynamics of the SIR model and utilizing the full information available in a snapshot, it provides a more accurate and robust solution than traditional graph-theoretic heuristics. Future work will explore extending this framework to handle multiple sources and dynamic network structures.
Summary updated