{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T04:20:28Z","timestamp":1771474828497,"version":"3.50.1"},"reference-count":47,"publisher":"Public Library of Science (PLoS)","issue":"11","license":[{"start":{"date-parts":[[2022,11,22]],"date-time":"2022-11-22T00:00:00Z","timestamp":1669075200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1757923"],"award-info":[{"award-number":["1757923"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1838251"],"award-info":[{"award-number":["1838251"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["www.ploscompbiol.org"],"crossmark-restriction":false},"short-container-title":["PLoS Comput Biol"],"abstract":"<jats:p>Network science has increasingly become central to the field of epidemiology and our ability to respond to infectious disease threats. However, many networks derived from modern datasets are not just large, but dense, with a high ratio of edges to nodes. This includes human mobility networks where most locations have a large number of links to many other locations. Simulating large-scale epidemics requires substantial computational resources and in many cases is practically infeasible. One way to reduce the computational cost of simulating epidemics on these networks is <jats:italic>sparsification<\/jats:italic>, where a representative subset of edges is selected based on some measure of their importance. We test several sparsification strategies, ranging from naive thresholding to random sampling of edges, on mobility data from the U.S. Following recent work in computer science, we find that the most accurate approach uses the <jats:italic>effective resistances<\/jats:italic> of edges, which prioritizes edges that are the only efficient way to travel between their endpoints. The resulting sparse network preserves many aspects of the behavior of an SIR model, including both global quantities, like the epidemic size, and local details of stochastic events, including the probability each node becomes infected and its distribution of arrival times. This holds even when the sparse network preserves fewer than 10% of the edges of the original network. In addition to its practical utility, this method helps illuminate which links of a weighted, undirected network are most important to disease spread.<\/jats:p>","DOI":"10.1371\/journal.pcbi.1010650","type":"journal-article","created":{"date-parts":[[2022,11,22]],"date-time":"2022-11-22T18:32:51Z","timestamp":1669141971000},"page":"e1010650","update-policy":"https:\/\/doi.org\/10.1371\/journal.pcbi.corrections_policy","source":"Crossref","is-referenced-by-count":8,"title":["Effective resistance against pandemics: Mobility network sparsification for high-fidelity epidemic simulations"],"prefix":"10.1371","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6295-1416","authenticated-orcid":true,"given":"Alexander","family":"Mercier","sequence":"first","affiliation":[]},{"given":"Samuel","family":"Scarpino","sequence":"additional","affiliation":[]},{"given":"Cristopher","family":"Moore","sequence":"additional","affiliation":[]}],"member":"340","published-online":{"date-parts":[[2022,11,22]]},"reference":[{"issue":"6208","key":"pcbi.1010650.ref001","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1126\/science.346.6208.433-a","article-title":"Ebola: mobility data","volume":"346","author":"ME Halloran","year":"2014","journal-title":"Science"},{"key":"pcbi.1010650.ref002","author":"N Oliver","year":"2020","journal-title":"Mobile phone data for informing public health actions across the COVID-19 pandemic life cycle"},{"issue":"38","key":"pcbi.1010650.ref003","doi-asserted-by":"crossref","first-page":"11887","DOI":"10.1073\/pnas.1504964112","article-title":"Impact of human mobility on the emergence of dengue epidemics in Pakistan","volume":"112","author":"A Wesolowski","year":"2015","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"11","key":"pcbi.1010650.ref004","doi-asserted-by":"crossref","first-page":"3747","DOI":"10.1073\/pnas.0400087101","article-title":"The architecture of complex weighted networks","volume":"101","author":"A Barrat","year":"2004","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"pcbi.1010650.ref005","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1007\/978-3-319-50806-1","volume-title":"Mathematics of epidemics on networks","author":"IZ Kiss","year":"2017"},{"key":"pcbi.1010650.ref006","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.physrep.2018.01.001","article-title":"Human mobility: Models and applications","volume":"734","author":"H Barbosa","year":"2018","journal-title":"Physics Reports"},{"issue":"7860","key":"pcbi.1010650.ref007","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1038\/s41586-021-03480-9","article-title":"The universal visitation law of human mobility","volume":"593","author":"M Schlapfer","year":"2021","journal-title":"Nature"},{"key":"pcbi.1010650.ref008","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.epidem.2014.07.003","article-title":"Eight challenges for network epidemic models.","volume":"10","author":"L Pellis","year":"2015","journal-title":"Epidemics."},{"issue":"4","key":"pcbi.1010650.ref009","doi-asserted-by":"crossref","first-page":"042304","DOI":"10.1103\/PhysRevE.98.042304","article-title":"Weight thresholding on complex networks","volume":"98","author":"X Yan","year":"2018","journal-title":"Physical Review E"},{"issue":"6","key":"pcbi.1010650.ref010","doi-asserted-by":"crossref","first-page":"1360","DOI":"10.1086\/225469","article-title":"The strength of weak ties","volume":"78","author":"MS Granovetter","year":"1973","journal-title":"American Journal of Sociology"},{"issue":"6","key":"pcbi.1010650.ref011","doi-asserted-by":"crossref","first-page":"1913","DOI":"10.1137\/080734029","article-title":"Graph sparsification by effective resistances","volume":"40","author":"DA Spielman","year":"2011","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"pcbi.1010650.ref012","doi-asserted-by":"crossref","first-page":"981","DOI":"10.1137\/08074489X","article-title":"Spectral sparsification of graphs","volume":"40","author":"DA Spielman","year":"2011","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"pcbi.1010650.ref013","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1038\/s41567-021-01222-2","article-title":"One outstanding path from A to B","volume":"17","author":"S Shugars","year":"2021","journal-title":"Nature Physics"},{"issue":"2","key":"pcbi.1010650.ref014","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1080\/0022250X.2001.9990249","article-title":"A faster algorithm for betweenness centrality","volume":"25","author":"U. Brandes","year":"2001","journal-title":"The Journal of Mathematical Sociology"},{"issue":"16","key":"pcbi.1010650.ref015","doi-asserted-by":"crossref","first-page":"6483","DOI":"10.1073\/pnas.0808904106","article-title":"Extracting the multiscale backbone of complex weighted networks.","volume":"106","author":"M\u00c1 Serrano","year":"2009","journal-title":"Proceedings of the national academy of sciences"},{"issue":"6","key":"pcbi.1010650.ref016","doi-asserted-by":"crossref","DOI":"10.1093\/comnet\/cnab021","article-title":"The distance backbone of complex networks","volume":"9","author":"T Simas","year":"2021","journal-title":"Journal of Complex Networks"},{"issue":"12","key":"pcbi.1010650.ref017","doi-asserted-by":"crossref","DOI":"10.1073\/pnas.2022598118","article-title":"The effective graph reveals redundancy, canalization, and control pathways in biochemical regulation and signaling","volume":"118","author":"AJ Gates","year":"2021","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"1","key":"pcbi.1010650.ref018","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0378-8733(89)90016-6","article-title":"Rethinking centrality: Methods and examples.","volume":"11","author":"K Stephenson","year":"1989","journal-title":"Social Networks."},{"issue":"3","key":"pcbi.1010650.ref019","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1016\/j.socnet.2013.05.003","article-title":"Resistance distance, closeness, and betweenness.","volume":"35","author":"E Bozzo","year":"2013","journal-title":"Social Networks"},{"key":"pcbi.1010650.ref020","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-319-30569-1_1","volume-title":"Complex Networks VII","author":"AS Teixeira","year":"2016"},{"issue":"1","key":"pcbi.1010650.ref021","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1017\/nws.2014.4","article-title":"Structure of complex networks: Quantifying edge-to-edge relations by failure-induced flow redistribution","volume":"2","author":"MT Schaub","year":"2014","journal-title":"Network Science"},{"key":"pcbi.1010650.ref022","article-title":"Effective resistances, statistical leverage, and applications to linear equation solving.","author":"P Drineas","year":"2010","journal-title":"arXiv preprint arXiv:10053097"},{"key":"pcbi.1010650.ref023","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern Graph Theory","author":"B Bollob\u00b4as","year":"1998"},{"issue":"3","key":"pcbi.1010650.ref024","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1103\/RevModPhys.87.925","article-title":"Epidemic processes in complex networks","volume":"87","author":"R Pastor-Satorras","year":"2015","journal-title":"Reviews of Modern Physics"},{"key":"pcbi.1010650.ref025","doi-asserted-by":"crossref","unstructured":"Van Mieghemy P, Sahnehz FD, Scoglioz C. An upper bound for the epidemic threshold in exact Markovian SIR and SIS epidemics on networks. In: 53rd IEEE Conference on Decision and Control. IEEE; 2014. p. 6228\u20136233.","DOI":"10.1109\/CDC.2014.7040365"},{"key":"pcbi.1010650.ref026","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: An Introduction","author":"MEJ Newman","year":"2010"},{"key":"pcbi.1010650.ref027","author":"S Swarup","year":"2016","journal-title":"Identifying Core Network Structure for Epidemic Simulations"},{"key":"pcbi.1010650.ref028","article-title":"The role of directionality, heterogeneity and correlations in epidemic risk and spread.","author":"A Allard","year":"2020","journal-title":"arXiv preprint arXiv:200511283."},{"issue":"4","key":"pcbi.1010650.ref029","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/0021-9991(76)90041-3","article-title":"A general method for numerically simulating the stochastic time evolution of coupled chemical reactions","volume":"22","author":"DT Gillespie","year":"1976","journal-title":"Journal of Computational Physics"},{"key":"pcbi.1010650.ref030","unstructured":"Koutis I, Levin A, Peng R. Improved spectral sparsification and numerical algorithms for SDD matrices. In: STACS\u201912 (29th Symposium on Theoretical Aspects of Computer Science). vol. 14. LIPIcs; 2012. p. 266\u2013277."},{"issue":"172","key":"pcbi.1010650.ref031","doi-asserted-by":"crossref","first-page":"20200393","DOI":"10.1098\/rsif.2020.0393","article-title":"Beyond R0: heterogeneity in secondary infections and probabilistic epidemic forecasting","volume":"17","author":"L H\u00b4ebert-Dufresne","year":"2020","journal-title":"Journal of the Royal Society Interface"},{"issue":"2","key":"pcbi.1010650.ref032","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1023\/A:1026543900054","article-title":"The earth mover\u2019s distance as a metric for image retrieval","volume":"40","author":"Y Rubner","year":"2000","journal-title":"International Journal of Computer Vision"},{"issue":"51","key":"pcbi.1010650.ref033","doi-asserted-by":"crossref","first-page":"21484","DOI":"10.1073\/pnas.0906910106","article-title":"Multiscale mobility networks and the spatial spreading of infectious diseases","volume":"106","author":"D Balcan","year":"2009","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"7","key":"pcbi.1010650.ref034","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1038\/nphys1944","article-title":"Phase transitions in contagion processes mediated by recurrent mobility patterns","volume":"7","author":"D Balcan","year":"2011","journal-title":"Nature Physics"},{"key":"pcbi.1010650.ref035","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.jtbi.2013.08.032","article-title":"Human mobility and time spent at destination: impact on spatial epidemic spreading","volume":"338","author":"C Poletto","year":"2013","journal-title":"Journal of Theoretical Biology"},{"issue":"6487","key":"pcbi.1010650.ref036","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1126\/science.abb8021","article-title":"Aggregated mobility data could help fight COVID-19","volume":"368","author":"CO Buckee","year":"2020","journal-title":"Science"},{"issue":"9","key":"pcbi.1010650.ref037","doi-asserted-by":"crossref","first-page":"e2020485","DOI":"10.1001\/jamanetworkopen.2020.20485","article-title":"Association of Mobile Phone Location Data Indications of Travel and Stay-at-Home Mandates With COVID-19 Infection Rates in the US","volume":"3","author":"S Gao","year":"2020","journal-title":"JAMA Network Open"},{"issue":"7840","key":"pcbi.1010650.ref038","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1038\/s41586-020-2923-3","article-title":"Mobility network models of COVID-19 explain inequities and inform reopening","volume":"589","author":"S Chang","year":"2021","journal-title":"Nature"},{"key":"pcbi.1010650.ref039","first-page":"368","article-title":"The Effect of Travel Restrictions on the Spread of the 2019 Novel Coronavirus (COVID-19) Outbreak.","author":"M Chinazzi","year":"2020","journal-title":"Science"},{"issue":"6490","key":"pcbi.1010650.ref040","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1126\/science.abb4218","article-title":"The effect of human mobility and control measures on the COVID-19 epidemic in China.","volume":"368","author":"MUG Kraemer","year":"2020","journal-title":"Science"},{"key":"pcbi.1010650.ref041","article-title":"Reshaping a nation: Mobility, commuting, and contact patterns during the COVID-19 outbreak.","author":"B Klein","year":"2020","journal-title":"Northeastern University-Network Science Institute Report"},{"issue":"1","key":"pcbi.1010650.ref042","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41467-020-18271-5","article-title":"Reductions in commuting mobility correlate with geographic differences in SARS-CoV-2 prevalence in New York City.","volume":"11","author":"SM Kissler","year":"2020","journal-title":"Nature Communications"},{"issue":"1\u20132","key":"pcbi.1010650.ref043","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0025-5564(94)00068-B","article-title":"A structured epidemic model incorporating geographic mobility among regions","volume":"128","author":"L Sattenspiel","year":"1995","journal-title":"Mathematical Biosciences"},{"issue":"3","key":"pcbi.1010650.ref044","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1016\/j.jtbi.2007.12.001","article-title":"Global disease spread: statistics and estimation of arrival times","volume":"251","author":"A Gautreau","year":"2008","journal-title":"Journal of Theoretical Biology"},{"issue":"4","key":"pcbi.1010650.ref045","doi-asserted-by":"crossref","first-page":"042301","DOI":"10.1103\/PhysRevE.102.042301","article-title":"Calculation of epidemic arrival time distributions using branching processes","volume":"102","author":"A Jamieson-Lane","year":"2020","journal-title":"Physical Review E"},{"key":"pcbi.1010650.ref046","article-title":"Eon (epidemics on networks): a fast, flexible Python package for simulation, analytic approximation, and analysis of epidemics on networks.","author":"JC Miller","year":"2020","journal-title":"arXiv preprint arXiv:200102436."},{"key":"pcbi.1010650.ref047","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.cpc.2019.02.008","article-title":"Efficient sampling of spreading processes on complex networks using a composition and rejection algorithm","volume":"240","author":"G St-Onge","year":"2019","journal-title":"Computer Physics Communications"}],"container-title":["PLOS Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1010650","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,22]],"date-time":"2022-11-22T18:33:49Z","timestamp":1669142029000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1010650"}},"subtitle":[],"editor":[{"given":"Feng","family":"Fu","sequence":"first","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2022,11,22]]},"references-count":47,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2022,11,22]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pcbi.1010650","relation":{},"ISSN":["1553-7358"],"issn-type":[{"value":"1553-7358","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,22]]}}}