Outbreak detection for temporal contact data

Spreading processes in networks have been extensively studied in the literature. Spreading can happen in a wide variety of contexts, including animal or human epidemic spreading (Rocha et al. 2011; Bajardi et al. 2012), computer virus spreading (Pastor-Satorras and Vespignani 2001), and misinformation spreading over social media (Budak et al. 2011). The spreading phenomena often have negative implications and it is of utmost importance to implement eradication strategies to avoid an uncontrolled result (e. g., a global pandemic or a political catastrophe). Sometimes, though, the goal is to foster spreading, for example in the case of viral marketing (Kempe et al. 2003). In both cases, the core idea is that spreading happens in a physical or virtual network, when pairs of nodes are coming into contact. Traditionally, spreading was investigated under a static condition. However, with the rise of more fine-grained tracking systems, which are able to log timestamped contact information, there is a growing body of research studying the spreading problem based on temporal networks (e.g., Bajardi et al. 2012; Valdano et al. 2015).

The optimal selection of monitoring nodes for outbreak detection is a challenging task. Leskovec et al. (2007) address this problem in one of the most influential research works in the field. The authors propose a near-optimal outbreak detection strategy that uses greedy optimization for selecting a (small) set of nodes to be monitored. Crucially, the nodes are selected once and are then monitored constantly. Leskovec et al. propose three optimization goals: detection likelihood (DL), time until detection (DT), and the population that is affected by an outbreak (PA). The approach works well when the network is static and the edges do not vary over time (e.g., a water distribution network). However, for temporal networks, an optimal set of nodes selected based on a past period may not generalize well to a future period of time, especially if the network topology changes rapidly (Bajardi et al. 2012; Leskovec et al. 2007). In general, we may expect central nodes to be suitable for effective monitoring strategies, as they tend to become infected before others (Christakis and Fowler 2010).

In our previous article (Sterchi et al. 2020), we attempt to maximize the likelihood of detecting outbreaks of a disease at a given time t. We define an outbreak of a disease as a spreading process that is initialized by one particular node in the network becoming infectious. This seed node then transmits the disease to at least one connected node in the network. As long as a node is infectious it can further transmit the disease upon contact with another node. In Sterchi et al. (2020), we slightly modify Leskovec et al.’s approach by optimizing the set of monitoring nodes on a given day t with respect to a large number of simulated outbreaks over the period \([t-b, t]\) with \(b=30, 60, 90\) days. More concretely, on a given day t, we select the nodes that detect the most outbreaks, or, in other words, nodes that are most often reached by outbreaks. The sets of optimal nodes may vary depending on t. As a consequence, we were restricted to the first of the objectives proposed in Leskovec et al. (2007), namely the optimization of the detection likelihood. In the present article, we avoid this restriction by replicating the approach proposed by Leskovec et al. By applying their method to two empirical timestamped contact networks and comparing the results with simple heuristic strategies that select nodes based on their centrality, we provide further empirical evidence for the greedy optimization method in the context of outbreak detection.

The approach consists of two main steps: (1) we simulate a large set of possible outbreak scenarios according to a simple susceptible-infected-recovered (SIR) propagation model (Barrat et al. 2008). The simulations are run on a past period where contact data are available. (2) we select nodes using a greedy strategy such that the three objectives mentioned above (DL, DT, and PA) are optimized on this past period. The size of the monitoring set, k, depends on the monitoring resources available. Importantly, we assume that the cost of monitoring a node is the same for all nodes.

The present study has two main objectives. First, we aim to investigate the characteristics of the set of nodes selected according to the greedy optimization approach proposed by Leskovec et al. (2007), as compared to simpler heuristics for node selection (based on centrality). Second, we want to analyze the generalization property, i.e., how well is a set of nodes optimized on a past period suited for outbreak detection on future data. Equivalently, we could ask how strongly the temporal-topological structure of a network changes over time leading to strong variations in the set of optimal nodes over time. These questions have also been partially covered by Leskovec et al. (2007) and subsequent studies. However, we believe that an application of the approach in Leskovec et al. (2007) to networks that are relevant for disease spreading among humans or livestock holdings is still lacking. The reader should bear in mind that this paper does not aim to examine a fully realistic disease spreading scenario. Instead, we use a simple SIR model which makes this paper comparable to many other works in the field of optimal surveillance and control (Bajardi et al. 2012; Holme 2018; Colman et al. 2019; Schirdewahn et al. 2017). However, as will become clear later on, the greedy approach is model-agnostic and can be applied to any spreading model that can be simulated on networks.

Greedy optimization of submodular set functions goes back to the seminal work by Nemhauser et al. who provide “worst case bounds on the quality of the [greedy] approximations.” Nemhauser et al. (1978). More concretely, they show that the solution found by greedily optimizing a submodular set function will be no worse than \(1-1/e\) times the often intractable optimal solution (\(\approx 63\%\)). This result had a profound effect on research communities in many different fields, as it provided a theoretical foundation for applying the simple greedy optimization algorithm to set functions. Unsurprisingly, many papers followed in the footsteps of Nemhauser et al. (1978). A popular application of greedy optimization for submodular set functions arises in the context of influence propagation in (online) social networks. Kempe et al. (2003) show that a greedily selected set of individuals, which maximizes the propagation of influence in a (static) social network, will reach more individuals than if the initial set of individuals is selected based on network centrality measures, such as degree centrality. Crucially, their approach employs extensive Monte Carlo simulations of a stochastic diffusion process (e.g., independent cascades (IC) or linear threshold (LT) models) in order to find the set of possible influence paths and their probabilities. It is obvious that this procedure does not scale to very large networks, which impedes the application of this approach to modern-day online social networks. Therefore, Chen et al. (2010) adopt a heuristic approach for the IC model that is based on local tree-like structures approximating the influence paths of a node. Avoiding the expensive simulations results in good scalability and, at the same time, the performance is close to that of Kempe et al. (2003). Another approach to avoid the Monte Carlo simulations has been proposed by Panagopoulos et al. (2019) who suggest using observed diffusion cascades. Instead of simulating the influence spread from every node, they simply use the observed diffusion cascades that maximize the marginal gain, which can be shown to be submodular. Finally, Budak et al. (2011) examine a variation of the influence propagation problem, namely the so-called influence limitation problem, which can be formulated as a submodular function maximization problem. The influence limitation problem has important applications, such as minimizing the impact of misinformation campaigns.

Optimal outbreak detection and influence maximization are two closely related problems. Maximizing influence corresponds to finding a set of seed nodes that maximize the size of the set of nodes to which the influence will propagate. In contrast, for optimal outbreak detection we aim to select a set of nodes that catches the maximum number of possible spreading cascades (DL objective). Leskovec et al. (2007) demonstrate how greedy optimization can be applied in the context of outbreak detection. In their seminal work, they propose three objective functions: detection likelihood, detection time, and the share of the population that is affected by the spreading process. All three objectives satisfy submodularity and can thus be greedily maximized with theoretical guarantees. One particular improvement of Leskovec et al. (2007) compared to previous approaches is the so called lazy-forward function evaluation. It is based on the idea that if the current marginal gain of a node i is larger than all other nodes’ marginal gains from the previous iteration, submodularity implies that i will also exhibit the largest marginal gain in the current iteration. This can dramatically reduce the number of function evaluations. However, Leskovec et al.’s approach has a limited applicability in temporal networks. For example, they show that the optimal node set selected based on observed blog network information cascades in the past does not generalize well to future outbreak detection. The reason for this is that blog networks are inherently dynamic and may change over time, such that the optimal node set will change substantially over time. One of the main objectives of this article is to assess this generalization problem in the context of epidemic spreading on a sexual contact network and an animal transport network. As mentioned above, the computationally expensive simulations may impair their use on large or very dense networks. However, there have been recent contributions in this area that substantially improve the efficiency of spreading simulations on temporal networks. For example, Vestergaard and Génois (2015) propose an extension of the Gillespie algorithm to temporal networks. Currently, the most efficient simulation approach seems to be an event-driven algorithm that is described in detail in Kiss et al. (2017), St-Onge et al. (2019), Holme (2020).

Both the outbreak detection and the influence maximization problem have been addressed with inexpensive heuristics, such as simply selecting the most central nodes. For example, Budak et al. (2011) note that a heuristic based on selecting nodes with high degree centrality is comparable in performance to the (greedy) optimization approach. Christakis and Fowler (2010) provide an intuitive explanation as to why central nodes can be good detectors of outbreaks: central nodes tend to be infected sooner, as they are topologically closer to the average node in a network. This has been confirmed by Holme (2018) who finds that degree, i.e., the number of distinct neighbors, (for static networks) and strength, i.e., the total number of contacts, (for temporal networks) are generally the best structural detectors of outbreaks for low transmission probabilities. A similar result comes from Sun et al. (2014) who find that in a large-scale city-wide outbreak detection scheme the number of contacts of an individual acts as the best detector in terms of early warnings about an outbreak. Colman et al. (2019) assert that a strategy based on selecting high-degree nodes for outbreak detection can be suboptimal if a (static) network is highly modular and exhibits a rather low degree heterogeneity because those central nodes may be topologically close. Therefore, they propose strategies that select high-degree nodes in different parts of the network (modules or spatial regions). Taken together, these studies indicate that selecting central nodes for monitoring may be overall the optimal structural heuristic for outbreak detection.

A different idea for outbreak detection has been proposed in Bajardi et al. (2012) and Schirdewahn et al. (2017) who suggest to monitor nodes that (1) are infected many times by deterministic spreading cascades from every possible seed node and (2) exhibit low uncertainty about the origin of the outbreak. However, this approach assumes that the starting time of the outbreak is known and spreading cascades are only simulated from this one starting time. Assuming that the specific contact patterns that underlie an emerging spreading process are not available, Valdano et al. (2015) propose to monitor so called loyal nodes, i.e., nodes that have been shown to repeat contact patterns over past periods. They show that loyal nodes are more likely to be reached by infections than disloyal nodes.

Let information about contacts between individuals be organized as a network \(G = (V, E)\) where V denotes the set of nodes (individuals) and E the set of edges (contacts between individuals). The edges in the network are timestamped. Accordingly, an edge can be represented as a triple \((v_i, v_j, t)\in E\) with \(v_i, v_j \in V\) and t a timestamp, indicating when the contact took place. The network can be directed or undirected. We assume that a single node introduced a disease into the network. The disease is then propagated along the edges in accordance with a propagation model, which is assumed to be known. Here, we use the classical susceptible-infectious-recovered (SIR) model: nodes get infected with probability \(\beta\) if they are in contact with an infectious node and the time until recovery follows an exponential distribution (Barrat et al. 2008; Holme 2018). The aim of the work presented here is to identify an optimal set of nodes \({\mathcal {S}} \subseteq V\) such that some objective function is maximized (or minimized). We consider the same three objectives as in Leskovec et al. (2007): the detection likelihood (DL), the time until detection (DT), and the population affected (PA) (i.e., the size of the outbreak at the time of detection). Obviously, we aim to maximize the first and minimize the second and third objective. Once we find the optimal set of nodes, we can constantly monitor them. Since our monitoring resources may be constricted, we set a limit k on the number of nodes we can monitor. Thus, the optimization problem (for the DL objective) is the following:Similarly, we want to find the optimal node set \({\mathcal {S}}\) such that \(DT({\mathcal {S}})\) and \(PA({\mathcal {S}})\) are minimized. Note that all three objectives are set functions that take a set of nodes \({\mathcal {S}}\) as the input and return a real number. For example, for the PA objective, the set function would return the aggregate outbreak sizes (over all outbreak scenarios) at the time of detection by a node in \({\mathcal {S}}\).

The outbreak detection approach used here is to a large extent identical with the one proposed in Leskovec et al. (2007). However, the key distinction between the information spreading example in Leskovec et al. (2007) and the disease outbreak examples in this work is that in the latter case no underlying spreading data are available. Hence, we need to simulate a set of outbreak scenarios. In this section, we first provide the details about the optimization objectives and then discuss the simulation approach we are going to use. Finally, we propose a fast implementation of the greedy optimization process.

In the first example, we consider the spread of sexually transmitted infections (STIs). We use a dataset of timestamped sexual contacts between sex workers and their clients, which is widely used in research on temporal contact networks (Rocha et al. 2011; Valdano et al. 2015; Holme 2018; Antulov-Fantulin et al. 2015). The network is undirected and bipartite and contacts are reported on a daily basis. This rather low temporal resolution means that the order of contacts within a day is not known. We thus assume that consecutive transmissions must be strictly increasing in time. The full dataset covers a period of 6 years from September 2002 to October 2008. We will focus on the last 3 years of the dataset and consider yearly periods. That is to say, we will optimize node selection on a year’s worth of data. The 3-year network consists of 8220 sex-buyers and 5549 sex-sellers and thus 13, 769 nodes overall. A total of 40, 440 timestamped sexual contacts have been registered during this 3-year period (11, 189, 14, 399, and 14, 852, for each year respectively). The most active sex-seller is active 424 times during this 3-year period, while the most active sex-buyer totals 128 contacts in the same period.

For the simulation of the spreading scenarios, we use the SIR model with infection probability \(\beta =0.3\) and an average recovery time of \(\lambda ^{-1}=100\) days. These parameter values are in accordance with related work on STIs (Rocha et al. 2011; Antulov-Fantulin et al. 2015). Average run times of the simulations and the greedy optimization are given in Table 1.

In the second example, we consider reported pig movements in Switzerland during the year 2017 (Sterchi et al. 2019). The movements are reported as directed transports between two animal holdings and contain a timestamp that indicates the day of transport. All movements to slaughterhouses are discarded, as the goal is to monitor farms and catch outbreaks before the final transport to the slaughterhouse. One movement is not necessarily equivalent to one direct transport between the two holdings, but may be part of a tour where multiple different herds of pigs are transported together. Here, we restrict our focus to disease transmission through introduction of new animals in an animal holding and neglect possible transmissions between herds during the transport. In line with (Bajardi et al. 2012), within-farm dynamics are ignored and a movement is regarded as a directed contact potentially transmitting a disease from one farm to the other. We consider monthly networks because a period of 30 days has been considered especially important for animal movement networks (Dubé et al. 2008; Nöremark et al. 2011). This duration corresponds to the silent spread phase, which is typically the maximum time a disease can spread before incidental detection. The full dataset (1 year) contains 6, 664 nodes and 48, 980 directed edges. The monthly networks contain on average 4, 082 edges. The most active node is involved in 615 recorded movements over the course of the year.

As in Example 1, we use a SIR model to simulate the spreading scenarios. In accordance with related work (Bajardi et al. 2012; Valdano et al. 2015; Schirdewahn et al. 2017), we simplify the spreading process by assuming that the infection probability \(\beta\) does not depend on the size of the herd that is transported. We use a rather high infection probability of \(\beta =0.6\) that takes into account the nature of the contact, which is more prone to transmission (multiple possibly infected pigs get introduced into a susceptible farm) than for example in the case of human disease spreading. Note that (Bajardi et al. 2012; Valdano et al. 2015) use even higher infection probabilities (see their supplementary material). The average time until recovery we use is \(\lambda ^{-1}=7\) days as in Bajardi et al. (2012). Note, however, that in Bajardi et al. (2012) the time until recovery is deterministically set to 7 days, whereas we use the stochastic version where the time until recovery stochastically varies around the average value of 7 days. Average run times of the simulations and the greedy optimization are given in Table 1.

The aim of this paper is to extend the greedy optimization method for outbreak detection (Leskovec et al. 2007) to the setting of disease outbreak detection on temporal contact networks. We focus on the same three objectives as in Leskovec et al. (2007): maximizing the detection likelihood, minimizing the time until detection, and minimizing the population affected by an outbreak. These three objectives can be shown to be submodular. Finding the optimal set of nodes that maximizes or minimizes these objectives would be NP-hard. However, due to the submodularity property we have theoretical guarantees that the solution found by greedy optimization is a good approximation to the theoretical optimum.

We used two temporal contact networks to evaluate the greedy approach and to compare it to heuristic benchmarks based on the centrality of a node. One dataset contains sexual contacts and thus represents a possible scenario for the spread of STIs. The other dataset represents directed contacts between Swiss pig farms and may be relevant for the spread of infectious diseases among animals, such as the foot-and-mouth disease (FMD) or African swine fever (ASF). In line with the related work (Rocha et al. 2011; Bajardi et al. 2012; Holme 2018; Colman et al. 2019; Schirdewahn et al. 2017; Antulov-Fantulin et al. 2015), we use a SIR model, which, in most cases, corresponds to a strong simplification of the true processes at work. Note however, that our approach is not constrained by the assumption of a SIR model and it is straightforward to adapt it to any propagation model that can be simulated efficiently.

The results in this paper show that selecting nodes for surveillance based on the greedy optimization approach performs at least as well as the heuristic methods and sometimes even slightly better. However, heuristics such as selecting high-degree nodes are computationally much cheaper and therefore provide a valuable alternative to the optimization-based approach. This corroborates earlier findings in influence maximization (Budak et al. 2011). Moreover, the degree heuristic has been shown to perform well by Holme (2018) for small outbreaks and by Colman et al. (2019) for static networks with small modularity and high degree heterogeneity. This brings us to another important implication of the greedy approach. It may outperform degree-based heuristics by a larger margin for highly modular networks, especially for the DL objective. However, more work is required to establish the connection between the network structure and the optimization-based selection of monitoring nodes. Another important aspect noted by Holme (2018) is that the degree of a node (or the number of links) is a local measure and estimating it does not require knowledge of the network. The fact that the heuristics are comparable in performance to the greedy optimization approach is promising and it can thus be suggested that efficient outbreak detection is possible with limited computational resources and does not require knowledge of the full network structure.

An interesting aspect of our results is that the type of nodes chosen for surveillance depends strongly on the type of network we consider. For the undirected network of sexual contacts, the node sets selected according to the three objectives overlap strongly and high-degree nodes seem to be crucial for all objectives. On the other hand, we observe very dissimilar node sets for the directed network of pig transports. Nodes that satisfy the PA objective (large out-degree) are different from nodes satisfying the DL and DT objective (large in-degree). This may have to do with the structure of the Swiss livestock industry, which is organized in a hierarchical and decentralized way where farms specialize on a specific task in the production process (Sterchi et al. 2019). As a result, farms at the beginning of the production process tend to have a large out-degree and are different from farms at the end of the production process typically exhibiting a large in-degree.

Another important point is that optimizing node selection on past time periods and applying the set of selected nodes for outbreak detection on future time periods may not work well for networks that have strong structural variations between periods. For example, the sexual contact network has a very small overlap in edges between periods that may be due to a lack of organization in this system. Valdano et al. (2015) describe this as a “lack of an intrinsic cycle of activity characterizing the system.” On the other hand, the animal movement network exhibits larger overlaps between periods, indicating a more organized system. While for the sexual contact network, selecting nodes based on a period that is close to the testing period works best, the animal movement network exhibits seasonalities that suggest selecting nodes in period \(t-3\) for monitoring in t. More research should be undertaken to investigate whether or not we can further optimize node selection on past data by optimizing on different past periods and possibly aggregating results over different time periods.

Taken together, the findings of this study suggest that the optimal nodes for outbreak detection are often the highly central nodes in the network because they are either infected early on or they are the origin of a potentially large outbreak themselves. Furthermore, the question which past period should be used to select nodes for future outbreak detection depends on the degree of organization a system exhibits but also on seasonal patterns. The findings of our paper may be somewhat limited by the fact that we only consider two example networks and one specific spreading process, namely a SIR model. To develop a full picture of the greedy optimization approach for outbreak detection and its comparison to heuristics, additional studies are needed that examine its performance over a range of parameter values and for different network structures and spreading models.