distances to infected nodes. Our simulations show that the sample path based estimator is closer to the actual source than the nodes with the maximum infection closeness.

Other related works include: (1) detecting the first adopter of innovations based on a game theoretical model [@SubBer_12] in which the authors derived the MLE but the computational complexity is exponential in the number of nodes, (2) network forensics under the SI model [@MilCarSha_12], where the goal is to distinguish an epidemic infection from a random infection, and (3) geospatial abduction problems (see [@ShaSubSap_11; @ShaSub_11] and references within).

Problem Formulation
===================

The SIR Model for Information Propagation
-----------------------------------------

Consider an undirected graph $G=\{\cal{V},\cal{E}\}$, where $\cal V$ is the set of nodes and $\cal E$ is the set of (undirected) edges. Each node $v\in \cal{V}$ has three possible states: susceptible ($S$), infected ($I$), and recovered ($R$). We assume a time slotted system. Nodes change their states at the beginning of each time slot, and the state of node $v$ in time slot $t$ is denoted by $X_v(t).$ Initially, all nodes are in state $S$ except node $v^*$ which is in state $I$ and is the information source. At the beginning of each time slot, 