Physical contact remains difficult to trace in large metropolitan networks, though it is a key vehicle for the transmission of contagious outbreaks. Co-presence encounters during daily transit use provide us with a city-scale time-resolved physical contact network, consisting of 1 billion contacts among 3 million transit users. Here, we study the advantage that knowledge of such co-presence structures may provide for early detection of contagious outbreaks. We first examine the "friend sensor" scheme -a simple, but universal strategy requiring only local information -and demonstrate that it provides significant early detection of simulated outbreaks. Taking advantage of the full network structure, we then identify advanced "global sensor sets", obtaining substantial early warning times savings over the friends sensor scheme. Individuals with highest number of encounters are the most efficient sensors, with performance comparable to individuals with the highest travel frequency, exploratory behavior and structural centrality. An efficiency balance emerges when testing the dependency on sensor size and evaluating sensor reliability; we find that substantial and reliable lead-time could be attained by monitoring only 0.01% of the population with the highest degree. Digital traces generated by citizens, during their commute across metropolitan transportation networks are helping answer long-standing questions on topics from individual mobility to collective interaction patterns. A series of landmark papers examining multiple large-scale digital traces has shifted the understanding of individual mobility patterns from random to highly structured and predictable [1][2][3][4][5]. This has important implications in urban dynamics and epidemiology, particularly as the reproducible structure of metropolitan face-to-face encounters does significantly shape the spatial-temporal dynamics of disease spreading [6] [7] [8] . Therefore, advances in deciphering metropolitan encounter patterns play an important role in detection and mitigation of contagious outbreaks [9] [10] [11] . In detecting and containing contagious outbreaks, it is crucial to identify "super-spreaders", as they may provide significant lead indicators for the early response of public health agencies [12, 13] . To measure an individual's importance in spreading processes, various centrality measures, such as degree, betweenness, closeness [14] , k-shell index [13] and activity potential [15] have been applied to theoretical diffusion models. Recent empirical works have confirmed the importance of these diverse measurements in real-world diffusion processes [13, [15] [16] [17] [18] [19] [20] . To obtain such measurements, full knowledge about the contact network structure is usually required; however, other than simulating human interaction at this level of resolution [6, 10, 21] , mapping such structure from real-world physical contact processes could be expensive to collect, computationally costly, laborious in the filtering of spurious connectivity, and privacy-sensitive [7, [22] [23] [24] . This has been particularly true for large metropolitan contact networks, where the availability of citywide datasets is still limited [25, 26] . Disease monitoring is extremely costly, privacy sensitive, and involves enormous technical difficulties. A lowcost contact network structure constructed from transit use may provide a way to design efficient monitoring strategies using a small fraction of the population. In this work, we examine the largest metropolitan encounter dataset collected to date -travel smart card data from all of Singapore's bus users, covering approximately 3 million users during 1 week. Using one week's tappingin/tapping-out data collected from public transit services in Singapore, we built a large-scale high-resolution physical contact network. In a recent study based on this dataset, we demonstrated that physical encounters display a significant degree of temporal regularity and these rhythmic interactions form a large-scale spatial-temporal contact network, spanning all of Singapore for the whole week [5]. The study emphasizes that encounters at this fine-grained scale are also very structured, and far from random. If the former study identified the global behavioral properties that generate this citywide co-presence network, our present study tries to identify the key individuals' network properties that can be exploited to combat the spread of infectious disease. As an alternative to constructing a global structure of contact networks, recent research exhibits an increasing arXiv:1401.2815v1 [physics.soc-ph] 13 Jan 2014 2 interest in applying crowd-sourcing as a potential strategy to detect contagious outbreaks, from using declared "friends as sensors", to aggregated search engine queries, to social media [27] [28] [29] [30] [31] [32] . Although these methods proposed are based on simple principles and require only small slices of information, they also show great advantages in providing early warning. Still, interesting questions remain in comparing the possible gains of using full knowledge vs. local methods in an epidemiological city-wide scenario. We perform such study in this highresolution network, as a first empirical evidence of its kind at a population and metropolitan level. To explore the dynamics of city-scale contagious outbreaks, we applied a general susceptible infected (SI) model [33] to simulate the spreading processes (see SI Text). Briefly, a simulation run is initialized with 10 infectious people (as index cases), who are selected randomly among all transit users on Saturday. In the temporal weighted physical encounter network (with each contact as an edge and its duration as weight), an infectious individual i will transmit disease to neighbor j with probability p ij = βd ij per 20 seconds (contagion rate β is a universal parameter across the population and d ij represents encounter duration; see Fig. 1A for example). Once a susceptible individual get infected, he/she becomes infectious after 2 hours, starting to spread the disease to other susceptible people. Note that β = 0.003 is used in a high-resolution contact network in Ref [7, 20] ; we apply comparable values in our simulations. The full temporal resolution enables us to simulate the spreading processes during the whole week based on the proposed scheme for detecting contagious outbreaks, by registering infection time and transmission pathway on individual levels (Fig. 1B) . As mentioned above, a simple, but effective strategy for early detecting contagious outbreaks without mapping the detailed structure of a social network is to find friend sensors from the population [22] . The inherent principle behind this method: a randomly selected "friend" (neighbor; in a friend group) of one vertex (in a control group) has higher degree on average when the network has a heterogeneous degree distribution, implying that friend group is more central than the control group (or the population as a whole). This is commonly referred as the "friendship paradox"; your friends have more friends than you do [34] . However, as social links initiated by physical encounters with strangers display a significant degree of heterogeneity, it remains unclear whether the friend sensor scheme -obtained from a static network structure -works in temporal spreading processes. Hence, to assess performance of the friend sensor scheme, we conducted multiple simulation experiments with different contagion rates β. In each simulation, we first select 1% individuals from population P randomly as a control set C := {c i |c i ∈ P }; the corresponding sensor group S is composed of randomly selected neighbors of each individual in C (S := s i |s i ∈ N (c i ) , c i ∈ C , and N (c i ) is a neighbor set of individual c i ). Note that S is a list instead of a set since an individual might be selected repeatedly from different N (c i ). After obtaining results from 20 simulations, we measured the average infected ratio I S /N S of the sensor groups and I P /N P of the whole population temporally, finding that friend sensors have large lead-times (Fig. 1C) . Given the heterogeneous individual participation and size of the time window [35] , spreading exhibits a linear increase -instead of a saturation process -after the explosive stage. In Fig. 1D , we show the temporal change of infection incidence i (t) from the same simulation as Fig. 1B . The sensor group S is obtained by the same selection scheme; however, in this case, the control group C is the whole population. Together with Fig. 1C , we found that spreading in S not only happens earlier, but also faster than in the whole population, suggesting that the lead-time also varies with time (or infected ratio; see SI Text and Fig.  S1 and S2). Notably, although the temporal structure is not used in finding sensors, the friend sensor scheme is still efficient in early detecting outbreaks in our simulation experiments. Considering that friend sensors are identified locally without using any centrality measures, they could be representative of a universally applicable strategy when it is costly or impossible to map the detailed network structure. To investigate the superiority of friend sensors in a comparable manner, we employed different centrality measures to quantify an individual's importance based on the both network structure and individual travel behavior employing the following centrality measures (see SI Text): (1) Degree k, measuring total number of contacts of each individual during the week, (2) Travel frequency f , frequency of taking public transit services, (f could also be interpreted as number of activities in temporal networks [15] ) (3) Shell index k s , taken from k-shell decomposition [13] on the static network and (4) Encounter entropy S, capturing temporal diversity of encounters: where p t is the probability of an individual's physical encounter in time t (hourly). Using time-stamped encounter transactions, we can build the whole contact network and determine individual's centrality for both control and sensor sets (see Fig. 2 ). Indeed, a sensor group is more central than the randomly selected control group in terms of degree k (Fig. 2A) ; however, it is not yet known whether the friend paradox applies to other measures related to travel behavior (other than network structure). Before looking for additional sensors, we first measured other centrality distributions P (f ), P (k s ) and P (S) using both population and friend sensors. Although most people traveled less than 5 times during the week, we still found that P (f ) was characterized by a heavy tail across the population, indicating a significant degree of heterogeneity in individual transit use pattern (Fig. 2B) . Moreover, we found that P (f ) of the sensor group clearly exhibited the friend paradox as well, indicating that the people you have encountered on buses traveled more often than you do. Using the same control and sensor groups, we then obtained the distributions P (k s ) and P (S). As Fig. 2C and D demonstrate, the friend paradox does exhibit in terms of shell index k s and encounter entropy S as well, suggesting that friend sensors have higher kshell indexes and show higher temporal encounter diversity than the population. Taken together, Fig. 2 suggests that the simple friend sensor scheme can universally identify more centrally located social sensors. Nevertheless, as the percentiles show (in all Fig. 2 panels) , there are still significant differences between the most central individuals and friend sensors, further indicating that the efficiency of friend sensors might be limited. Taken together, as one might expect, the simple principle of friend sensor scheme also prevents itself from performing more efficiently, as better sensors could always be obtained by using more information on contact structure. We next compare performance of the best sensors identified by each centrality measure against friend sensors by quantifying lead-time on a universal scale. When individual infected time cannot be obtained across the whole population, lead-time is estimated as difference between control and sensor samples in general [22] . However, since transit services are generally not operated 24 hours a day, the cumulative infection curve is not strictly monotonic increasing during the monitoring period in our case, resulting in significant difference when calculating lead-time from multiple runs; thus, using instantaneous lead-time is a biased measure of sensor performance (see SI Text and Fig. S2 ). However, given that individual infection time can be traced from simulations, we can essentially quantify lead-time against the whole population instead of a small sample control group. For efficient early detection, we fixed the monitored infected 99.99 th percentiles of corresponding values across the whole population, explaining the degree of heterogeneity among most centrally located individuals, friend sensors and the population as a whole. ratioα = [α 1 , α 2 ) = [0.05, 0.25) and measured only the difference of infection time of people inα, obtaining infection time tα P = {t i |α 1 ≤ F P (t i ) < α 2 } from population and tα S = {t i |α 1 ≤ F S (t i ) < α 2 } from sensor group (F represents the empirical distribution of infected time). We re-define lead-time as the difference of average tα P and tα S : Next, we ordered individuals according to their centrality measure and divided the whole population into 100 percentiles. Using each percentile as a sensor group, we performed 20 simulation runs and measured the corresponding lead-times under different contagion rate β. As  Fig. 3 shows, the top 1% slices from all these partitions are able to provide early detection; however, the less the average centrality is, the shorter the lead-time T will be. For example, the sensor group provides no advanced detection when k ≈ k 0.4 and even falls behind the general population when k > k 0.4 (k 0.4 is the 40 th percentile of degree). In this case, lead-time may reach infinity if the spreading cannot reach α 2 (25%) among sensor group. By comparing these centrality measures jointly, we found that they actually vary consistently on sensor composition; however, no one outperforms the others significantly (see SI Fig. S3 ). The efficiency of using such sensors to detect contagious outbreaks depends not only on centrality measures, but also sensor size |S|. On one hand, a small sample size induces large variation, providing poor reliability in potential applications. On the other hand, the difference of average centrality measure might be more and more significant given the intrinsic heterogeneity of individual behavior, revealing that we may achieve longer lead-time with lower cost (if the cost is in proportion to sensor size). In Fig. 4A , we chose degree as primary centrality and measured lead-time for logarithmically spaced sampling rate n = |S| / |P |, spanning from 0.001% (only 27 people with highest degree) to 100% (the full population is used as sensors; lead-time is zero in this case). As the figure shows, smaller sample size indeed provides longer lead-time, but, with larger variation. In Fig. 4B , we show performance of friend sensors obtained from equally sized control groups. Given that the sensor group is always sampled from a deterministic population, we observed a constant average lead-time, independent of sampling rate n. However, the standard deviation of lead-time decreases as sample size gets larger in both Fig. 4A and B, corresponding to the law of large numbers when calculating lead-time in each simulation. In practice, one should not just consider average leadtime and monitoring cost of such sensors; their reliability is equally important. To evaluate sensor reliability, we created a simulation result set with 500 runs and measured the lead-time distribution P (T ) for contagion rate β = 0.001. As Fig. 4C shows, average lead-time of different sensor groups (in terms of sensor sizes) is well characterized by normal distribution, however, with significant mean and variance difference. Notably, the top 0.01% group performs extremely well for both average lead-time provided and reliability. Fig. 4D shows results of the same analysis for the friend sensor scheme. We observed that the larger the sensor size is, the more reliable the lead-time becomes; however, increasing sensor size does not raise average performance, consistent with what Fig. 4B shows. We also applied this procedure to other centrality measures: frequency f , k-shell index k s and encounter entropy S, finding that sensor group identified by degree outperforms all other centrality measures (see SI Text and Fig. S4 ). Taken together, Fig. 4 suggests that the friend sensor scheme indeed provides a substantial lead-time in early detection; however, the inherent principle prevents it from performing better by adjusting sensor sizes (in other words, average performance is independent on sensor size), whereas a well-defined sensor (obtained by degree centrality in this case) can easily outperform it. Our results further illustrate a clear advantage of deriving sensors from the full co-presence network, providing longer, more reliable lead-time by using a smaller sensor group.  6 To summarize, we show the feasibility of a friend sensor scheme in providing early detection during a contagious outbreak in a metropolitan physical contact network. Indeed, the simple friend sensor scheme, which does not require a detailed network structure, works consistently well in finding sensors that are more central in the network. However, since all friend sensors are actually characterized by a deterministic neighbor population based on network structure, their performance is often limited by inherent characteristics of the neighbor population, providing constant early warning on average, independent of sample selection and sample size. Therefore, it is still crucial to show the value of full network structure, in particular for early detecting contagious outbreaks. Taking advantage of individual-based passive data collection techniques on city-scale (transit fare collection systems in this paper), we mapped detailed spatial and temporal structures as a whole and identified new sensors given diverse centrality measures, offering new insight into finding more efficient social sensors. Considering the weak, passive and indirect nature of social links enabled by these common daily physical encounters, k-shell index k s -a well-defined structural centrality -is less effective than the simple degree k and frequency f (number of activities) in contagious detection. Note that we did not use betweenness and closeness centralities as a measure in our study. On one hand, computing shortest pathbased centralities is extremely time-consuming because of this network's high density. On the other hand, considering the temporal nature of daily encounters, the role of static shortest path is not as significant as it is in social networks of personal relations. Based on the spreading settings examined in our study, a well-defined social sensor group based on degree may account for only 0.01% of the total population; however, it provides longer and more reliable lead-time -than the friend sensor scheme -allowing public health officials and governments to plan a quick and efficient response. Influenza-like diseases are transmitted primarily by close contacts. Although the network used in our study is created across the whole metropolitan area, capturing all transit users' contacts during a whole week, it still covers only a small slice of all potential contacts in our daily life. On the other hand, to simulate an outbreak, we fixed simulation settings for the outbreak to travel at a speed where global and local methodologies could be tested. To what extent the simulation can match a real contagious outbreak remains to be measured. Thus, it is important to note that the specific results in our study are embedded in the physical encounter network with a pre-defined spreading mechanism. Such encounters on transit vehicles occur more often between perfect strangers than among friends, colleagues or families, making the network incomplete for predicting epidemic spreading via all possible transmission pathways. Therefore, great caution should be exercised in interpreting the results. In reality, a full contact network for disease spreading consists of all of social links from diverse circumstances; it remains unclear to us which part should be given priority with respect to the characteristics of an unknown virus/disease. Nevertheless, with the rapid development of information and communication technologies, mapping the whole structure of close encounters from various data would be far less difficult and laborious today. Given the high individual and collective regularities rooted in human behaviors [2][3][4][5], patterns of face-to-face encounters in various settings could be documented as well [7, 24] , helping us build more comprehensive agent-based models to contain emerging epidemics [10, 36] . Moreover, with our increasing knowledge about ourselves and various microorganisms around us, more efficient social sensors for different scenarios can be identified and applied in monitoring contagious spreading from day to day, providing early and accurate information to support better decision making. We believe that our work can serve as a base to help better combat the spread of disease on a citywide scale [37, 38] and better understand social contagion dynamics [39] [40] [41] .
In particular, high resolution human interaction network data have much to offer in the domain of public health (see REF for a review).
Efficient detection of contagious outbreaks in massive metropolitan encounter networks
Sci. Rep. 4, 5099 (2014)
Computer Science Physics Medicine Geography