# Locating the Epidemic Source in Complex Networks with Sparse Observers
## 2 Model and Method
### Problem Definition  
Consider the early-warning mechanism of an epidemic, e.g., influenza. When some new flu starts spreading in a crowd, only a few people realize it is flu and chose to go to the hospital, while most citizens think they have a common cold with no need to go to the hospital. After that, hospital can only collect infection information of the few people and submit it to centers for disease control and prevention. When the number of infectious people exceeds the threshold, on the one hand, the centers for disease control and prevention organize social forces to isolate and treat patients; on the other hand, it is necessary for them to locate the epidemic source using the data from all the hospitals so as to curb the spread of the epidemic.  
In this paper, we focus on an undirected graph \(G=(V,E)\) in which the spread occurs, where \(V\) denotes the set of nodes and \(E\) denotes the set of edges. In particular, the network remains static, which means its topology never changes during the epidemic spread model. The epidemic source \(s^{*}\in V\) represents the only node where the epidemic originates, and it triggers spread at an unknown initial time \(t_{0}\). Furthermore, the spread process associated with a time delay along the edge is considered in our work based on epidemic spread process.  
The spread process is modeled as follows. There are three kinds of node states in network, i.e., Susceptible (S), Infectious (I), and Recovered (R) in SIR spread model. The susceptible nodes represent the citizens who are easily infected but now stay healthy, whereas the infectious nodes represent the individuals who have already been infected and have the ability to infect neighbors. The recovered nodes denote the people who have the antibody after infection, or die. At first, there is only one node \(s^{*}\) in the infectious state and other nodes are all in susceptible state. Let \(\Gamma_{v}\) denote the neighbors of node \(v\) and assume that \(v\) is in the infectious state at time \(t_{v}\). The node \(v\) will infect susceptible neighbors \(\Gamma_{v}\) at the probability of \(\beta\), meanwhile it will recover to the recovered state at the probability of \(\gamma\). Once a node \(u\in\Gamma_{v}\) is infected, its state will change from susceptible state to infectious state and node \(u\) can infect susceptible neighbors. At this time, the infected time of node \(u\) is at \(t_{v}+\theta_{vu}\), where \(\theta_{vu}\) represents the time delay associated with edge \(vu\). Finally, when there is no node in infectious state, the whole spread process terminates.  
Let \(O=\{\theta_{k}\}_{k=1}^{K}\) represent a group of observers whose infected time \(T_{O}=[t_{o_{1}},t_{o_{2}},...,t_{o_{K}}]^{T}\) can be acquired by us. Then the epidemic source localization problem can be described as follows: given the network topology and sparse observers (partial nodes in network), which can report their infected time, our goal is to find the epidemic source \(s_{*}\) in the network. Due to the randomness of the spread process, it is difficult to determine what infected the susceptible nodes before so that we cannot conclude actual spread path, which brings a huge challenge to epidemic source localization. Moreover, the initial time of epidemic spread is impossible to acquire, which increases the difficulty of locating the epidemic source.