  Given an aftermath of a cascade in the network, i.e. a set $V_I$ of
"infected" nodes after an epidemic outbreak or a propagation of
rumors/worms/viruses, how can we infer the sources of the cascade? Answering
this challenging question is critical for computer forensic, vulnerability
analysis, and risk management. Despite recent interest towards this problem,
most of existing works focus only on single source detection or simple network
topologies, e.g. trees or grids.
  In this paper, we propose a new approach to identify infection sources by
searching for a seed set $S$ that minimizes the \emph{symmetric difference}
between the cascade from $S$ and $V_I$, the given set of infected nodes. Our
major result is an approximation algorithm, called SISI, to identify infection
sources \emph{without the prior knowledge on the number of source nodes}. SISI,
to our best knowledge, is the first algorithm with \emph{provable guarantee}
for the problem in general graphs. It returns a
$\frac{2}{(1-\epsilon)^2}\Delta$-approximate solution with high probability,
where $\Delta$ denotes the maximum number of nodes in $V_I$ that may infect a
single node in the network. Our experiments on real-world networks show the
superiority of our approach and SISI in detecting true source(s), boosting the
F1-measure from few percents, for the state-of-the-art NETSLEUTH, to
approximately 50\%.
