Locating the Epidemic Source in Complex Networks with Sparse Observers

Abstract

Epidemic source localization is one of the most meaningful areas of research in complex networks, which helps solve the problem of infectious disease spread. Limited by incomplete information of nodes and inevitable randomness of the spread process, locating the epidemic source becomes a little difficult. In this paper, we propose an efficient algorithm via Bayesian Estimation to locate the epidemic source and find the initial time in complex networks with sparse observers. By modeling the infected time of observers, we put forward a valid epidemic source localization method for tree network and further extend it to the general network via maximum spanning tree. The numerical analyses in synthetic networks and empirical networks show that our algorithm has a higher source localization accuracy than other comparison algorithms. In particular, when the randomness of the spread path enhances, our algorithm has a better performance. We believe that our method can provide an effective reference for epidemic spread and source localization in complex networks.

1. Introduction

Epidemic spread [1,2] in complex networks is an important topic with significant value to help us better understand the spread law and influence scope of contagion. In fact, epidemic is a serious threat to human safety, and it is a new one, drawing research attention. If leaders can identify the epidemic source in time, they prefer to make the right decision and avoid greater harm. To protect citizens from epidemic harm, there is an urgent need for us to develop efficient methods to locate the epidemic source with higher accuracy.

In the past ten years, the source localization problem has attracted many scholars’ attention and some good works have been done, but remains still a challenge. Shah et al. [3] first proposed a rumor centrality, as maximum likelihood estimation of single-source, in tree network under SI model. Inspired by Shah, Zhu et al. [4] studied the source localization problem under the SIR model and presented a Jordan centrality. The node with the smallest Jordan centrality is a source, i.e., the largest distance between source to all infectious nodes remains the least. A similar concept, namely distance centrality, means the sum distance between one node and other all infectious nodes. The source always has the smallest distance centrality. Fioriti et al. [5] calculated the dynamical age of each node based on the importance of node dynamical. They considered the eigenvalue drop rate of the adjacency matrix as dynamical age when a node was eliminated from this network and the sources are the nodes with highest dynamical age. Based on the SIR model and incomplete node information, Zang et al. [6] proposed an advanced unbiased betweenness algorithm. They used a reverse propagation algorithm to build an extended infection graph and marked off several infection subgraphs where we can identify the source with the highest unbiased betweenness.

The above methods consider the location information of all nodes or most nodes in complex networks and the location information and time information of sparse observers can also achieve a satisfactory source localization accuracy. The information source localization method based on observer placement was presented by Pinto [7], called the Gaussian-based method. They calculated the likelihood of each node when it is considered to be the source using the data from observers. The larger the likelihood, the higher probability the node became the source with. Shen et al. [8] investigated a universal method, constructing a virtual backward diffusion tree to locate the source, called Time-Reversal Backward Spreading. By calculating the time of each node when observers reach it reversely, they chose the node with smallest variance as source. Furthermore, Huang et al. [9] extended and applied it in temporal network. For multiple source localization, Fu et al. [10] proposed a maximum–minimum strategy based on backward diffusion, which has been further extended by Hu et al. [11] via integer programming.

Moreover, Brockmann et al. [12] presented the equivalent distance concept, changing the disease-spread problem to a plane wave diffusion process. The source is in the middle of plane wave. Nino Antulov-Fantulin et al. [13] proposed a new source localization method-based Monte-Carlo simulation under the SIR model, through a lot of simulations. Based on source identification algorithm, Wang et al. [14] presented label propagation, where they set up the initial label, propagated the label, and chose the nodes with the tallest labels as the sources.

In this paper, we present the Pascal-based Epidemic Source Localization (PESL) algorithm as a simple and efficient framework for locating the epidemic source and finding the initial time in complex networks with sparse observers. We mainly consider the SIR spread model with time delay and provide a probabilistic method to locate the epidemic source via Bayesian Estimation and Maximum Likelihood Estimation. Simply speaking, we derived an optimal solution of the source localization problem in tree networks and extended to general networks. The experiments show that in synthetic networks and empirical networks, our algorithm has a better performance than other comparison algorithms.

2. Model and Method

In this section, we will provide a detailed description for the epidemic source localization algorithm. First, we will give a brief introduction to epidemic source localization problem formulation; for a tree network, we will next put forward PESL algorithm as a Bayesian and Maximum Likelihood estimator that can simultaneously estimate the probability that a node becomes the epidemic source and the initial time; finally, we will give an example in the tree network.

2.1. 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 ${\mathsf{\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 ${\mathsf{\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 {\mathsf{\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={\{o_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.

2.2. Locating the Epidemic Source in Tree Network

Following the relevant definitions in graph theory, tree is a graph where there is only one path between any two vertices or a connected graph without circuit. If a connected subgraph exists in the original network containing all nodes without circuit, this subgraph is a maximum spanning tree of the original network. Next we research the epidemic source localization problem.

2.2.1. Infected Time Modeling

Consider the case of a tree network. Obviously, studying the epidemic spread problem in tree has a huge advantage because there is only one path between the source and each observer. Recall that $O={\{o_k\}}_{k=1}^K$ is a set of K observers with infected time $T_O={[t_{o_1},t_{o_2},...,t_{o_K}]}^T$. Since the time delay $\{{\theta }_{vu}\}$ along edges are random variables, the infected time $\{{\tau }_{sk}\}$ of observers can also be seen as random variables. Suppose that the value of ${\theta }_{vu}$ can be all positive integers ${\theta }_{vu}\in {\mathbb{Z}}_{+}$ and we next discuss the distribution of random variable ${\theta }_{vu}$.

$$\left\{\begin{array}{cc}\hfill P({\theta }_{vu}=1)& =\frac{1}{Z}·\beta \hfill \\ \hfill P({\theta }_{vu}=2)& =\frac{1}{Z}·\beta (1-\beta )(1-\gamma )\hfill \\ & ⋮\hfill \\ \hfill P({\theta }_{vu}=k)& =\frac{1}{Z}·\beta {(1-\beta )}^{k-1}{(1-\gamma )}^{k-1}\hfill \end{array}\right.$$

(1)

where $\beta$ and $\gamma$ denote infection probability and recovery probability respectively and Z means normalized factor, which can be calculated directly:

$$\begin{array}{cc}\hfill Z& =\beta +\beta (1-\beta )(1-\gamma )+\beta {(1-\beta )}^2{(1-\gamma )}^2+...\hfill \\ & =\frac{\beta }{\beta +\gamma -\beta \gamma }\hfill \end{array}$$

(2)

Let $\alpha =\beta +\gamma -\beta \gamma$, so the distribution of random variable ${\theta }_{vu}$ can be simplified to $P({\theta }_{vu}=k)=\alpha {(1-\alpha )}^{k-1}$ that is: ${\theta }_{vu}$ is a random variable obeying geometric distribution ${\theta }_{vu}\sim Geo(\alpha )$.

Suppose one node s in network and it does not belong to observers $s\in V\backslash O$. If node s is the epidemic source in network, for one observer $o_k$, its infected time ${\tau }_{sk}$ should be the sum of the initial time $t_0$ and all time delay ${\theta }_{vu}$ on the path from node s to node $o_k$.

$${\tau }_{sk}=t_0+\sum _{\overline{vu}\in \mathcal{P}(s,o_k)}{\theta }_{vu}$$

(3)

where $\mathcal{P}(s,o_k)\subset E$ denotes the path from node s to node $o_k$. Thanks for the tree we consider, the path is unique.

Due to all random variables ${\theta }_{vu}$ with independent identical distribution ${\theta }_{vu}\stackrel{i.i.d.}{\sim }Geo(\alpha )$, we can find the infected time ${\tau }_{sk}$ of node $o_k$ actually obeys a Pascal distribution after translation transformation, i.e., ${\tau }_{sk}\sim t_0+NB(d_{sk},\alpha )$, its probability density function shows:

$$P({\tau }_{sk}=t_0+r_{sk}|s,t_0)=C_{r_{sk}-1}^{d_{sk}-1}{\alpha }^{d_{sk}}{(1-\alpha )}^{r_{sk}-d_{sk}},r_{sk}\ge d_{sk}$$

(4)

where $C_b^a=\frac{b!}{a!(b-a)!}$ represents the number of combinations and $d_{sk}$ denotes the length of path $\mathcal{P}(s,o_k)$.

2.2.2. Parameter Estimation of S

Let ${\mathcal{T}}_O=[{\tau }_{s1},{\tau }_{s2},...,{\tau }_{sK}]$, so the posterior probability of node s as epidemic source shows:

$$P(s,t_0|{\mathcal{T}}_O=T_O)=\frac{P({\mathcal{T}}_O=T_O|s,t_0)P(s,t_0)}{P({\mathcal{T}}_O=T_O)}$$

(5)

Suppose that there is no prior knowledge of the epidemic source and the observers, i.e., the probability of any node as the epidemic source in the network keeps equal and the probability that any node becomes an observer is equal too. Then the following derivation can be obtained.

$$\begin{array}{c}\hfill P(s,t_0|{\mathcal{T}}_O=T_O)\propto P({\mathcal{T}}_O=T_O|s,t_0)\approx \prod _{o_k\in O}P({\tau }_{sk}=t_{o_k}|s,t_0)\end{array}$$

(6)

Let $L(s,t_0|{\mathcal{T}}_O=T_O)={\sum }_{o_k\in O}logP({\tau }_{sk}=t_{o_k}|s,t_0)$, so the epidemic source localization problem can be transformed into following optimization problem.

$$(\widehat{s},\widehat{t_0})=\underset{s\in V,t_0\in \mathbb{Z}}{argmax}L(s,t_0|{\mathcal{T}}_O=T_O)$$

(7)

To solve this optimization problem, we first calculate initial time $\widehat{t_0}={argmax}_{t_0\in \mathbb{Z}}L(s,t_0|{\mathcal{T}}_O=T_O)$ of each node s and then drag in Equation (7) to get the objective function value $L(s,\widehat{t_0}|{\mathcal{T}}_O=T_O)$. And the node with the maximum objective function value is the epidemic source in network.

When the network is not a tree but a general network, the first idea is to build a maximum spanning tree and then locate the epidemic source same as before. Considering that the epidemic spread between nodes prefers to occur in a shorter path, we can build a BFS tree randomly and then find the node with maximum objective function as the epidemic source. In fact, from Equation (4), it is even unnecessary to actually construct these BFS trees. If only the distance $d_{sk}$ between node s and each observer $o_k$ is known, parameter estimation and likelihood probability can be calculated. As the core of the whole algorithm is to optimize the Pascal distribution, it is called the Pascal-based Epidemic Source Localization algorithm (PESL).

2.3. Initial Time Range Confirmation

In the PESL algorithm, the key procedure is calculating initial time $\widehat{t_0}={argmax}_{t_0\in \mathbb{Z}}L(s,t_0|{\mathcal{T}}_O=T_O)$ of one node s. Theoretically, the range of $t_0$ is all integers $t_0\in \mathbb{Z}$. We may research all possible $t_0$, which is not realistic because of its high computational complexity, however. Therefore, we must shrink the range of $t_0$ through a certain method.

On the one hand, from Equation (4), for any observer $o_k$, in equation $r_{sk}=t_{o_k}-t_0\ge d_{sk}$ sets up all the tie, we next get

$$t_0\le \underset{o_k\in O}{min}\left\{t_{o_k}-d_{sk}\right\}$$

(8)

On the other hand, from the properties of Pascal distribution, for a random variable $X\sim NB(r,p)$ subject to Pascal distribution, when $X=⌊r+\frac{(1-p)(r-1)}{p}⌋=⌊\frac{r+p-1}{p}⌋$, the corresponding probability density function can be maximized.

Therefore, the maximum of probability density function is $r_{sk}=⌊\frac{d_{sk}+\alpha -1}{\alpha }⌋$ in Equation (4) that is: $t_0=t_{o_k}-r_{sk}=t_{o_k}-⌊\frac{d_{sk}+\alpha -1}{\alpha }⌋$. Inspired, narrow the research range further of $t_0$

$$t_0\ge \underset{o_k\in O}{min}\left\{t_{o_k}-⌊\frac{d_{sk}+\alpha -1}{\alpha }⌋\right\}$$

(9)

Let $t_0^l={min}_{o_k\in O}\left\{t_{o_k}-⌊\frac{d_{sk}+\alpha -1}{\alpha }⌋\right\}$, $t_0^r={min}_{o_k\in O}\left\{t_{o_k}-d_{sk}\right\}$, we just find the optimal initial time $t_0$ from $[t_0^l,t_0^l+1,...,t_0^r]$ that is

$$\widehat{t_0}=\underset{t_0^l\le t_0\le t_0^r,t_0\in \mathbb{Z}}{argmax}L(s,t_0|{\mathcal{T}}_O=T_O)$$

(10)

2.4. 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:

$$\left\{\begin{array}{cc}\hfill d_{h1}& =dist(h,i)=1\hfill \\ \hfill d_{h2}& =dist(h,e)=2\hfill \\ \hfill d_{h3}& =dist(h,g)=3\hfill \end{array}\right.$$

(11)

From Equations (8) and (9), for node h, we can confirm the research range of initial time $t_0$:

$$\left\{\begin{array}{cc}\hfill t_0^l& =min\left\{1-⌊\frac{1+0.65-1}{0.65}⌋,2-⌊\frac{2+0.65-1}{0.65}⌋,3-⌊\frac{3+0.65-1}{0.65}⌋\right\}=-2\hfill \\ \hfill t_0^r& =min\left\{1-1,2-2,5-3\right\}=0\hfill \end{array}\right.$$

(12)

Next, using Equation (10) to solve optimal initial time $t_0$, when $\widehat{t_0}=0$, objective function $L(h,t_0|{\mathcal{T}}_O=T_O)$ can get the maximum −2.89($\widehat{t_0}=-2$, $L=-7.18$; $\widehat{t_0}=-1$, $L=-4.84$).

Table 1. The results of epidemic source localization in network. Where ${\widehat{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 $(I,e,g)$, use their infected time as the initial time directly.

MLE	a	b	c	d	e	f	g	h	i	j	k	i
${\widehat{t}}_0$	$-3$	−2	−3	−1	2	−3	5	0	1	−1	−3	−3
$L_s$	−5.69	−5.94	−5.69	−6.84	−8.02	−11.58	−27.90	−2.89	−3.12	−3.67	−4.38	−4.38

shows the epidemic source localization result using the PESL algorithm in the tree network. From this result, when $\widehat{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.

3. Experiments and Analysis

In the previous section, the solving process of the epidemic source localization problem under the SIR model has been elaborated in detail. This section comprehensively analyzes the performance of PESL algorithm and other common source localization algorithms, and verifies the performance of the algorithms in synthetic networks and empirical networks, respectively.

To get closer to the epidemic source localization in the real world, the classic SIR model is used in the network to simulate spread process. The infection probability is set as $\beta$ and recovery probability as $\gamma$. A node is randomly selected as the epidemic source. Once a susceptible node is infected by a neighbor node, it will report its own state at the probability of $\delta$, which is called the observer. When the number of observers in the network reaches a threshold K, the algorithm needs to locate the epidemic source backward according to the infected time of these observers. To verify the performance of the algorithm, Distance Centrality (DC) [4], Jordan Centrality (JC) [4], Gaussian-based method (GAU) [7] and Time-Reversal Backward Spreading (TRBS) [8] were selected as comparison algorithms. DC and JC only use the location information of observers, while GAU and TRBS comprehensively use the location information of observers and infection time information to locate the epidemic source.

In this paper, we chose average error distance [15] as the evaluation index, which was described as follows. The average error distance is referred as the mean shortest distance of hops between the accurate source and estimated source found by an algorithm. The shorter average error distance is, the higher the accuracy becomes.

3.1. Source Localization Accuracy in Synthetic Networks

In this section, we mainly consider the source localization performance of the algorithm in two synthetic tree networks, namely ER tree (Erdös-Rényi tree, ERT) and BA tree (Barabási-Albert tree, BAT). These two networks are generated by random network (ER) and scale-free network (BA) respectively, which are all connected networks.

To generate BAT, we first make the initial network contain only one isolated node, then add one node at a time and add an edge according to the preference attachment rule in the BA model. Relatively speaking, it is very difficult to directly use ER model to generate a connected tree network with N nodes. Although $n-1$ edges can be randomly generated among the N nodes, there is no guarantee that the generated network is a connected network. Therefore, a compromise is adopted here: First, generate a ER network with $1.5N$ node and 1 average degree; then, if the giant component in the network has N nodes (through the vast simulations, we do find the giant component), take the maximum spanning tree as the approximation of ERT. The basic topological properties of these two tree networks are shown in

Table 2. Basic topological properties of two tree networks. Where $N,M$ represent the number of nodes and edges respectively, $〈k〉$ and $k_{max}$ denote the average degree and maximum degree respectively, H means index of degree heterogeneity in network and $〈d〉$ is the mean shortest path in network.

Type	Name	N	M	$〈\mathit{k}〉$	${\mathit{k}}_{\mathbf{max}}$	H	$〈\mathit{d}〉$
Erdös-Rènyi Tree	ERT	100	99	1.980	5	1.240	9.855
Barabási-Albert Tree	BAT	100	99	1.980	22	2.372	4.945

.

Figure 2 shows the source localization performance under various infection probabilities with five various algorithms in ERT and BAT. In ERT, the epidemic source localization accuracy of PESL algorithm is consistently better than other comparison algorithms. In BAT, PESL algorithm can still achieve good performance of source localization, which reflects the advantages of PESL algorithm on the source localization in ERT and BAT. Intuitively speaking, the larger the infection probability $\beta$ under the SIR model is, the earlier the infected time of the nodes near the epidemic source will be, so the infected time of the observers will be closer to the initial time and a better source localization algorithm should have higher accuracy. It can be found from the results in the figure that the localization accuracy of GAU, TRBS, and PESL increases with the increasing of infection probability, while DC and JC, which only use the location information of nodes, do not show such a trend.

The relationship between source localization performance and reporting probability of different source localization algorithms in two kinds of tree networks is shown in Figure 3. It is easy to see that PESL algorithm is still the most competitive source localization algorithm. Especially when the infection probability $\beta$ is very small, the performance of PESL algorithm is significantly better than other comparison algorithms, indicating that PESL algorithm can well deal with the influence of randomness in the spread process. As can be seen from Figure 3c and Figure 3f, when the infection probability $\beta$ is large, the randomness in the spread process decreases significantly and at this time, PESL algorithm cannot well reflect its advantages. On the other hand, with the same infection probability, the larger the reporting probability $\delta$ is, the closer the observers will be to the epidemic source, the less randomness brought by the observer will be and the gap between PESL algorithm and other algorithms will be further narrowed. In general, the results in Figure 3 indirectly indicate the applicability of PESL algorithm: as reporting randomness of source localization problem increases, the advantages of PESL algorithm will be more obvious compared with other algorithms.

The relationship between the performance of source localization algorithm and the number of observers is shown in Figure 4. In the visual impression of people, the more the number of observers is, the more accurate the source localization accuracy will be. However, the results in the figure are not like this: there is no obvious tendency between source localization accuracy of GAU, TRBS, PESL, and the number of observers; The localization accuracy of DC and JC declines as the number of observers increases. This means the information provided by observers in network has a lot of redundancy, as shown in Figure 1. Because node e reports the infected time after node i, and node g only can be infected by node e, even if we have known the infected time of node g, it has no ability to provide any useful information for source localization, which is called information redundancy. In a tree network, as the number of observers increases, a great source localization algorithm should perform as stably as possible. From this point of view, PESL algorithm has the strongest stability, i.e., it behaves best.

3.2. Parameter Estimation Accuracy

Considering that PESL algorithm can estimate the initial time while locating the epidemic source, we further study MSE of the initial time with different infection probabilities and reporting probabilities in ERT and BAT. Figure 5 shows the mean square error of the initial time $t_0$ of our algorithm. The lower the mean square error is, the more accurate the estimate will be. It can be seen from the results that the MSE of $t_0$ is positively correlated with the infection probability $\beta$ and the reporting probability $\delta$. When the infection probability $\beta$ or the reporting probability $\delta$ increases, the estimation accuracy of the initial time will also increase.

3.3. Algorithm Performance under Unknown Parameters

In the previous experiment, in order to use the PESL algorithm to carry out the epidemic source localization, we must suppose that the infection probability $\beta$ and recovery probability $\gamma$ in the SIR model are all known. Only in this way can we calculate the parameters of the PESL algorithm $\alpha =\beta +\gamma -\beta \gamma$ and carry out the subsequent optimization process. However, it is difficult to know in advance the exact value of the infection probability $\beta$ and the recovery probability $\gamma$ for many real-life epidemic source localization problems. Therefore, it is necessary to study the effects of parameters $\beta$ and $\gamma$ on PESL algorithm. The specific results are shown in Figure 6, the vertical dotted line represents the true infection probability in the SIR model $\tilde{\beta }$ and the horizontal coordinate denotes the parameter $\beta$ used in PESL. When these two parameters are equal $\beta =\tilde{\beta }$, the PESL algorithm has the best source localization performance. When the parameters $\beta$ and $\tilde{\beta }$ differ greatly, the source localization accuracy of the algorithm will decrease significantly, indicating that the PESL algorithm is very sensitive to parameters. In practical problems, it is necessary to estimate the spread parameters as accurately as possible to better use the PESL algorithm to solve the source localization problem.

3.4. Source Localization Accuracy in Empirical Networks

The problem of epidemic source localization in empirical networks is discussed below. Nine empirical networks from the real world are selected to verify the performance of the algorithm. Hospital [16]: The data comes from the contact between patients and medical staff in one hospital of Lyon between 6 December 2010 and 10 December. In the network, node represents the patient or medical personnel, edge between two nodes denotes the close contact(including chat, ward inspection, operation, etc.). Workplace [17]: The network consists of the communication among staffs in an office building in France from 23 June 2013 to 3 July 2013. When two staff members have face-to-face chat, an edge is built between the corresponding nodes. ACM [18]: The data set is an exchange of participants’ data collected during the 2009 ACM Hypertext conference. All participants who volunteer to participate in the data collection program wear a radio badge that records a data item when two participants get close to each other. School [19]: The original data recorded the contact between all students in a local high school of Marseilles, France in December 2013. During the five-day data collection period, any two students who had face-to-face communication were recorded. Infectious [18]: The human exchange network at the art and science fair in Dublin, Ireland, recorded a data item between INFECTIOUS: STAY AWAY (2009) of participants when they became close to each other. URV [20]: The internal email communication network of Rovira I Virgili university in Tarragona, southern Catalonia, Spain. The nodes in the network include the university’s students and faculty members. Yeast [21,22,23,24]: A contact network of proteins within yeast, where node represents proteins and edge denotes the relationships between the two proteins. OpenFlights [25]: The traffic network consists of all the flight information collected by OpenFlights.org. The node in the network represents the airports and edge denotes the flight between them. Sex [26,27]: The sex trade information is collected by a public forum. The original network is a bipartite graph between sex buyers and sex workers, where the edge denotes the trade between them. In the experiment, we ignore the identity and deal with it as an ordinary network.

In above nine empirical networks, Hospital, Workplace, ACM, School and Infectious networks are all collected by the SocioPatterns project http://www.sociopatterns.org/ about the close contact among people, Sex network is a network of intimate sexual contact among citizens, URV network represents the telecommunication networks, Yeast and OpenFlights networks reflect the information diffusion among the human being. For the research convenience, only the giant component of these networks is preserved, and the multilateral and self-loop are deleted. The basic properties of the network obtained are shown in

Table 3. Basic topological properties of nine various networks. Where $N,M$ represent the number of nodes and edges, $〈k〉$ and $k_{max}$ denote the average degree and maximum degree, H means index of degree heterogeneity, $〈d〉$ is the mean shortest path length and $〈C〉$ represents mean local clustering coefficient.

Type	Name	N	M	$〈\mathit{k}〉$	${\mathit{k}}_{\mathbf{max}}$	H	$〈\mathit{d}〉$	$〈\mathit{C}〉$
Contact	Hospital	75	1139	30.373	61	1.244	1.598	0.640
Contact	Workplace	92	755	16.413	44	1.213	1.964	0.426
Contact	ACM	113	2196	38.867	98	1.223	1.656	0.535
Contact	School	327	5818	35.584	87	1.144	2.159	0.504
Contact	Infectious	410	2765	13.488	50	1.388	3.631	0.456
Communication	URV	1133	5451	9.622	71	1.942	3.606	0.220
Biological	Yeast	1458	1948	2.672	56	2.667	6.812	0.071
Transport	OpenFlights	3397	19,230	11.322	248	5.699	4.103	0.488
Contact	Sex	15,810	38,540	4.875	305	5.828	5.785	0.000

.

The relation between epidemic source localization accuracy and infection probability with various source localization algorithms in nine empirical networks is shown in Figure 7. The recovery probability in the SIR model was set as $\gamma =0.1$ and the reporting probability of nodes was set as $\delta =0.3$. It can be seen from the results that the performance of PESL algorithm in all empirical networks except URV network is consistently better than that of other algorithms. When there is a lower infection probability, the spread process has stronger randomness. Although at this time GAU and TRBS algorithms consider location information and time information of observers, their behavior is not better than DC and JC algorithms only considering the location information especially in Hospital and ACM networks. When the infection probability increases, GAU and TRBS will gradually show their wonderful performance. Figure 8 shows the relationship between the performance of source localization algorithm and the reporting probability. Similar to the previous situation, PESL algorithm still has a great source localization performance.

4. Conclusions

Source localization problem is one of the most important topics in complex networks, including information source estimation, rumor source identification and epidemic source localization. In particular, locating the epidemic source in complex network is a classical application, helping us to deal with epidemic problems in a way. In this paper, the main purpose was to propose a method that can locate the epidemic source in complex networks with sparse observers. First, we did some derivation about the probability distribution of infected time of observers. In consideration of the randomness of the spread process, we modeled infected time using probability and then found that the infected time of two adjacent nodes in the network is independent and obeys the geometric distribution of the same parameter. Thus, the infected time from the source to any observer obeys the Pascal distribution. Next, we proposed an epidemic source localization algorithm based on Pascal distribution. We found that when there is no prior knowledge with epidemic source and observers; the posterior probability of epidemic source was equal to the product of infected time of each observer, so that it located the epidemic source through maximizing the posterior probability. After analysis of the initial time range, the algorithm only needed to optimize and solve in a very small search space, which greatly improved the computational efficiency.

To verify the performance of the algorithm, the epidemic source localization experiments were carried out in the synthetic networks and empirical networks and we chose average error distance as the evaluation index. The results showed that the epidemic source localization accuracy of our algorithm in most cases was better than other several comparison algorithms; meanwhile, when the randomness increased, the performance of our algorithm behaved better. The randomness mainly reflected which node was infected by which node through which path. The results of sensitivity analysis showed that the source localization performance of this algorithm was closely related to the parameters in the SIR model. However, obtaining spread parameters from real data has always been a challenge, especially for a new epidemic, whose spread parameters could only be inferred after a large outbreak in a population.

Although our proposed method provides a new reference for source localization problem in complex networks, more considerable works remain to be done. How to identify the multiple sources in complex networks now is a hot topic and useful in practical applications. Compared with the single-source localization problem, the case of multiple sources localization becomes more difficult because it needs to locate the sources at the same time in most cases. However, there are some works [6,28,29] dealing with multi-source localization via two-step strategies that first divide the network into several communities and then apply the single-source localization method to locate sources in each community. In addition, the network topology we consider in this paper is static and just single layer. In fact, the topology in the real world remains dynamic as time goes by or has multiple layers. As we know, few theoretical and practical works have proposed source localization in multi-layer networks [30] and temporal networks [31].

References