{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T07:33:33Z","timestamp":1778830413162,"version":"3.51.4"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T00:00:00Z","timestamp":1613692800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T00:00:00Z","timestamp":1613692800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003475","name":"Hasler Stiftung","doi-asserted-by":"publisher","award":["18050"],"award-info":[{"award-number":["18050"]}],"id":[{"id":"10.13039\/501100003475","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["407540_167303"],"award-info":[{"award-number":["407540_167303"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Epidemic spreading is a widely studied process due to its importance and possibly grave consequences for society. While the classical context of epidemic spreading refers to pathogens transmitted among humans or animals, it is straightforward to apply similar ideas to the spread of information (e.g., a rumor) or the spread of computer viruses. This paper addresses the question of how to optimally select nodes for monitoring in a network of timestamped contact events between individuals. We consider three optimization objectives: the detection likelihood, the time until detection, and the population that is affected by an outbreak. The optimization approach we use is based on a simple greedy approach and has been proposed in a seminal paper focusing on information spreading and water contamination. We extend this work to the setting of disease spreading and present its application with two example networks: a timestamped network of sexual contacts and a network of animal transports between farms. We apply the optimization procedure to a large set of outbreak scenarios that we generate with a <jats:italic>susceptible-infectious-recovered<\/jats:italic> model. We find that simple heuristic methods that select nodes with high degree or many contacts compare well in terms of outbreak detection performance with the (greedily) optimal set of nodes. Furthermore, we observe that nodes optimized on past periods may not be optimal for outbreak detection in future periods. However, seasonal effects may help in determining which past period generalizes well to some future period. Finally, we demonstrate that the detection performance depends on the simulation settings. In general, if we force the simulator to generate larger outbreaks, the detection performance will improve, as larger outbreaks tend to occur in the more connected part of the network where the top monitoring nodes are typically located. A natural progression of this work is to analyze how a representative set of outbreak scenarios can be generated, possibly taking into account more realistic propagation models.<\/jats:p>","DOI":"10.1007\/s41109-021-00360-z","type":"journal-article","created":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T20:46:05Z","timestamp":1613767565000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Outbreak detection for temporal contact data"],"prefix":"10.1007","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1105-8780","authenticated-orcid":false,"given":"Martin","family":"Sterchi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cristina","family":"Sarasua","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Gr\u00fctter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abraham","family":"Bernstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,19]]},"reference":[{"key":"360_CR1","doi-asserted-by":"publisher","first-page":"248701","DOI":"10.1103\/PhysRevLett.114.248701","volume":"114","author":"N Antulov-Fantulin","year":"2015","unstructured":"Antulov-Fantulin N, Lan\u010di \u0107 A, \u0160muc T, \u0160tefan\u010di \u0107 H, \u0160iki \u0107 M (2015) Identification of patient zero in static and temporal networks: robustness and limitations. Phys Rev Lett 114:248701. https:\/\/doi.org\/10.1103\/PhysRevLett.114.248701","journal-title":"Phys Rev Lett"},{"issue":"76","key":"360_CR2","doi-asserted-by":"publisher","first-page":"2814","DOI":"10.1098\/rsif.2012.0289","volume":"9","author":"P Bajardi","year":"2012","unstructured":"Bajardi P, Barrat A, Savini L, Colizza V (2012) Optimizing surveillance for livestock disease spreading through animal movements. J R Soc Interface 9(76):2814\u20132825. https:\/\/doi.org\/10.1098\/rsif.2012.0289","journal-title":"J R Soc Interface"},{"key":"360_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511791383","volume-title":"Dynamical processes on complex networks","author":"A Barrat","year":"2008","unstructured":"Barrat A, Barthlemy M, Vespignani A (2008) Dynamical processes on complex networks, 1st edn. Cambridge University Press, New York","edition":"1"},{"key":"360_CR4","doi-asserted-by":"publisher","unstructured":"Budak C, Agrawal D, El\u00a0Abbadi A (2011) Limiting the spread of misinformation in social networks. In: Proceedings of the 20th International Conference on World Wide Web, pp. 665\u2013674. ACM, New York, NY, USA. https:\/\/doi.org\/10.1145\/1963405.1963499","DOI":"10.1145\/1963405.1963499"},{"key":"360_CR5","doi-asserted-by":"publisher","unstructured":"Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining. KDD \u201910. Association for Computing Machinery, New York, NY, USA, pp 1029\u20131038. https:\/\/doi.org\/10.1145\/1835804.1835934","DOI":"10.1145\/1835804.1835934"},{"issue":"9","key":"360_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pone.0012948","volume":"5","author":"NA Christakis","year":"2010","unstructured":"Christakis NA, Fowler JH (2010) Social network sensors for early detection of contagious outbreaks. PLOS ONE 5(9):1\u20138. https:\/\/doi.org\/10.1371\/journal.pone.0012948","journal-title":"PLOS ONE"},{"issue":"11","key":"360_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pcbi.1007517","volume":"15","author":"E Colman","year":"2019","unstructured":"Colman E, Holme P, Sayama H, Gershenson C (2019) Efficient sentinel surveillance strategies for preventing epidemics on networks. PLOS Comput Biol 15(11):1\u201319. https:\/\/doi.org\/10.1371\/journal.pcbi.1007517","journal-title":"PLOS Comput Biol"},{"key":"360_CR8","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. The MIT Press, Cambridge","edition":"3"},{"issue":"9\u201310","key":"360_CR9","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1111\/j.1865-1682.2008.01053.x","volume":"55","author":"C Dub\u00e9","year":"2008","unstructured":"Dub\u00e9 C, Ribble C, Kelton D, McNab B (2008) Comparing network analysis measures to determine potential epidemic size of highly contagious exotic diseases in fragmented monthly networks of dairy cattle movements in Ontario, Canada. Transbound Emerg Dis 55(9\u201310):382\u2013392. https:\/\/doi.org\/10.1111\/j.1865-1682.2008.01053.x","journal-title":"Transbound Emerg Dis"},{"key":"360_CR11","doi-asserted-by":"publisher","first-page":"022313","DOI":"10.1103\/PhysRevE.98.022313","volume":"98","author":"P Holme","year":"2018","unstructured":"Holme P (2018) Objective measures for sentinel surveillance in network epidemiology. Phys Rev E 98:022313. https:\/\/doi.org\/10.1103\/PhysRevE.98.022313","journal-title":"Phys Rev E"},{"key":"360_CR10","unstructured":"Holme P (2020) Fast and principled simulations of the SIR model on temporal networks. arXiv:2007.14386"},{"key":"360_CR12","doi-asserted-by":"publisher","unstructured":"Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining. KDD \u201903. ACM, New York, NY, USA, pp 137\u2013146. https:\/\/doi.org\/10.1145\/956750.956769","DOI":"10.1145\/956750.956769"},{"key":"360_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-50806-1","volume-title":"Mathematics of epidemics on networks","author":"I Kiss","year":"2017","unstructured":"Kiss I, Miller J, Simon P (2017) Mathematics of epidemics on networks. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-319-50806-1"},{"key":"360_CR14","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1017\/CBO9781139177801.004","volume-title":"Tractability: practical approaches to hard problems","author":"A Krause","year":"2014","unstructured":"Krause A, Golovin D (2014) Submodular function maximization. In: Bordeaux L, Hamadi Y, Kohli P (eds) Tractability: practical approaches to hard problems. Cambridge University Press, Cambridge, pp 71\u2013104. https:\/\/doi.org\/10.1017\/CBO9781139177801.004"},{"key":"360_CR15","doi-asserted-by":"publisher","unstructured":"Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, New York, NY, USA, pp 420\u2013429. https:\/\/doi.org\/10.1145\/1281192.1281239","DOI":"10.1145\/1281192.1281239"},{"issue":"1","key":"360_CR16","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions\u2014i. Math Program 14(1):265\u2013294. https:\/\/doi.org\/10.1007\/BF01588971","journal-title":"Math Program"},{"issue":"2","key":"360_CR17","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.prevetmed.2010.12.009","volume":"99","author":"M N\u00f6remark","year":"2011","unstructured":"N\u00f6remark M, H\u00e5kansson N, Lewerin SS, Lindberg A, Jonsson A (2011) Network analysis of cattle and pig movements in sweden: measures relevant for disease control and risk based surveillance. Prev Vet Med 99(2):78\u201390. https:\/\/doi.org\/10.1016\/j.prevetmed.2010.12.009","journal-title":"Prev Vet Med"},{"key":"360_CR18","first-page":"392","volume-title":"Complex Netw Their Appl VII","author":"G Panagopoulos","year":"2019","unstructured":"Panagopoulos G, Malliaros FD, Vazirgiannis M (2019) DiffuGreedy: an influence maximization algorithm based on diffusion cascades. In: Aiello LM, Cherifi C, Cherifi H, Lambiotte R, Li\u00f3 P, Rocha LM (eds) Complex Netw Their Appl VII. Springer, Cham, pp 392\u2013404"},{"key":"360_CR19","doi-asserted-by":"publisher","first-page":"3200","DOI":"10.1103\/PhysRevLett.86.3200","volume":"86","author":"R Pastor-Satorras","year":"2001","unstructured":"Pastor-Satorras R, Vespignani A (2001) Epidemic spreading in scale-free networks. Phys Rev Lett 86:3200\u20133203. https:\/\/doi.org\/10.1103\/PhysRevLett.86.3200","journal-title":"Phys Rev Lett"},{"issue":"3","key":"360_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pcbi.1001109","volume":"7","author":"LEC Rocha","year":"2011","unstructured":"Rocha LEC, Liljeros F, Holme P (2011) Simulated epidemics in an empirical spatiotemporal network of 50,185 sexual contacts. PLOS Comput Biol 7(3):1\u20139. https:\/\/doi.org\/10.1371\/journal.pcbi.1001109","journal-title":"PLOS Comput Biol"},{"key":"360_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-10-5287-3_10","volume-title":"Temporal network epidemiology. theoretical biology","author":"F Schirdewahn","year":"2017","unstructured":"Schirdewahn F, Colizza V, Lentz HHK, Koher A, Belik V, H\u00f6vel P (2017) Surveillance for outbreak detection in livestock-trade networks. In: Masuda N, Holme P (eds) Temporal network epidemiology. theoretical biology. Springer, Singapore. https:\/\/doi.org\/10.1007\/978-981-10-5287-3_10"},{"key":"360_CR24","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.cpc.2019.02.008","volume":"240","author":"G St-Onge","year":"2019","unstructured":"St-Onge G, Young J-G, H\u00e9bert-Dufresne L, Dub\u00e9 LJ (2019) Efficient sampling of spreading processes on complex networks using a composition and rejection algorithm. Comput Phys Commun 240:30\u201337. https:\/\/doi.org\/10.1016\/j.cpc.2019.02.008","journal-title":"Comput Phys Commun"},{"issue":"5","key":"360_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pone.0217974","volume":"14","author":"M Sterchi","year":"2019","unstructured":"Sterchi M, Faverjon C, Sarasua C, Vargas ME, Berezowski J, Bernstein A, Gr\u00fctter R, Nathues H (2019) The pig transport network in Switzerland: structure, patterns, and implications for the transmission of infectious diseases between animal holdings. PLOS ONE 14(5):1\u201320. https:\/\/doi.org\/10.1371\/journal.pone.0217974","journal-title":"PLOS ONE"},{"key":"360_CR23","first-page":"481","volume-title":"Complex Netw Their Appl VIII","author":"M Sterchi","year":"2020","unstructured":"Sterchi M, Sarasua C, Gr\u00fctter R, Bernstein A (2020) Maximizing the likelihood of detecting outbreaks in temporal networks. In: Cherifi H, Gaito S, Mendes JF, Moro E, Rocha LM (eds) Complex Netw Their Appl VIII. Springer, Cham, pp 481\u2013493"},{"issue":"1","key":"360_CR25","doi-asserted-by":"publisher","first-page":"5099","DOI":"10.1038\/srep05099","volume":"4","author":"L Sun","year":"2014","unstructured":"Sun L, Axhausen KW, Lee D-H, Cebrian M (2014) Efficient detection of contagious outbreaks in massive metropolitan encounter networks. Sci Rep 4(1):5099. https:\/\/doi.org\/10.1038\/srep05099","journal-title":"Sci Rep"},{"issue":"3","key":"360_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pcbi.1004152","volume":"11","author":"E Valdano","year":"2015","unstructured":"Valdano E, Poletto C, Giovannini A, Palma D, Savini L, Colizza V (2015) Predicting epidemic risk from past temporal contact data. PLOS Comput Biol 11(3):1\u201319. https:\/\/doi.org\/10.1371\/journal.pcbi.1004152","journal-title":"PLOS Comput Biol"},{"issue":"10","key":"360_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pcbi.1004579","volume":"11","author":"CL Vestergaard","year":"2015","unstructured":"Vestergaard CL, G\u00e9nois M (2015) Temporal Gillespie algorithm: fast simulation of contagion processes on time-varying networks. PLOS Comput Biol 11(10):1\u201328. https:\/\/doi.org\/10.1371\/journal.pcbi.1004579","journal-title":"PLOS Comput Biol"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00360-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s41109-021-00360-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00360-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T20:49:18Z","timestamp":1613767758000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-021-00360-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,19]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["360"],"URL":"https:\/\/doi.org\/10.1007\/s41109-021-00360-z","relation":{},"ISSN":["2364-8228"],"issn-type":[{"value":"2364-8228","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,19]]},"assertion":[{"value":"27 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"17"}}