Abstract
Identifying the source of an outbreak in a network is a critical challenge, often hampered by uncertainty regarding the spreading model and its parameters. This paper demonstrates that the Jordan center—a simple topological measure—is a universal estimator for the infection source. We prove its optimality across SI, SIR, SIRI, and SIS models in tree networks and show its superior performance in complex real-world networks compared to traditional centrality heuristics.
Introduction
When a virus or rumor spreads through a network, we often only observe a snapshot of the infected nodes. To mitigate the spread or understand its origin, finding the "patient zero" is essential. However, existing source-estimation methods typically require precise knowledge of infection and recovery rates—parameters that are rarely available in real-time. This paper addresses this "parameter blindness" by investigating whether a universal, parameter-free estimator exists that works regardless of the spreading model or its specific parameters.
The Jordan Center Approach
The authors propose using the Jordan center as the primary estimator. For a set of infected nodes $V_i$, the Jordan center $s$ is the node that minimizes the maximum distance to any infected node: $$\bar{d}(s, V_i) = \max_{u \in V_i} d(s, u)$$ In simpler terms, it is the node that is "closest" to the furthest infected node. This approach is based on the Most Likely Infection Path (MLIP) criterion. Instead of calculating the probability of all possible infection paths (a computationally difficult task), the MLIP focuses on the single most probable path that could have caused the observed pattern. The Jordan center is purely topological, requiring no information about the specific "rules" of the spread or the rates at which it occurs.
Theoretical Optimality and Universality
A key contribution of this work is the mathematical proof of the Jordan center's optimality in tree networks. The paper shows that for SI, SIR, and SIRI models, the Jordan center remains the optimal MLIP estimator even under heterogeneous conditions where nodes have different infection and recovery rates.
This universality suggests that the network's geometry often dictates the spread's behavior more than the specific biological or social parameters of the agent. While previous work assumed symmetric infection probabilities, these findings hold even in heterogeneous networks where some nodes are much easier to infect than others.
Empirical Performance and Robustness
The researchers evaluated the Jordan center and a proposed Multiple Jordan Center (MJC) algorithm against six common centrality measures (Betweenness, Closeness, Distance, Degree, Eigenvector, and Pagerank) across several datasets:
- Random Tree Networks: Synthetic trees with varying node degrees.
- Facebook Social Graph: A complex network of 4,039 nodes.
- US Power Grid: A high-voltage power grid network.
In all simulations, the Jordan center-based estimators consistently achieved the lowest average error distance (the number of hops between the estimated source and the true source). Remarkably, while the theoretical proofs are grounded in tree structures, the MJC algorithm outperformed all benchmarks on the Facebook and Power Grid networks, which contain numerous cycles and complex structures.
Conclusion and Future Work
The Jordan center provides a robust, parameter-free solution for identifying infection sources. Its universality across various epidemiological models and its strong performance in real-world networks make it a powerful tool for practical applications where data is messy or incomplete.
However, limitations remain. The rigorous mathematical optimality is currently limited to tree structures, and the model assumes full observation of the infected set. Future research will focus on extending proofs to graphs with cycles and addressing scenarios where only a small fraction of the infected population is visible.
Summary updated