Jordan Center Estimation for Network Diffusion Sources

56 concepts22 papers2 proposals

When a rumor spreads through a social network or a virus moves through a population, investigators are often left with a "snapshot" of the aftermath: a set of infected individuals, but no clear record of how the infection traveled. Identifying "Patient Zero" in these scenarios is a needle-in-a-stack problem, compounded by the fact that the specific parameters of the spread—such as the infection rate or recovery time—are usually unknown.

Research into source localization has converged on a powerful geometric intuition: the most likely origin of a diffusion process is the Jordan center of the infected subgraph. By focusing on the topological midpoint of the spread rather than the global importance of nodes, this approach provides a robust, parameter-agnostic framework for tracing infections back to their roots.

The Intuition of Infection Eccentricity

In a network, the "Jordan center" is the node that minimizes the maximum distance to all other nodes in a specific set. In the context of an epidemic, this means finding the node that has the smallest "infection eccentricity"—the shortest path to the most distant infected individual.

The power of this metric lies in its symmetry. As Luo et al. demonstrate, for tree-structured networks, the Jordan center is mathematically the most probable source of a diffusion process. While traditional centrality measures like degree or betweenness identify nodes that are important to the entire network, the Jordan center focuses specifically on the spatial distribution of the infected cluster. As Tay and Luo argue, minimizing the maximum distance to infected nodes is significantly more accurate than minimizing the average distance, because the boundaries of the infection carry more information about the origin than the nodes in the middle.

Parameter-Agnostic Robustness

A recurring challenge in epidemiology and cybersecurity is that we rarely know the "speed" of a spread before we need to stop it. Most source estimation models require pre-defined spreading rates or propagation variances, which Tang notes are rarely available for emerging threats.

The Jordan center approach bypasses this requirement. Because it relies purely on the topology of the network—the arrangement of links—it is "parameter-agnostic." Luo et al. show that this geometric estimator is "universal," meaning it remains optimal across diverse spreading models, including Susceptible-Infected (SI), Susceptible-Infected-Recovered (SIR), and Susceptible-Infected-Susceptible (SIS). Whether a disease allows for lifelong immunity or constant reinfection, the topological midpoint of the observed snapshot remains the most reliable indicator of the source.

Solving the Sparse Observation Problem

In real-world scenarios, we rarely see every infected node. We might only have a "sparse" sample—perhaps only 10% of infected users reported a rumor. Zhu et al. proved that the Jordan infection center remains a robust estimator even under these conditions. As long as the observations are unbiased, the geometric center of a small fraction of infected nodes still points toward the true origin.

This robustness extends to the temporal stability of the center. Pattathil et al. found that in many growing tree models, the Jordan center eventually "settles" on a single node and stops moving as the network expands. This suggests that the center is not just a temporary fluke of a small outbreak, but a consistent proxy for the starting point as the diffusion matures.

Scaling to Multiple Sources and Complex Graphs

While the Jordan center is naturally suited for single-source spreads on trees, the research has evolved to handle the complexity of real-world networks:

  • Multiple Sources: When an infection starts from several places at once, the problem becomes one of partitioning. Luo et al. proposed the Multiple Sources Estimation and Partitioning (MSEP) algorithm, which uses Voronoi partitions to divide infected nodes into regions, each with its own Jordan center. Similarly, Zhu et al. introduced the Optimal-Jordan-Cover (OJC), which identifies a set of nodes that collectively "cover" the infected population with a minimum radius.
  • Loopy Topologies: Real social networks are full of cycles (loops), which can confuse simple distance metrics. To address this, Figueiredo et al. developed the epicenter estimator, which minimizes the discrepancy between the distances in the observed infection tree and the shortest paths in the underlying graph. By incorporating the structural constraints of the original network, the estimator can distinguish the true origin from nodes that only appear central due to the specific path the infection took.
  • Topographic Prominence: Other methods, like the LPSI algorithm proposed by Wang et al., treat the infection snapshot as a topography. By allowing labels to propagate through the network, sources emerge as "local peaks" of prominence, identifying the centers of infected clusters without needing to know the transmission rules.

By shifting the focus from complex biological modeling to the inherent geometry of network paths, Jordan center estimation provides a fast, effective, and mathematically grounded way to find the start of a spread when time and data are at a premium.

Key Foundational Work

Identifying Infection Sources and Regions in Large Networks (2012) — contributed 1 concept elements to this direction.
Rumors in a Network: Who's the Culprit? (2011) — 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_jordan_center_estimation_0adff49c,
  title = {Jordan center estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/jordan-center-estimation/rdr_0adff49c9cc3458b9201d5f916f16ce1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_jordan_center_estimation_0adff49c_v1,
  title = {Jordan center estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/jordan-center-estimation/rdr_0adff49c9cc3458b9201d5f916f16ce1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake