Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-22T11:54:38.607Z Has data issue: false hasContentIssue false
  • English
  • Français

Forward reachable sets: Analytically derived properties of connected components for dynamic networks

Published online by Cambridge University Press:  29 June 2017

BENJAMIN ARMBRUSTER ,
LI WANG  and
MARTINA MORRIS
BENJAMIN ARMBRUSTER
Affiliation:
Northwestern University, Industrial Engineering and Management Sciences, Evanston, IL, USA (e-mail: [email protected])
LI WANG
Affiliation:
Statistics, University of Washington, Seattle, WA, USA (e-mails: [email protected], [email protected])
MARTINA MORRIS
Affiliation:
Statistics, University of Washington, Seattle, WA, USA (e-mails: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Formal analysis of the emergent structural properties of dynamic networks is largely uncharted territory. We focus here on the properties of forward reachable sets (FRS) as a function of the underlying degree distribution and edge duration. FRS are defined as the set of nodes that can be reached from an initial seed via a path of temporally ordered edges; a natural extension of connected component measures to dynamic networks. Working in a stochastic framework, we derive closed-form expressions for the mean and variance of the exponential growth rate of the FRS for temporal networks with both edge and node dynamics. For networks with node dynamics, we calculate thresholds for the growth of the FRS. The effects of finite population size are explored via simulation and approximation. We examine how these properties vary by edge duration and different cross-sectional degree distributions that characterize a range of scientifically interesting normative outcomes (Poisson and Bernoulli). The size of the forward reachable set gives an upper bound for the epidemic size in disease transmission network models, relating this work to epidemic modeling (Ferguson, 2000; Eames, 2004).

Keywords

networksdynamic networknetwork transmissionreachable setreachabilityepidemic size
Type
Research Article
Information
Network Science , Volume 5 , Special Issue 3: Networks and Health , September 2017 , pp. 328 - 354
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Baggaley, R. F., Garnett, G. P., & Ferguson, N. M. (2006). Modelling the impact of antiretroviral use in resource-poor settings. PLoS Medicine, 3 (4), e124.Google Scholar
Banks, H. T., Broido, A., Canter, I., Gayvert, K., Hu, S., Joyner, M., & Link, K. (2011). Simulation Algorithms for Continuous Time Markov Chain Models. Raleigh, NC: Tech. rept. North Carolina State University.Google Scholar
Bauch, C., & Rand, D. A. (2000). A moment closure model for sexually transmitted disease transmission through a concurrent partnership network. Proceedings of the Royal Society B: Biological Sciences, 267 (1456), 2019–2027.Google Scholar
Bender-deMoll, S., & Morris, M. (2015). tsna: Tools for Temporal Social Network Analysis (Version 0.2.0). Comprehensive R Archive Network (CRAN). Retrieved from https://cran.r-project.org/web/packages/tsna/index.html.Google Scholar
Britton, T., & Trapman, P. (2014). Stochastic epidemics in growing populations. Bulletin of Mathematical Biology, 76 (5), 985–996.Google Scholar
Dangerfield, C. E., Ross, J. V., & Keeling, M. J. (2009). Integrating stochasticity and network structure into an epidemic model. Journal of the Royal Society Interface, 6 (38), 761–774.CrossRefGoogle ScholarPubMed
Dietz, K., & Hadeler, K. P. (1988). Epidemiological models for sexually transmitted diseases. Journal of Mathematical Biology, 26 (1), 1–25.Google Scholar
Eames, K. T. D., & Keeling, M. J. (2002). Modeling dynamic and network heterogeneities in the spread of sexually transmitted diseases. Proceedings of the National Academy of Sciences, 99 (20), 13330–13335.Google Scholar
Eaton, J. W., & Hallett, T. B. (2014). Why the proportion of transmission during early-stage HIV infection does not predict the long-term impact of treatment on HIV incidence. Proceedings of the National Academy of Sciences, 111 (45), 16202–16207.CrossRefGoogle Scholar
Eaton, J. W., Hallett, T. B., & Garnett, G. P. (2011). Concurrent sexual partnerships and primary HIV infection: A critical interaction. AIDS and Behavior, 15 (4), 687–692.Google Scholar
Ferguson, N. M., & Garnett, G. P. (2000). More realistic models of sexually transmitted disease transmission dynamics: Sexual partnership networks, pair models, and moment closure. Sexually Transmitted Diseases, 27 (10), 600–609.CrossRefGoogle ScholarPubMed
Goodreau, S. M., Cassels, S., Kasprzyk, D., Montaño, D. E., Greek, A., & Morris, M. (2012). Concurrent partnerships, acute infection and HIV epidemic dynamics among young adults in Zimbabwe. AIDS and Behavior, 16 (2), 312–322.Google Scholar
Hallett, T. B., Singh, K., Smith, J. A., White, R. G., Abu-Raddad, L. J., & Garnett, G. P. (2008). Understanding the impact of male circumcision interventions on the spread of HIV in southern Africa. PLoS One, 3 (5), e2212.Google Scholar
Hamilton, D. T., Handcock, M. S., & Morris, M. (2008). Degree distributions in sexual networks: A framework for evaluating evidence. Sexually Transmitted Diseases, 35 (1), 30.Google Scholar
Hamilton, D. T., & Morris, M. (2010). Consistency of self-reported sexual behavior in surveys. Archives of Sexual Behavior, 39 (4), 842–860.Google Scholar
Holme, P., & Saramäki, J. (2012). Temporal networks. Physics Reports, 519 (3), 97–125.CrossRefGoogle Scholar
Karlin, S., & Taylor, H. E. (2012). A first course in stochastic processes (2nd ed.). New York: Academic press.Google Scholar
Kretzschmar, M., & Dietz, K. (1998). The effect of pair formation and variable infectivity on the spread of an infection without recovery. Mathematical Biosciences, 148 (1), 83–113.CrossRefGoogle ScholarPubMed
Leung, K. Y., & Kretzschmar, M. (2015). Concurrency can drive an HIV epidemic by moving R0 across the epidemic threshold. AIDS, 29 (9), 1097–1103.Google Scholar
Leung, K. Y., Kretzschmar, M. E. E., & Diekmann, O. (2012). Dynamic concurrent partnership networks incorporating demography. Theoretical Population Biology, 82 (3), 229–239.Google Scholar
Leung, K. Y., Kretzschmar, M., & Diekmann, O. (2014). SI infection on a dynamic partnership network: Characterization of R0. Journal of Mathematical Biology, 71 (1), 1–56.Google Scholar
Miller, J. C., Slim, A. C., & Volz, E. M. (2012). Edge-based compartmental modelling for infectious disease spread. Journal of the Royal Society Interface, 9 (70), 890–906.Google Scholar
Moody, J. (2002). The importance of relationship timing for diffusion. Social Forces, 81 (1), 25–56.Google Scholar
Morris, M. (1993). Telling tails explain the discrepancy in sexual partner reports. Nature, 365, 437–440.Google Scholar
Morris, M., Epstein, H., & Wawer, M. (2010). Timing is everything: International variations in historical sexual partnership concurrency and HIV prevalence. PLoS One, 5 (11), e14092.Google Scholar
Morris, M., & Kretzschmar, M. (1995). Concurrent partnerships and transmission dynamics in networks. Social Networks, 17, 299–318.Google Scholar
Morris, M., & Kretzschmar, M. (1997). Concurrent partnerships and the spread of HIV. AIDS, 11 (5), 641–648.Google Scholar
Morris, M., & Kretzschmar, M. (2000). A microsimulation study of the effect of concurrent partnerships on the spread of HIV in Uganda. Mathematical Population Studies, 8 (2), 109–133.Google Scholar
Morris, M., Kurth, A. E., Hamilton, D. T., Moody, J., & Wakefield, S. (2009). Concurrent partnerships and HIV prevalence disparities by race: Linking science and public health practice. American Journal of Public Health, 99 (6), 1023–1031.Google Scholar
Newman, M. E. J. (2007). Component sizes in networks with arbitrary degree distributions. Physical Review E, 76 (4), 045101.Google Scholar
Nicosia, V., Tang, J., Musolesi, M., Russo, G., Mascolo, C., & Latora, V. (2012). Components in time-varying graphs. Chaos: An Interdisciplinary Journal of Nonlinear Science, 22 (2), 023101.Google Scholar
Watts, C. H., & May, R. M. (1992). The influence of concurrent partnerships on the dynamics of HIV/AIDS. Mathematical Biosciences, 108 (1), 89–104.Google Scholar