On the Universality of Jordan Centers for Estimating Infection Sources in Tree Networks

Wuqiong Luo, Wee-Peng Tay, Mei Leng

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.

Figure 1: Parameter regions (α, β) where the Jordan center maintains optimality for infection source estimation, illustrating its robustness to parameter uncertainty.

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.

Figure 2: Analysis of the estimator's performance across a broader range of infection and recovery parameters, demonstrating consistent accuracy.

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

Abstract

Finding the infection sources in a network when we only know the network topology and infected nodes, but not the rates of infection, is a challenging combinatorial problem, and it is even more difficult in practice where the underlying infection spreading model is usually unknown a priori. In this paper, we are interested in finding a source estimator that is applicable to various spreading models, including the Susceptible-Infected (SI), Susceptible-Infected-Recovered (SIR), Susceptible-Infected-Recovered-Infected (SIRI), and Susceptible-Infected-Susceptible (SIS) models. We show that under the SI, SIR and SIRI spreading models and with mild technical assumptions, the Jordan center is the infection source associated with the most likely infection path in a tree network with a single infection source. This conclusion applies for a wide range of spreading parameters, while it holds for regular trees under the SIS model with homogeneous infection and recovery rates. Since the Jordan center does not depend on the infection, recovery and reinfection rates, it can be regarded as a universal source estimator. We also consider the case where there are k>1 infection sources, generalize the Jordan center definition to a k-Jordan center set, and show that this is an optimal infection source set estimator in a tree network for the SI model. Simulation results on various general synthetic networks and real world networks suggest that Jordan center-based estimators consistently outperform the betweenness, closeness, distance, degree, eigenvector, and pagerank centrality based heuristics, even if the network is not a tree.
BibTeX
@article{luo2014universality,
  author = {Wuqiong Luo and Wee-Peng Tay and Mei Leng},
  title = {{On the Universality of Jordan Centers for Estimating Infection Sources in Tree Networks}},
  journal = {IEEE Trans. Information Theory},
  year = {2014},
  doi = {10.1109/tit.2017.2698504},
}
Figure