Social Sensors in Epidemiological Networks via Graph Eigenvectors

One of the earliest attempts to solve the aforementioned problem was by Christakis and Fowler [2010]. They first introduced the notion of a sensor set, i.e. a subset of the set of individuals (vertices) from the original network. Their idea was to monitor this sensor set to detect contagious outbreaks before they occur in the population at large. Now, the next problem is to come up with a feasible method to choose the sensor set. In this regard, they used the underlying social network structure. They argued that during an outbreak, nodes at the center of the network are more likely to be infected sooner. Hence, choosing central individuals as the sensor set might provide the information about the outbreak in advance. However, it might be costly, and time consuming to collect the information about the entire large network. So they proposed an alternative method that does not require to do that. They leverage an interesting property of a social network, that says, on average your friends have more friends than you do (Feld [1991]). In more formal words, friends of a randomly selected individuals in a social networks are more central (i.e. in general have higher degrees, higher betweenness centrality etc.) than the randomly chosen individuals. So their proposed strategy was to monitor the friends nominated by the randomly chosen individuals as the sensor set. Note that in an epidemic outbreak, these nominated friends are expected to be infected sooner. From here on we refer this method as FOS approach.

They evaluated this FOS method in a flu outbreak in Harvard College in the fall of 2009. As expected there was a shift in the S-shaped cumulative incidence curve, and the daily incidence curve, detecting a significant amount of lead time. Moreover, it was observed that the friend group exhibited higher in-degree (number of times an individual was nominated by someone as a friend), higher centrality (number of shortest paths between two nodes in the network that pass through an individual), higher coreness (number of friends an individual has when individuals with lowest degrees are iteratively removed), and lower transitivity (the probability that two of one’s friends are friends with one another). Moreover, the aforementioned features were also used to construct the sensor set alternatively, but none of those parameters provided significant improvement in terms of the lead time than the method originally proposed. Rather, computation of these parameters required entire information about the network structure, in contrast with the monitoring the friends method, which requires the information on the sample collected only.

This work by Christakis and Fowler [2010] was one of the earliest attempt to identify the social sensor in epidemic outbreak. Although the importance of central individuals during an outbreak was not unknown (Cohen et al. [2003]), the credit for introducing the notion of sensors for an early detection of an outbreak goes to them. Moreover, they applied an interesting but easily comprehensible property of a social network in order to identify the sensor group that even does not require the information about the entire network.

Despite the merits of this method, there are certain drawbacks which one should address. First of all, this method lacks mathematical rigor. Although it describes certain important properties of a social network in terms of the degree distribution, how that helps to identify the sensors in an epidemiological network is not discussed mathematically, only intuition was provided. Apart from this, this method can’t predict the lead time which could be of real importance in disease management. Moreover, this method might not always provide a lead time as noted by Shao et al. [2016]. It was shown that this method works better in a star like topology compared to a network where the degree does not follow a scale-free distribution.

Shao et al. [2016] suggest another way of identifying social sensors for early detection of a contagious epidemic. They noted that networks with star-like topology where a few of the central nodes have very large degrees, perform relatively better under the ‘Friends of Friend’ approach as this graph structure facilitates inclusion of central nodes with high degrees to form the sensor group. On the other hand, in networks where the total number of nodes is large with an average number of edges spread across the network, it is difficult for the ‘Friends of Friend’ approach to select sensors that will represent the entire graph based only on local friend-friend information. To tackle this kind of situation, they base their sensor selection technique on the objective of choosing the smallest group $S$ so that at least some nodes in $S$ contract the disease within the first $d$ days of the outbreak with probability at least $\epsilon$. This can be done by the PLTM (Peak Lead Time Maximization) method.

		$\displaystyle S=\arg\max_{S}E[t_{pk}-t_{pk}(S)]$		(1)
		$\displaystyle s.t.\enskip f(S)\geq\epsilon,|S|=k$		(2)

where $t_{pk}=\arg\max_{t}I(t)$ and $t_{pk}(S)$ denotes the time of peak of the entire network and the sensor set respectively, $f(S)$ is the probability that at least one node in $S$ is infected, assuming that the disease spread started from a random initial node. However, this optimization problem is non-submodular. Leskovec et al. [2007] developed a greedy algorithm that adds a sensor that maximizes the marginal gain based on expected penalty reduction, where a penalty is incurred depending on the time of detection and impact on the whole network before detection. Following this method, Shao et al. [2016] consider a different, although related method with the aim of reaching a sub-modular optimization problem after defining $t_{inf}(v)$ as the expected infection time for node $v$,

		$\displaystyle S=\arg\min_{S}\sum_{v\in S}t_{inf}(v)/|S|$		(3)
		$\displaystyle s.t.\enskip f(S)\geq\epsilon,|S|=k.$		(4)

The second method is submodular, but non-linear and as a result existing greedy approaches for maximizing submodular functions do not work directly. The authors propose two faster greedy approaches that picks nodes in non-decreasing $t_{inf}(.)$ order until $S$ has $f(S)\geq\epsilon$, namely, Transmission Tree (TT) based sensors heuristic and Dominator Tree (DT) based sensor heuristic. The TT based sensor selection heuristic first generates subgraphs of the whole network (called dendrograms) that contain infected nodes and edges through which the disease is transmitted and the depth of each node ($v$) is computed if the node gets infected in a dendrogram. This is done for all the generated dendrograms and the average of all such depths gives $t_{inf}(v)$. The heuristic then discards nodes for which $t_{inf}(v)$ is smaller than a specified value and from among the rest selects the first $k$ nodes with smallest $t_{inf}$ values. The DT based sensor selection heuristic, on the other hand, follows the exact same steps, except that the average depth of a node $v$ is now computed from a dominator tree generated from each dendrogram, where a node $x$ is said to dominate node $y$ in a directed graph if and only if all paths from the source node of infection to node $y$ has to pass through $x$.

Experimental studies on a star-like network of Oregon route-views and social contact networks for six large cities in the US show that the TT and DT approaches perform quite better than the algorithm proposed in Christakis and Fowler [2010], but the ‘Friends of friend’ approach still works better in the Oregon network. Moreover, for the TT and DT approaches, observing the whole network is essential for selecting the sensor group that gives substantial lead time in detection. Although, Shao et al. [2016] also do not give an estimate of the lead time, however, they empirically show the stability of the lead time with increasing monitoring days. Also, their methods have high variance in lead time for smaller sensor set sizes, but it steadily falls as $k$ increases.

The fundamental premise of the notion of the eigenvector centrality is, a node is important if it is neighbor to other important nodes. This is in some sense an inductive concept. However, mathematically this can be expressed precisely. In this method relative centrality scores $\{v_{1},\dots,v_{n}\}$ are assigned to all nodes in the network based on the concept that connections to high-scoring nodes should contribute more to the score of the node in question. This can be done recursively by initially taking $v_{i}^{(1)}=1\enskip\forall i=1,\dots,n$ and then defining a node importance at step $t+1$ as a function of the node importance of its neighbors at step $t$ as follows.

$$v_{i}^{(t+1)}=\frac{1}{\lambda}\sum_{j}A_{ij}v_{j}^{(t)}\iff\lambda\textbf{v}^{(t+1)}=A\textbf{v}^{(t)},$$

(6)

Here $\lambda$ is used for down-weighing the scores and facilitating convergence to the centrality scores. We also assume the network to be connected. Assuming the convergence of Equation 6, note that any eigenvector of the adjacency matrix could be the limiting value. However, the following theorem asserts the unique convergence of the given equation.

Note that obtaining eigenvector centrality scores include summing only nonnegative real numbers and hence score for a node can not be negative. Hence by Theorem 3.1, the only solution to which the above recurrence relation converges, is the largest eigenvector of the adjancency matrix of the graph $A$. Hence, we propose the following method leveraging the eigenvector centrality of the nodes of the underlying social network. Select the first $k$ nodes based on the eigenvector centrality score (i.e. for node $i$, the $i$-th element of the eigenvector corresponding to the largest eigenvalue would be the score) in the sensor set. $k$ is the parameter of this method. Choice of $k$ is certainly is an important task, since choosing $k$ to be very high or very low might lead to the reduction in the lead time. However, in this write-up we would not focus on this. Instead, for the sake of comparison, the $k$ is taken as the size of the sensor set chosen by the FOS approach.

This approach can be interpreted as a direct extension of the FOS approach. In FOS approach, more central nodes are selected by choosing the friends of a random sample. But one might wonder what would happen if this is repeatedly done. Would that lead to more central nodes? In this approach we have investigated the answer to this question. For the sake of simplicity start with selecting one node randomly from the graph. Then at each step we select one individual randomly from the friends of the individual selected in the previous step. This transition can be interpreted as a discrete time markov chain $\left\{X_{i}\right\}_{i\in\mathbb{N}}$ with the state space being the nodes of the network in consideration. We say that the chain in at state $i$ at time $t$ if the $i$-th node is selected at time $t$. Next consider the following lemma and the theorem.

The NEV approach proposes to select the nodes based on the eigenvector corresponding to the eigenvalue 1 of B. Similar to EV approach, in this method also, we do not focus on the regime of determining the size of the sensor set. It is taken to be the size of the sensor set by FOS approach.

Below we provide the comparative summary of the methods we have discussed so far (Table 1).

The previous heuristic methods did not leverage any information on the disease propagation model itself. So our next approach would be to use that information in order to predict the lead time. One simple but computationally expensive way could be to run an SIR simulation based on estimated $\beta$ and $\gamma$ values to analytically determine the peak time and hence the lead time. The first and foremost step of that would be to estimate the parameters used to define the disease SIR model $\beta$ and $\gamma$. The Maximum Likelihood Estimators of these quantities cannot be derived analytically as the likelihood is very complex. So we provide simple Method of Moments type unbiased estimators of $\beta$ and $\gamma$. We first define

$$I_{it}=\begin{cases}1&\text{ if node i is infected at time t}\\ 0&\text{otherwise}\end{cases}$$

$$S_{it}=\begin{cases}1&\text{ if node i is susceptible at time t}\\ 0&\text{otherwise}\end{cases}$$

$$R_{it}=\begin{cases}1&\text{ if node i is recovered at time t}\\ 0&\text{otherwise}\end{cases}$$

Then, define $\hat{\beta}=\frac{1}{nT}\sum_{t=2}^{T}\sum_{i=1}^{n}\frac{I_{it}S_{i,t-1}}{\sum_{j\in N(i)}I_{j,t-1}}$ and $\hat{\gamma}=\frac{1}{nT}\sum_{t=2}^{T}\sum_{i=1}^{n}{R_{it}I_{i,t-1}}$. To show the unbiasedness we use the smoothing formula of expectation,

	$\displaystyle\allowdisplaybreaks E(\hat{\beta})$	$\displaystyle=\frac{1}{nT}\sum_{t=2}^{T}\sum_{i=1}^{n}E\left[\frac{I_{it}S_{i,t-1}}{\sum_{j\in N(i)}I_{j,t-1}}\right]$
		$\displaystyle=\frac{1}{nT}\sum_{t=2}^{T}\sum_{i=1}^{n}E\left[\frac{S_{i,t-1}}{\sum_{j\in N(i)}I_{j,t-1}}E(I_{it}|\mathcal{A}_{t-1})\right]$

where $\mathcal{A}_{t-1}$ is the sigma field generated by $\{S_{i,t-1}\}$ and $\{I_{j,t-1}\}$.

		$\displaystyle=\frac{1}{nT}\sum_{t=2}^{T}\sum_{i=1}^{n}E\left[\frac{S_{i,t-1}}{\sum_{j\in N(i)}I_{j,t-1}}P(I_{it}=1|\mathcal{A}_{t-1})\right]$
		$\displaystyle=E\left[\frac{1}{\sum_{j\in N(i)}I_{j,t-1}}P(I_{it}=1|S_{i,t-1}=1)\right]$
		$\displaystyle=\beta$

And similarly, defining a sigma algebra over $I_{i,t-1}$, we can write

	$\displaystyle E(\hat{\gamma})$	$\displaystyle=\frac{1}{nT}\sum_{t=2}^{T}\sum_{i=1}^{n}E\left[R_{it}I_{i,t-1}\right]$
		$\displaystyle=\frac{1}{nT}\sum_{t=2}^{T}\sum_{i=1}^{n}E\left[I_{i,t-1}P(R_{i}t=1|I_{i,t-1}=1)\right]$
		$\displaystyle=\gamma$

Note that here $T$ is not the entire period of the disease propagation, rather it is the time till when we have observed the propagation, very likely a few time points after the lead time in the sensor group. However, simulations studies suggest that these estimators largely under-estimate the actual parameter values, hence we have not proceeded much further in this direction. In future work, we plan to further investigate the reasons for this, and then we would like to look at the variance of these estimators. The closed form expression could be derived from the smoothing formula on the variance operator.

The degree of a node in an undirected graph is the number of edges it has. The degree distribution is the probability mass function for all the degrees, i.e., the distribution of degree we would find by picking randomly and uniformly over nodes. For our purpose, we consider two broad groups of random graphs; egalitarian or decentralized (one where the edges are more or less equally distributed across the network, that is a more or less uniform degree distribution) and authoritarian or centralized (where a central node has a much higher degree than non-central nodes) [Sueur et al., 2012]. We choose the Erdös-Rényi and Chung-Lu models to represent the two kinds of graphs respectively.

Erdös-Rényi networks are random graph with $n$ vertices where each possible edge has probability $p$ of existing. Consider a graph with $n$ nodes. The full graph will then consist of $N={n\choose 2}$ edges, and say the set of all possible edges is $E=\{e_{1},e_{2},\dots,e_{N}\}$. In an Erdos Renyi random graph $G(n,p)$, an edge $e_{i}$ is picked with probability $p$ independently of occurrences of other edges. Let $X$ be the number of edges in the graph. Then, The expected number of edges in this graph is ${n\choose 2}p$. The expected mean degree in such a network is $(n-1)p$, which is the same for all vertices, implying that it pertains to our condition of being a representative of the decentralized society.

Chung-Lu Networks are random graphs with n vertices where each possible edge has probability $p_{ij}=\frac{w_{i}w_{j}}{\sum_{k}w_{k}}$ of existing between nodes $i$ and $j$, where $\{w_{1},\dots,w_{n}\}$ is a set of weights attached the $n$ nodes. Here, for a pair (i,j) an edge $e_{i}$ is chosen independently with probability $p_{ij}$. The expected degree of vertex $i$ is:

$\displaystyle\sum_{j=0}^{n}\frac{w_{i}w_{j}}{\sum_{k}w_{k}}=w_{i}$

The edge distribution here thus depends upon the centrality of the nodes in this graph. The weights can be modified to create star-like topology which are vital to our study.

We used the simple network based SIR model for our simulation study. Let $G_{s}=(V,E_{s})$ be a social network. Based on this, the disease network would progress over time as follows:

Consider the following probabilities,

	$\displaystyle S_{i}(t)=P(\text{node i is susceptible at time t})$
	$\displaystyle I_{i}(t)=P(\text{node i is infected at time t})$
	$\displaystyle R_{i}(t)=P(\text{node i has recovered at time t})$

Clearly, at any given time $t$, $S_{i}(t)+I_{i}(t)+R_{i}(t)=1$ should hold for all vertices. The disease propagation on the underlying network structure can then be modelled as

	$\displaystyle\frac{dI_{i}}{dt}=\beta S_{i}\sum_{j}A_{ij}I_{j}-\gamma I_{i}$
	$\displaystyle\frac{dS_{i}}{dt}=-\beta S_{i}\sum_{j}A_{ij}I_{j},\quad\frac{dR_{i}}{dt}=\gamma I_{i}$

An approximate solution to the above set of differential equations is as follows:

$$I(t)\approx\textbf{v}_{1}e^{(\beta\lambda_{1}-\gamma)t}$$

where $\lambda_{1}$ is the largest eigenvalue of the adjacency matrix A and $\textbf{v}_{1}$ is the corresponding eigenvector.

For the ease of simulation, we consider discrete time setup with the probabilities of transition of node i from the state at time t (say $x_{i,t}$) to the state at time t+1 (say $x_{i,t+1}$) as follows:

	$\displaystyle(x_{i,t+1}\,|\,x_{i,t}=S)$	$\displaystyle=\begin{cases}I,&\text{w.p. }\beta{\sum_{j\in\mathcal{N}(i)}\mathbb{I}(x_{jt}=I)},\\ S,&\text{w.p. }1-\beta{\sum_{j\in\mathcal{N}(i)}\mathbb{I}(x_{jt}=I)}.\end{cases}$
	$\displaystyle(x_{i,t+1}\,|\,x_{i,t}=I)$	$\displaystyle=\begin{cases}R,&\text{w.p. }\gamma,\\ I,&\text{w.p.}1-\gamma.\end{cases}$
	$\displaystyle(x_{i,t+1}\,|\,x_{i,t}=R)$	$\displaystyle=\begin{cases}R,&\text{w.p. }1.\end{cases}$

From the plots in Figure 1 and also the results in table 2, we can see that EV and NEV approaches to sensor group selection give a lead time ahead of the FOS approach , which in turn peaks before the entire network on the whole. Shao et al. [2016] had noted that networks with star-like topology where a few of the central nodes have very large degrees, perform relatively better under the FOS approach as this graph structure facilitates inclusion of central nodes with high degrees to form the sensor group. However, our proposed methods give greater lead times under such star-like graphs generated by the Chung-Lu model. Moreover, we also noted that the lead time difference between the FOS and EV/NEV methods are more pronounced when smaller random samples are chosen to begin with. Having said that, henceforth we provide results for the cases where we begin with larger (20) initial samples, hoping that the corresponding outcomes would be better if smaller (10) samples were initially chosen.

Next, for the different values of infection and recovery rates, we present the peak times for the four groups in 3. Our proposed methods not only work better than the exsiting FOS approach under the star-like Chung-Lu Model under all the three variations in the values of thr rate parameters, but also perform comparably under the Erdös-Rényi Network.

Finally, we report the estimated peaks from the sensor groups. The polynomial regression of degree three fits the data quite well and Figure 2 shows that the estimated peak time by the EV sensor group for the Erdös-Rényi Model is 2000, whereas the population actually peaks on the time point 1892. However, for the Chung Lu Model, the EV sensor group estimates the peak time to be 1144, whereas the population actually peaks on 1284. The absolute peak time difference for the ER model is 108 and that for the CL model is 140. We note here that the simulation was conducted over 10000 time points and so estimation of the margin of error of the peak time is acceptable here.

For the NEV sensor group with initially 20 infected individuals, we notice from Figure 3 that for the Erdös-Rényi Model, the estimated peak time is 1588, which is 304 time points ahead of the actual time to peak by the population 1892. Again, for the Chung Lu Network, the estimated peak time is 1259, whereas the population peak time is 1284, resulting in a margin of error of 25. The NEV approach is seen to work better for star-like graph structures and that explains why the error in estimation under Chung Lu Model is lower.