{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T22:37:25Z","timestamp":1740177445370,"version":"3.37.3"},"reference-count":73,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,8,21]],"date-time":"2023-08-21T00:00:00Z","timestamp":1692576000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,21]],"date-time":"2023-08-21T00:00:00Z","timestamp":1692576000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021-182407","200021-182407"],"award-info":[{"award-number":["200021-182407","200021-182407"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"name":"EPFL Lausanne"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Inferring the source of a diffusion in a large network of agents is a difficult but feasible task, if a few agents act as sensors revealing the time at which they got hit by the diffusion. One of the main limitations of current source identification algorithms is that they assume full knowledge of the contact network, which is rarely the case, especially for epidemics, where the source is called patient zero. Inspired by recent implementations of contact tracing algorithms, we propose a new framework, which we call Source Identification via Contact Tracing Framework (SICTF). In the SICTF, the source identification task starts at the time of the first hospitalization, and initially we have no knowledge about the contact network other than the identity of the first hospitalized agent. We may then explore the network by contact queries, and obtain symptom onset times by test queries in an adaptive way, i.e., both contact and test queries can depend on the outcome of previous queries. We also assume that some of the agents may be asymptomatic, and therefore cannot reveal their symptom onset time. Our goal is to find patient zero with as few contact and test queries as possible. We implement two local search algorithms for the SICTF: the LS algorithm, which has recently been proposed by Waniek et al. in a similar framework, is more data-efficient, but can fail to find the true source if many asymptomatic agents are present, whereas the LS+ algorithm is more robust to asymptomatic agents. By simulations we show that both LS and LS+ outperform previously proposed adaptive and non-adaptive source identification algorithms adapted to the SICTF, even though these baseline algorithms have full access to the contact network. Extending the theory of random exponential trees, we analytically approximate the source identification probability of the LS\/ LS+ algorithms, and we show that our analytic results match the simulations. Finally, we benchmark our algorithms on the Data-driven COVID-19 Simulator (DCS) developed by Lorch et al., which is the first time source identification algorithms are tested on such a complex dataset.<\/jats:p>","DOI":"10.1007\/s41109-023-00566-3","type":"journal-article","created":{"date-parts":[[2023,8,21]],"date-time":"2023-08-21T15:02:05Z","timestamp":1692630125000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Source identification via contact tracing in the presence of asymptomatic patients"],"prefix":"10.1007","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9139-249X","authenticated-orcid":false,"given":"Gergely","family":"\u00d3dor","sequence":"first","affiliation":[]},{"given":"Jana","family":"Vuckovic","sequence":"additional","affiliation":[]},{"given":"Miguel-Angel Sanchez","family":"Ndoye","sequence":"additional","affiliation":[]},{"given":"Patrick","family":"Thiran","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,21]]},"reference":[{"issue":"2020","key":"566_CR1","doi-asserted-by":"publisher","first-page":"171325","DOI":"10.1109\/ACCESS.2020.3025971","volume":"8","author":"NY Ahn","year":"2020","unstructured":"Ahn NY, Park JE, Lee DH, Hong PC (2020) Balancing personal privacy and public safety during COVID-19: the case of South Korea. Ieee Access 8(2020):171325\u2013171333","journal-title":"Ieee Access"},{"issue":"2014","key":"566_CR2","doi-asserted-by":"publisher","first-page":"P10016","DOI":"10.1088\/1742-5468\/2014\/10\/P10016","volume":"10","author":"F Altarelli","year":"2014","unstructured":"Altarelli F, Braunstein A, Dall\u2019Asta L, Ingrosso A, Zecchina R (2014) The patient-zero problem with noisy observations. J Stat Mech Theory Exp 10(2014):P10016","journal-title":"J Stat Mech Theory Exp"},{"key":"566_CR3","unstructured":"Auffinger A, Damron M, Hanson J (2015) 50 years of first passage percolation. Preprint arXiv:1511.03262"},{"issue":"3","key":"566_CR4","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.jocs.2010.07.002","volume":"1","author":"D Balcan","year":"2010","unstructured":"Balcan D, Gon\u00e7alves B, Hao H, Ramasco JJ, Colizza V, Vespignani A (2010) Modeling the spatial spread of infectious diseases: the GLobal Epidemic and Mobility computational model. J Comput Sci 1(3):132\u2013145","journal-title":"J Comput Sci"},{"issue":"3","key":"566_CR5","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1239\/aap\/1253281063","volume":"41","author":"F Ball","year":"2009","unstructured":"Ball F, Sirl D, Trapman P (2009) Threshold behaviour and final outcome of an epidemic on a random network with household structure. Adv Appl Probab 41(3):765\u2013796","journal-title":"Adv Appl Probab"},{"key":"566_CR6","unstructured":"BeidasRinad S, ButtenheimAlison M, KilaruAustin S, AschDavid A, VolppKevin G, LawmanHannah G, CannuscioCarolyn C, et\u00a0al. (2020) Optimizing and implementing contact tracing through behavioral economics. NEJM Catalyst Innovations in Care Delivery"},{"key":"566_CR7","doi-asserted-by":"crossref","unstructured":"Benjamini I, Schramm O (2011) Recurrence of distributional limits of finite planar graphs. In: Selected works of oded schramm. Springer, pp 533\u2013545","DOI":"10.1007\/978-1-4419-9675-6_15"},{"issue":"1","key":"566_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41467-020-20325-7","volume":"12","author":"WJ Bradshaw","year":"2021","unstructured":"Bradshaw WJ, Alley EC, Huggins JH, Lloyd AL, Esvelt KM (2021) Bidirectional contact tracing could dramatically improve COVID-19 control. Nat Commun 12(1):1\u20139","journal-title":"Nat Commun"},{"key":"566_CR9","doi-asserted-by":"crossref","unstructured":"Braithwaite I, Callender T, Bullock M, Aldridge RW (2020) Automated and partly automated contact tracing: a systematic review to inform the control of COVID-19. The Lancet Digital Health (2020)","DOI":"10.1101\/2020.05.27.20114447"},{"key":"566_CR10","doi-asserted-by":"publisher","unstructured":"Carinci F (2020) Covid-19: preparedness, decentralisation, and the hunt for patient zero. https:\/\/doi.org\/10.1136\/bmj.m799","DOI":"10.1136\/bmj.m799"},{"issue":"2021","key":"566_CR11","doi-asserted-by":"publisher","first-page":"2621","DOI":"10.1109\/TIFS.2021.3050604","volume":"16","author":"Y Chai","year":"2021","unstructured":"Chai Y, Wang Y, Zhu L (2021) Information sources estimation in time-varying networks. IEEE Trans Inf For Secur 16(2021):2621\u20132636. https:\/\/doi.org\/10.1109\/TIFS.2021.3050604","journal-title":"IEEE Trans Inf For Secur"},{"issue":"7840","key":"566_CR12","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1038\/s41586-020-2923-3","volume":"589","author":"S Chang","year":"2021","unstructured":"Chang S, Pierson E, Koh PW, Gerardin J, Redbird B, Grusky D, Leskovec J (2021) Mobility network models of COVID-19 explain inequities and inform reopening. Nature 589(7840):82\u201387","journal-title":"Nature"},{"key":"566_CR13","doi-asserted-by":"crossref","unstructured":"Chen S, Yu P-D, Tan CW, Poor HV (2022) Identifying the superspreader in proactive backward contact tracing by deep learning. In: 2022 56th annual conference on information sciences and systems (CISS). IEEE, pp 43\u201348","DOI":"10.1109\/CISS53076.2022.9751196"},{"key":"566_CR14","unstructured":"Dawkins Q, Li T, Xu H (2021) Diffusion Source Identification on Networks with Statistical Confidence. In Proceedings of the 38th international conference on machine learning (Proceedings of machine learning research, Vol\u00a0139). PMLR, pp 2500\u20132509"},{"key":"566_CR15","doi-asserted-by":"crossref","unstructured":"Drmota M (2009) Random trees: an interplay between combinatorics and probability. Springer","DOI":"10.1007\/978-3-211-75357-6"},{"key":"566_CR16","doi-asserted-by":"crossref","unstructured":"Endo A et\u00a0al (2020) Implication of backward contact tracing in the presence of overdispersed transmission in COVID-19 outbreaks. Wellcome Open Res 5","DOI":"10.12688\/wellcomeopenres.16344.1"},{"key":"566_CR17","doi-asserted-by":"crossref","unstructured":"Fan L, Li B, Liu D, Dai H, Ru Y (2020) Identifying propagation source in temporal networks based on label propagation. In: International conference of pioneering computer scientists, engineers and educators. Springer, pp 72\u201388","DOI":"10.1007\/978-981-15-7981-3_6"},{"issue":"2021","key":"566_CR18","doi-asserted-by":"publisher","DOI":"10.3389\/fpubh.2021.670669","volume":"9","author":"M Feng","year":"2021","unstructured":"Feng M, Ling Q, Xiong J, Manyande A, Weiguo X, Xiang B (2021) Occupational characteristics and management measures of sporadic COVID-19 outbreaks from June 2020 to January 2021 in China: the importance of tracking down \u201cpatient zero\u2019\u2019. Front Public Health 9(2021):670669","journal-title":"Front Public Health"},{"issue":"2","key":"566_CR19","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/s11009-017-9578-z","volume":"20","author":"Y Feng","year":"2018","unstructured":"Feng Y, Mahmoud H (2018) Profile of random exponential binary trees. Methodol Comput Appl Probab 20(2):575\u2013587","journal-title":"Methodol Comput Appl Probab"},{"issue":"2008","key":"566_CR20","first-page":"81","volume":"5","author":"C Hernando","year":"2008","unstructured":"Hernando C, Mora M, Slater PJ, Wood DR (2008) Fault-tolerant metric dimension of graphs. Convexity Discrete Struct 5(2008):81\u201385","journal-title":"Convexity Discrete Struct"},{"key":"566_CR21","doi-asserted-by":"crossref","unstructured":"Huang Q (2017) Source locating of spreading dynamics in temporal networks. In: Proceedings of the 26th international conference on world wide web companion, pp 723\u2013727","DOI":"10.1145\/3041021.3053376"},{"issue":"12","key":"566_CR22","doi-asserted-by":"publisher","DOI":"10.1002\/ctm2.685","volume":"11","author":"NE Ingraham","year":"2021","unstructured":"Ingraham NE, Ingbar DH (2021) The omicron variant of SARS-CoV-2: understanding the known and living with unknowns. Clin Transl Med 11(12):e685. https:\/\/doi.org\/10.1002\/ctm2.685","journal-title":"Clin Transl Med"},{"issue":"2","key":"566_CR23","doi-asserted-by":"publisher","first-page":"221","DOI":"10.2307\/1427068","volume":"16","author":"P Jagers","year":"1984","unstructured":"Jagers P, Nerman O (1984) The growth and composition of branching populations. Adv Appl Probab 16(2):221\u2013259","journal-title":"Adv Appl Probab"},{"issue":"1","key":"566_CR24","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1109\/TDSC.2016.2522436","volume":"15","author":"J Jiang","year":"2016","unstructured":"Jiang J, Wen S, Shui Yu, Xiang Y, Zhou W (2016) Rumor source identification in social networks with time-varying topology. IEEE Trans Dependable Secure Comput 15(1):166\u2013179","journal-title":"IEEE Trans Dependable Secure Comput"},{"key":"566_CR25","doi-asserted-by":"crossref","unstructured":"Kandeel M, Elsayed\u00a0Mohamed Mohamed M, Abd El-Lateef HM, Venugopala N, El-Beltagi HS (2021) Omicron variant genome evolution and phylogenetics. J Med Virol","DOI":"10.1002\/jmv.27515"},{"issue":"1","key":"566_CR26","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.82.016101","volume":"82","author":"B Karrer","year":"2010","unstructured":"Karrer B, Newman MEJ (2010) Message passing approach for general epidemic models. Phys Rev E 82(1):016101. https:\/\/doi.org\/10.1103\/PhysRevE.82.016101","journal-title":"Phys Rev E"},{"issue":"1","key":"566_CR27","doi-asserted-by":"publisher","first-page":"858","DOI":"10.1038\/s41467-023-36495-z","volume":"14","author":"M Kendall","year":"2023","unstructured":"Kendall M, Tsallis D, Wymant C, Di Francia A, Balogun Y, Didelot X, Ferretti L, Fraser C (2023) Epidemiological impacts of the NHS COVID-19 app in England and Wales throughout its first year. Nat Commun 14(1):858","journal-title":"Nat Commun"},{"key":"566_CR28","first-page":"1","volume":"2021","author":"S Kojaku","year":"2021","unstructured":"Kojaku S, H\u00e9bert-Dufresne L, Mones E, Lehmann S, Ahn Y-Y (2021) The effectiveness of backward contact tracing in networks. Nat Phys 2021:1\u20137","journal-title":"Nat Phys"},{"key":"566_CR29","doi-asserted-by":"crossref","unstructured":"Kopel J, Goyal H, Perisetti A (2021) Antibody tests for COVID-19. In: Baylor University medical center proceedings, Vol\u00a034. Taylor & Francis, pp 63\u201372","DOI":"10.1080\/08998280.2020.1829261"},{"issue":"8","key":"566_CR30","doi-asserted-by":"publisher","first-page":"e452","DOI":"10.1016\/S2468-2667(20)30157-2","volume":"5","author":"ME Kretzschmar","year":"2020","unstructured":"Kretzschmar ME, Rozhnova G, Bootsma MCJ, van Boven M, van de Wijgert JHHM, Bonten MJM (2020) Impact of delays on effectiveness of contact tracing strategies for COVID-19: a modelling study. Lancet Public Health 5(8):e452\u2013e459","journal-title":"Lancet Public Health"},{"key":"566_CR31","doi-asserted-by":"crossref","unstructured":"Kupferschmidt K (2021) Where did \u2018weird\u2019Omicron come from? American Association for the Advancement of Science","DOI":"10.1126\/science.acx9738"},{"key":"566_CR32","doi-asserted-by":"crossref","unstructured":"Lecomte V, \u00d3dor G, Thiran P (2020) The power of adaptivity in source location on the path. Theoretical Computer Science, Vol. 911, pp 92-123, 2022. Preprint arXiv:2002.07336","DOI":"10.1016\/j.tcs.2022.02.008"},{"issue":"2","key":"566_CR33","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1111\/all.14622","volume":"76","author":"Q Lei","year":"2021","unstructured":"Lei Q, Li Y, Hou H, Wang F, Ouyang Z, Zhang Y, Lai D, Ndzouboukou J-LB, Zhao-wei X, Zhang B et al (2021) Antibody dynamics to SARS-CoV-2 in asymptomatic COVID-19 infections. Allergy 76(2):551\u2013561","journal-title":"Allergy"},{"issue":"18","key":"566_CR34","doi-asserted-by":"publisher","first-page":"3758","DOI":"10.3390\/app9183758","volume":"9","author":"X Li","year":"2019","unstructured":"Li X, Wang X, Zhao C, Zhang X, Yi D (2019) Locating the source of diffusion in complex networks via Gaussian-based localization and deduction. Appl Sci 9(18):3758","journal-title":"Appl Sci"},{"issue":"1","key":"566_CR35","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.90.012801","volume":"90","author":"AY Lokhov","year":"2014","unstructured":"Lokhov AY, M\u00e9zard M, Ohta H, Zdeborov\u00e1 L (2014) Inferring the origin of an epidemic with a dynamic message-passing algorithm. Phys Rev E 90(1):012801","journal-title":"Phys Rev E"},{"issue":"4","key":"566_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3530774","volume":"8","author":"L Lorch","year":"2022","unstructured":"Lorch L, Kremer H, Trouleau W, Tsirtsis S, Szanto A, Sch\u00f6lkopf B, Gomez-Rodriguez M (2022) Quantifying the effects of contact tracing, testing, and containment measures in the presence of infection hotspots. ACM Trans Spat Algorithms Syst 8(4):1\u201328","journal-title":"ACM Trans Spat Algorithms Syst"},{"key":"566_CR37","unstructured":"Louni A, Santhanakrishnan A, Subbalakshmi KP (2015) Identification of source of rumors in social networks with incomplete information. Preprint arXiv:1509.00557"},{"key":"566_CR38","first-page":"1","volume":"2021","author":"H Mahmoud","year":"2021","unstructured":"Mahmoud H (2021) Profile of random exponential recursive trees. Methodol Comput Appl Probab 2021:1\u201317","journal-title":"Methodol Comput Appl Probab"},{"key":"566_CR39","unstructured":"Manitz J, Harbering J, Schmidt M, Kneib T, Sch\u00f6bel A (2014a) Network-based source detection: from infectious disease spreading to train delay propagation. In: 29th international workshop on statistical modelling, vol\u00a01, pp 201\u2013205"},{"key":"566_CR40","doi-asserted-by":"crossref","unstructured":"Manitz J, Kneib T, Schlather M, Helbing D, Brockmann D (2014b) Origin detection during food-borne disease outbreaks-A case study of the 2011 EHEC\/HUS outbreak in Germany. PLoS Curr 6","DOI":"10.1371\/currents.outbreaks.f3fdeb08c5b9de7c09ed9cbcef5f01f2"},{"key":"566_CR41","doi-asserted-by":"crossref","unstructured":"Mashkaria S, \u00d3dor G, Thiran P (2020) On the robustness of the metric dimension to adding a single edge. Discrete Applied Mathematics, Vol 316, pp. 1-27, 2022. Preprint arXiv:2010.11023","DOI":"10.1016\/j.dam.2022.02.014"},{"issue":"10","key":"566_CR42","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0259037","volume":"16","author":"SA M\u00fcller","year":"2021","unstructured":"M\u00fcller SA, Balmer M, Charlton W, Ewert R, Neumann A, Rakow C, Schlenther T, Nagel K (2021) Predicting the effects of COVID-19 related interventions in urban settings by combining activity-based modelling, agent-based simulation, and mobile phone data. PLoS ONE 16(10):e0259037","journal-title":"PLoS ONE"},{"key":"566_CR43","unstructured":"Odor G (2022) The Role of Adaptivity in Source Identification with Time Queries. Technical Report, EPFL"},{"issue":"2020","key":"566_CR44","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1016\/j.future.2020.06.023","volume":"112","author":"R Paluch","year":"2020","unstructured":"Paluch R, Gajewski \u0141G, Ho\u0142yst JA, Szymanski BK (2020a) Optimizing sensors placement in complex networks for localization of hidden signal source: a review. Fut Gen Comput Syst 112(2020):1070\u20131092","journal-title":"Fut Gen Comput Syst"},{"issue":"1","key":"566_CR45","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41598-018-20546-3","volume":"8","author":"R Paluch","year":"2018","unstructured":"Paluch R, Xiaoyan L, Suchecki K, Szyma\u0144ski BK, Ho\u0142yst JA (2018) Fast and accurate detection of spread source in large complex networks. Sci Rep 8(1):1\u201310","journal-title":"Sci Rep"},{"key":"566_CR46","unstructured":"Paluch R, Suchecki K, Ho\u0142yst JA (2020b) Locating the source of interacting signal in complex networks. Preprint arXiv:2012.02039"},{"issue":"10","key":"566_CR47","doi-asserted-by":"publisher","first-page":"2465","DOI":"10.3201\/eid2610.201315","volume":"26","author":"YJ Park","year":"2020","unstructured":"Park YJ, Choe YJ, Park O, Park SY, Kim Y-M, Kim J, Kweon S, Woo Y, Gwack J, Kim SS et al (2020) Contact tracing during coronavirus disease outbreak, South Korea, 2020. Emerg Infect Dis 26(10):2465","journal-title":"Emerg Infect Dis"},{"issue":"6","key":"566_CR48","first-page":"3","volume":"1","author":"J Perrenet","year":"2012","unstructured":"Perrenet J, Zwaneveld B (2012) The many faces of the mathematical modeling cycle. J Math Model Appl 1(6):3\u201321","journal-title":"J Math Model Appl"},{"key":"566_CR49","doi-asserted-by":"crossref","unstructured":"Pinto P, Thiran P, Vetterli M (2012) Locating the source of diffusion in large-scale networks. Phys Review Lett 109","DOI":"10.1103\/PhysRevLett.109.068702"},{"issue":"1","key":"566_CR50","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41467-022-32531-6","volume":"13","author":"J Raymenants","year":"2022","unstructured":"Raymenants J, Geenen C, Thibaut J, Nelissen K, Gorissen S, Andre E (2022) Empirical evidence on the efficiency of backward contact tracing in COVID-19. Nat Commun 13(1):1\u201313","journal-title":"Nat Commun"},{"issue":"10","key":"566_CR51","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0240649","volume":"15","author":"L Russo","year":"2020","unstructured":"Russo L, Anastassopoulou C, Tsakris A, Bifulco GN, Campana EF, Toraldo G, Siettos C (2020) Tracing day-zero and forecasting the COVID-19 outbreak in Lombardy, Italy: a compartmental modelling and numerical optimization approach. PLoS ONE 15(10):e0240649. https:\/\/doi.org\/10.1371\/journal.pone.0240649","journal-title":"PLoS ONE"},{"key":"566_CR52","doi-asserted-by":"crossref","unstructured":"Shah D, Zaman T (2010) Detecting sources of computer viruses in networks: theory and experiment. In: Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (New York, New York, USA) (SIGMETRICS \u201910). ACM, New York, NY, USA, pp 203\u2013214","DOI":"10.1145\/1811099.1811063"},{"issue":"8","key":"566_CR53","doi-asserted-by":"publisher","first-page":"5163","DOI":"10.1109\/TIT.2011.2158885","volume":"57","author":"D Shah","year":"2011","unstructured":"Shah D, Zaman T (2011) Rumors in a network: Who\u2019s the culprit? IEEE Trans Inf Theory 57(8):5163\u20135181","journal-title":"IEEE Trans Inf Theory"},{"issue":"2019","key":"566_CR54","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.osnem.2018.12.001","volume":"9","author":"S Shelke","year":"2019","unstructured":"Shelke S, Attar V (2019) Source detection of rumor in social network-a review. Online Soc Networks Media 9(2019):30\u201342","journal-title":"Online Soc Networks Media"},{"issue":"3","key":"566_CR55","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.93.032301","volume":"93","author":"Z Shen","year":"2016","unstructured":"Shen Z, Cao S, Wang W-X, Di Z, Eugene HS (2016) Locating the source of diffusion in complex networks by time-reversal backward spreading. Phys Review E 93(3):032301","journal-title":"Phys Review E"},{"issue":"2019","key":"566_CR56","volume":"527","author":"X Shuaishuai","year":"2019","unstructured":"Shuaishuai X, Teng C, Zhou Y, Peng J, Zhang Y, Zhang Z-K (2019) Identifying the diffusion source in complex networks with limited observers. Phys A 527(2019):121267","journal-title":"Phys A"},{"key":"566_CR57","unstructured":"Spinelli B, Celis E, Thiran P (2017a) A general framework for sensor placement in source localization. IEEE Trans Netw Sci Eng"},{"key":"566_CR58","doi-asserted-by":"crossref","unstructured":"Spinelli B, Celis LE, Thiran P (2017b) Back to the source: an online approach for sensor placement and source localization. In: Proceedings of the 26th international conference on world wide web, pp 1151\u20131160","DOI":"10.1145\/3038912.3052584"},{"issue":"1","key":"566_CR59","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/s41109-017-0040-5","volume":"2","author":"BL Spinelli","year":"2017","unstructured":"Spinelli BL, Celis E, Thiran P (2017c) The effect of transmission variance on observer placement for source-localization. Appl Netw Sci 2(1):20","journal-title":"Appl Netw Sci"},{"key":"566_CR60","doi-asserted-by":"crossref","unstructured":"Spinelli B, Celis LE, Thiran P (2018) How many sensors to localize the source? The double metric dimension of random networks. In: 2018 56th annual allerton conference on communication, control, and computing (Allerton). IEEE, pp 1036\u20131043","DOI":"10.1109\/ALLERTON.2018.8635897"},{"issue":"12","key":"566_CR61","doi-asserted-by":"publisher","first-page":"3035","DOI":"10.1109\/TIFS.2018.2837655","volume":"13","author":"W Tang","year":"2018","unstructured":"Tang W, Ji F, Tay WP (2018) Estimating infection sources in networks using partial timestamps. IEEE Trans Inf For Secur 13(12):3035\u20133049","journal-title":"IEEE Trans Inf For Secur"},{"key":"566_CR62","unstructured":"Troncoso C, Payer M, Hubaux J-P, Salath\u00e9 M, Larus J, Bugnion E, Lueks W, Stadler T, Pyrgelis A, Antonioli D et\u00a0al. (2020) Decentralized privacy-preserving proximity tracing. Preprint arXiv:2005.12273 (2020)"},{"issue":"1","key":"566_CR63","doi-asserted-by":"publisher","first-page":"22582","DOI":"10.1038\/s41598-022-26892-7","volume":"12","author":"M Waniek","year":"2022","unstructured":"Waniek M, Holme P, Farrahi K, Emonet R, Cebrian M, Rahwan T (2022) Trading contact tracing efficiency for finding patient zero. Sci Rep 12(1):22582","journal-title":"Sci Rep"},{"key":"566_CR64","first-page":"239","volume":"1999","author":"NC Wormald","year":"1999","unstructured":"Wormald NC et al (1999) Models of random regular graphs. Lond Math Soc Lect Note Ser 1999:239\u2013298","journal-title":"Lond Math Soc Lect Note Ser"},{"key":"566_CR65","unstructured":"Xie Y, Sekar V, Maltz DA, Reiter MK, Zhang H (2005) Worm origin identification using random moonwalks. In: 2005 IEEE symposium on security and privacy (S &P\u201905). IEEE, pp 242\u2013256"},{"issue":"2","key":"566_CR66","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1109\/JSTSP.2022.3153168","volume":"16","author":"P-D Yu","year":"2022","unstructured":"Yu P-D, Tan CW, Hung-Lin F (2022) Epidemic source detection in contact tracing networks: epidemic centrality in graphs and message-passing algorithms. IEEE J Sel Top Signal Process 16(2):234\u2013249","journal-title":"IEEE J Sel Top Signal Process"},{"key":"566_CR67","doi-asserted-by":"crossref","unstructured":"Zejnilovic S, Gomes J, Sinopoli B (2013) Network observability and localization of the source of diffusion based on a subset of nodes. In: 2013 51st annual allerton conference on communication, control, and computing (Allerton). IEEE, pp 847\u2013852","DOI":"10.1109\/Allerton.2013.6736613"},{"key":"566_CR68","doi-asserted-by":"crossref","unstructured":"Zejnilovi\u0107 S, Gomes J, Sinopoli B (2015) Sequential observer selection for source localization. In: 2015 IEEE Global Conference on signal and information processing (GlobalSIP). IEEE, pp 1220\u20131224","DOI":"10.1109\/GlobalSIP.2015.7418392"},{"key":"566_CR69","doi-asserted-by":"crossref","unstructured":"Zejnilovi\u0107 S, Gomes J, Sinopoli B (2017) Sequential source localization on graphs: a case study of cholera outbreak. In: 2017 IEEE global conference on signal and information processing (GlobalSIP). IEEE, pp 1010\u20131014","DOI":"10.1109\/GlobalSIP.2017.8309113"},{"issue":"2016","key":"566_CR70","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/j.tcs.2015.10.022","volume":"609","author":"S Zejnilovi\u0107","year":"2016","unstructured":"Zejnilovi\u0107 S, Mitsche D, Gomes J, Sinopoli B (2016) Extending the metric dimension to graphs with missing edges. Theoret Comput Sci 609(2016):384\u2013394","journal-title":"Theoret Comput Sci"},{"issue":"6","key":"566_CR71","doi-asserted-by":"publisher","DOI":"10.1016\/j.jinf.2020.03.032","volume":"80","author":"X Zhang","year":"2020","unstructured":"Zhang X, Chen X, Zhang Z, Roy A, Shen Y (2020) Strategies to trace back the origin of COVID-19. J Infect 80(6):e39","journal-title":"J Infect"},{"issue":"5","key":"566_CR72","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1007\/s10618-015-0435-9","volume":"30","author":"K Zhu","year":"2016","unstructured":"Zhu K, Chen Z, Ying L (2016) Locating the contagion source in networks with partial timestamps. Data Min Knowl Disc 30(5):1217\u20131248","journal-title":"Data Min Knowl Disc"},{"issue":"14","key":"566_CR73","doi-asserted-by":"publisher","first-page":"931","DOI":"10.1016\/j.physleta.2018.01.037","volume":"382","author":"H Zhao-Long","year":"2018","unstructured":"Zhao-Long H, Shen Z, Tang C-B, Xie B-B, Jian-Feng L (2018) Localization of diffusion sources in complex networks with sparse observations. Phys Lett A 382(14):931\u2013937","journal-title":"Phys Lett A"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-023-00566-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-023-00566-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-023-00566-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,22]],"date-time":"2023-11-22T03:08:46Z","timestamp":1700622526000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-023-00566-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,21]]},"references-count":73,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["566"],"URL":"https:\/\/doi.org\/10.1007\/s41109-023-00566-3","relation":{},"ISSN":["2364-8228"],"issn-type":[{"type":"electronic","value":"2364-8228"}],"subject":[],"published":{"date-parts":[[2023,8,21]]},"assertion":[{"value":"1 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 August 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"53"}}