# Catch'Em All: Locating Multiple Diffusion Sources in Networks with Partial Observations

arXiv: https://arxiv.org/abs/1611.06963 · HTML: https://mlsanity.com/paper/1611.06963/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Nov 2016.

## Built on by (most cited first, 16 of 16)

- [Source Localization of Graph Diffusion via Variational Autoencoders for Graph Inverse Problems](https://mlsanity.com/paper/2206.12327/) (2022)
- [Reconstructing Graph Diffusion History from a Single Snapshot](https://mlsanity.com/paper/2306.00488/) (2023)
- [GIN-SD: Source Detection in Graphs with Incomplete Nodes via Positional Encoding and Attentive Fusion](https://mlsanity.com/paper/2403.00014/) (2024)
- [Two-stage Denoising Diffusion Model for Source Localization in Graph Inverse Problems](https://mlsanity.com/paper/2304.08841/) (2023)
- [Schemes of Propagation Models and Source Estimators for Rumor Source Detection in Online Social Networks: A Short Survey of a Decade of Research](https://mlsanity.com/paper/2101.00753/) (2021)
- [Learning the Topology and Behavior of Discrete Dynamical Systems](https://mlsanity.com/paper/2402.11686/) (2024)
- [GraphSL: An Open-Source Library for Graph Source Localization Approaches and Benchmark Datasets](https://mlsanity.com/paper/2405.03724/) (2024)
- [Inference of a Rumor's Source in the Independent Cascade Model](https://mlsanity.com/paper/2205.12125/) (2022)
- [XFlow: Benchmarking Flow Behaviors over Graphs](https://mlsanity.com/paper/2308.03819/) (2023)
- [Backward and Forward Inference in Interacting Independent-Cascade Processes: A Scalable and Convergent Message-Passing Approach](https://mlsanity.com/paper/2310.19138/) (2023)
- [Multiple-Source Localization from a Single-Snapshot Observation Using Graph Bayesian Optimization](https://mlsanity.com/paper/2403.16818/) (2024)
- [Structure-prior Informed Diffusion Model for Graph Source Localization with Limited Data](https://mlsanity.com/paper/2502.17928/) (2025)
- [HyperDet: Source Detection in Hypergraphs via Interactive Relationship Construction and Feature-rich Attention Fusion](https://mlsanity.com/paper/2505.12894/) (2025)
- [SourceDetMamba: A Graph-aware State Space Model for Source Detection in Sequential Hypergraphs](https://mlsanity.com/paper/2505.12910/) (2025)
- [Large language models for spreading dynamics in complex systems](https://mlsanity.com/paper/2602.08085/) (2026)
- [Network World Models as Environments for Algorithm Design on Complex Systems](https://mlsanity.com/paper/2610.01048/) (2026)

## Abstract (arXiv)

This paper studies the problem of locating multiple diffusion sources in networks with partial observations. We propose a new source localization algorithm, named Optimal-Jordan-Cover (OJC). The algorithm first extracts a subgraph using a candidate selection algorithm that selects source candidates based on the number of observed infected nodes in their neighborhoods. Then, in the extracted subgraph, OJC finds a set of nodes that "cover" all observed infected nodes with the minimum radius. The set of nodes is called the Jordan cover, and is regarded as the set of diffusion sources. Considering the heterogeneous susceptible-infected-recovered (SIR) diffusion in the Erdos-Renyi (ER) random graph, we prove that OJC can locate all sources with probability one asymptotically with partial observations. OJC is a polynomial-time algorithm in terms of network size. However, the computational complexity increases exponentially in m, the number of sources. We further propose a low-complexity heuristic based on the K-Means for approximating the Jordan cover, named Approximate-Jordan-Cover (AJC). Simulations on random graphs and real networks demonstrate that both AJC and OJC significantly outperform other heuristic algorithms.