this problem has many important applications, and can help us answer the following questions: who is the rumor source in online social networks? which computer is the first one infected by a computer virus? who is the one who uploaded contraband materials to the Internet? and where is the source of an epidemic?

We call this problem information source detection problem. This information source detection problem has been studied in [@ShaZam_10; @ShaZam_11; @ShaZam_12] under the Susceptible-Infected (SI) model, in which susceptible nodes may be infected but infected nodes cannot recover. The authors formulated the problem as a maximum likelihood estimation (MLE) problem, and developed novel algorithms to detect the source.

In this paper, we adopt the Susceptible-Infected-Recovered (SIR) model, a standard model of epidemics [@Bai_75; @EasKle_10]. The network is assumed to be an undirected graph and each node in the network has three possible states: susceptible ($S$), infected ($I$), and recovered ($R$). Nodes in state $S$ can be infected and change to state $I$, and nodes in state $I$ can recover and change to state $R$. Recovered nodes cannot be infected again. We assume that initially all nodes are in the susceptible state except one infected node (called the information 