# Locating the Epidemic Source in Complex Networks with Sparse Observers
## 2 Model and Method
### An Example in Tree Network  
To better describe implementation process of PESL algorithm, we make some tests of epidemic source localization in a tree network of 12 nodes and 11 edges. Figure 1 shows we simulate the epidemic spread in this network under the SIR model, where infection probability is \(\beta=0.5\), recovery probability is \(\gamma=0.3\), and thus \(\alpha=\beta+\gamma-\beta\gamma=0.65\). Assume node \(h\) is the epidemic source. When initial time is \(t=0\), only this node is infectious; others are all susceptible. Figure 1a-f represent the state of each node in the network at six successive moments, respectively. The nodes in the orange box denote the three observers \(O=[i,e,g]\) and their infected time is \(T_{O}=[1,2,5]\). Without knowing the concrete spread process, we try to locate the epidemic source only by their observers and its infected time.  
Now we introduce the calculation process of PESL algorithm, taking node \(h\) for example. From Figure 1, it is easy to calculate the distance between node \(h\) and each observer:  
\[\begin{cases}d_{h1}=dist(h,i)=1\\ d_{h2}=dist(h,e)=2\\ d_{h3}=dist(h,g)=3\end{cases} \tag{11}\]  
From Equations (8) and (9), for node \(h\), we can confirm the research range of initial time \(t_{0}\):  
\[\begin{cases}t_{0}^{l}=min\left\{1-\left\lfloor\frac{1+0.65-1}{0.65}\right\rfloor,2-\left\lfloor\frac{2+0.65-1}{0.65}\right\rfloor,3-\left\lfloor\frac{3+0.65-1 }{0.65}\right\rfloor\right\}=-2\\ t_{0}^{r}=min\left\{1-1,2-2,5-3\right\}=0\end{cases} \tag{12}\]Next, using Equation (10) to solve optimal initial time \(t_{0}\), when \(\hat{t_{0}}=0\), objective function \(L(h,t_{0}|\mathcal{T}_{O}=T_{O})\) can get the maximum \(-2.89(\hat{t_{0}}=-2,\,L=-7.18;\,\hat{t_{0}}=-1,\,L=-4.84)\).  
Table 1 shows the epidemic source localization result using the PESL algorithm in the tree network. From this result, when \(\hat{t_{0}}=0\), the objective function value of node \(h\) can achieve maximum among all nodes, i.e., this algorithm locates the epidemic source successfully and gets the correct initial time.  
\begin{table}
\begin{tabular}{c c c c c c c c c c c c c} \hline \hline
**MLE** & **a** & **b** & **c** & **d** & **e** & **f** & **g** & **h** & **i** & **j** & **k** & **i** \\ \hline \(\hat{t_{0}}\) & \(-3\) & \(-2\) & \(-3\) & \(-1\) & \(2\) & \(-3\) & \(5\) & \(\mathbf{0}\) & \(1\) & \(-1\) & \(-3\) & \(-3\) \\ \(L_{s}\) & \(-5.69\) & \(-5.94\) & \(-5.69\) & \(-6.84\) & \(-8.02\) & \(-11.58\) & \(-27.90\) & \(-\mathbf{2.89}\) & \(-3.12\) & \(-3.67\) & \(-4.38\) & \(-4.38\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: The results of epidemic source localization in network. Where \(\hat{t_{0}}\) represents the initial time obtained from Equation (10) and \(L_{s}\) is the target function value obtained from Equation (7). The node with the largest objective function value is the epidemic source in the network. For the three observers in the network \((1,e,g)\), use their infected time as the initial time directly.  
Figure 1: Schematic diagram of SIR spread process in a tree network. The time delay of each node all equals \(1\). (**a–f**) respectively represent the states of all nodes in network at six successive moments, among which white represents susceptible, red represents infectious, and purple represents recovered. Node \(h\) is the epidemic source and the initial time is \(t_{0}=0\). At this moment, only this node is infectious and other nodes are all susceptible. As time goes by, more and more nodes change from susceptible to infectious, and the infectious nodes also recover successively. The node in the orange box represents the observer. The goal of PESL algorithm is to locate the epidemic source in the network according to the network topology and observers, which report its infected time.