  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.
