Abstracts:

Networks and the Population Dynamics of Disease Transmission

November 17-21, 2003

Photo Gallery       Material from Talks

Stephen P. Borgatti (Department of Organization Studies in the Carroll School of Management, Boston College)  borgatts@bc.edu

Issues in Identifying Structurally important Nodes in Networks
Slides:   pdf
Paper:   pdf

This paper considers the problem of identifying sets of structurally important nodes in a network. A number of related issues are considered. First, I outline the different reasons why we might want to identify key nodes, showing that different measures (known as centrality measures in the social network literature) are needed for each. Second, I show how structural importance is affected by the manner in which things flow through a network. A typology is constructed to classify types of flows in terms of the kinds of trajectories that are possible (e.g., paths, trails or walks) and whether transmission occurs via serial replication, parallel replication or transfer. The relative importance of nodes in a given graph changes depending on what kind of flow process is operating. Third, I consider the problem of measuring the importance of sets of nodes. Finally, the subtext of the paper is a commentary on the nature of centrality measures and what they are intended to measure.

Rodney J. Dyer (Department of Ecology, Evolution, and Organismal Biology, Iowa State University, Ames, Iowa 50011)  rodney@iastate.edu

A Graph-Theoretic Analysis of Global Human Genetic Structure (poster session)

The amount and geographic patterning of human genetic variation is an evolutionary consequence of several historical and contemporary processes including population expansion, demographic subdivision, and migration. Quantifying this variation, and in turn the extent to which these forces have acted in shaping human genetic structure is a key component to understanding the evolution of human populations. Here I present an analysis framework based upon graph-theory, which we call Population Graphs (PG). While the PG framework allows the extraction of traditional population genetic statistics such as differentiation (_ST) and isolation by distance , topological analysis of the connectedness among human populations provides heretofore-unattainable information on intra-population evolutionary history. I highlight the utility of the PG framework using data consisting of 1056 individuals assayed for 376 variable microsatellite loci sampled from 52 populations around the globe. An analysis of the topology of the human graphs reveals the following characteristics of human population genetic structure. First, groups of populations exhibit significant topological structuring consistent with geographically relevant population subdivisions. Second, the topological distances among populations are significantly correlated with geographic separation supporting the notion of isolation by distance and spatially proximate migration patterns. Finally, we show how the topology of the graph is used to identify specific populations whose patterns of connectivity prove to be critical to the movement of genetic information across the entire graph.

Ken Eames (Department of Zoology, University of Cambridge)  ktde2@hermes.cam.ac.uk

Contact Tracing and Disease Control (poster session)

Contact tracing, followed by treatment, is a key control measure in the battle against infectious diseases. It represents an extreme form of locally targetted control, a hyper-parasite acting on infection, and as such has the potential to be highly efficient, especially when dealing with low numbers of cases. Modelling contact tracing requires explicit information about the transmission pathways from each individual and hence the network of contacts. Using pair-wise approximations and full stochastic simulations to model network-based processes, the utility of contact tracing is investigated. A simple relationship between the efficiency of contact tracing necessary to eradicate infection and te basic reproductive ratio of the disease is shown to hold in a wide variety of scenarios. Only clustering within the transmission network is found to destroy this relationship, enhancing the effectiveness of contact tracing by providing alternative tracing pathways. Since the critical efficiency depends on the characteristics of individuals within the network, applying different tracing regimes within differing subpopulations can achieve the elimination of infection whilst lowering the burden on health care services.

Stephen Eubank (Computer and Computational Sciences Division, Los Alamos National Laboratory)  eubank@lanl.gov

Structural Aspects of Massive Social Networks
Slides:   html    pdf    ps    ppt

We describe the estimation of very large, realistic social contact networks and study their structural properties. As a specific example, we consider the social network for the city of Portland, Oregon, developed as a part of the TRANSIMS/EpiSims project at the Los Alamos National Laboratory. The most complete description of the network is a bipartite graph, with two types of nodes: people and locations; where edges represent people visiting locations on a typical day. We describe various computationally tractable projections and approximations of this network and compare their structural properties.

Simon D.W. Frost (Department of Pathology, University of California, San Diego, Antiviral Research Center)  sdfrost@ucsd.edu

Simulation of Epidemiological Models on Networks (poster session)

Joint work with Klaus G. Muller.

Individual- or agent-based simulations are useful tools for understanding how the spread of an infectious agent or computer virus is affected by the structure of the underlying contact network and by the natural history of infection at an individual level. Spurred by the lack of freely available software to simulate epidemic processes on networks, we are developing a package, Epydemic, based upon SimPy (http://simpy.sourceforge.net), an open-source discrete-event simulation library written in Python, that permits the rapid prototyping of epidemic models. Infections consisting of multiple stages are easily and concisely modeled using semi-coroutines. The software includes a graphical user interface for parameter entry, result visualization etc., and an interactive console that allows the user to directly analyze components of the simulation. The poor performance normally associated with the use of an interpreted language for simulation is compensated for; by the use of efficient algorithms for the contact process and for the scheduling of events; by run-time compilation; by the use of extension modules programmed in C; and by parallelization of model runs using the Message Passing Interface. We present an example of a standard SIR model spreading in a configuration graph.

Mark S. Handcock (Department of Statistics, University of Washington)  handcock@stat.washington.edu  http://www.stat.washington.edu/handcock

Social Networks Models: Inference and Degeneracy

We consider statistical and stochastic models for graphs that can be used to represent the structural characteristics of network. To date, the use of graph models for networks has been limited by three interrelated factors: the complexity of realistic models, paucity of empirically relevant simulation studies, and a poor understanding of the properties of inferential methods. In this talk we discuss solutions to these limitations. We emphasize the important of likelihood-based inferential procedures and role of Markov Chain Monte Carlo (MCMC) algorithms for simulation and inference. A primary ongoing issue is the identification of classes of realistic and parsimonious models. In this regard show the unsuitability of some commonly promoted Markov models classes because they can result in degenerate probability distributions. The ideas are motivated and illustrated by the study of sexual relations networks with the objective of understanding the social determinants of HIV spread.

Peter Hoff (Departments of Statistics and Biostatistics, University of Washington)  hoff@stat.washington.edu

Mixed Effects Models for Network Data
Slides:   pdf

One impediment to the statistical analysis of network data has been the difficulty in modeling the dependence among the observations. In the very simple case of binary (0-1) network data, some researchers have parameterized network dependence in terms of exponential family representations. Accurate parameter estimation for such models is difficult, and the most commonly used models often display a significant lack of fit. Additionally, such models are generally limited to binary data. In contrast, mixed effects models have been a widely successful tool in capturing statistical dependence for a variety of data types, and allow for prediction, imputation, and hypothesis testing within a general regression context. We propose novel random effects structures to capture network dependence, which can also provide graphical representations of network structure and variability.

David R. Hunter (Department of Statistics, Pennsylvania State University)  dhunter@stat.psu.edu

Fitting Exponential Random Graph Models via Maximum Likelihood
Slides:   pdf

There is increasing interest in modeling network data using exponential random graph models (ERGMs). Fitting these models using traditional methods such as maximum likelihood is difficult if not impossible due to the fact that evaluation of the likelihood function involves a summation with a very large number of terms. This talk discusses a method that uses stochastic approximation of the likelihood function based on a Markov chain Monte Carlo (MCMC) approach. An alternative approach known as maximum pseudolikelihood is also discussed.

Alden S. Klovdahl (Social Sciences, Australian National University)  alden.klovdahl@anu.edu.au

Big Worlds, Isolated Individuals: Some Characteristics of Social Networks of Ordinary People

Belief in the idea of a 'small world' as applied to human societies lacks empirical support. Even the data that originally gave rise to this idea (Milgram) does not support it. The purpose here is to consider some characteristics of social networks of randomly selected (Table of Random Numbers) ordinary urban residents as a first step away from speculations about networks in modern societies towards solid empirical evidence. Measures presented will include graph- theoretic mean and median distances, and eccentricities. At the core of this work is the presupposition that to more fully understand factors affecting the spread of many human pathogens it is necessary to be able to accurately characterize the underlying population networks through which they can be transmitted.

Denis Mollison (Heriot-Watt, Edinburgh) denis@ma.hw.ac.uk

Small Worlds and Giant Epidemics
Slides:   pdf

Key problems for models of disease spread relate to threshold, velocity of spread, final size and control. All of these depend crucially on the network structure of individual interactions.

Networks of interest range from the local extreme where interactions are only between nearest neighbours in some low dimensional space, and the infinite-dimensional 'mean-field' extreme where all interact equally with all. Intermediate cases of practical interest include 'small-world' and meta-population models.

I shall discuss the various structures of such models, their similarities and differences, and some approximations to them. The main aim is to identify what features of contact structure need to be captured when formulating a model for any specific problem of disease spread.

James Moody (Department of Sociology, Ohio State University)  Moody.77@sociology.osu.edu  http://www.soc.sbs.ohio-state.edu/jwm/

Epidemic Potential in Human Sexual Networks: Connectivity and The Development of STD Cores
Slides:   html    pdf    ps    ppt

Research on the spread of many sexually transmitted diseases suggests that infection results from a heterogeneous distribution of infected actors. While infection rates are too low in the population at large to account for epidemic spread, within smaller groups infection rates are high enough to generate outbreaks. This paper shows that network node connectivity provides a natural measure for such STD cores. After describing STD cores and node connectivity, I demonstrate the plausibility of the model with data from prior epidemic outbreaks, discuss the std-core implications of popular large-scale network models, and show how STD cores can develop with small changes in local behavior.

Martina Morris (Department of Sociology, University of Washington)  morrism@u.washington.edu  http://faculty.washington.edu/morrism/

The Influence of Concurrent Partnerships on Network Structure and Transmission Dynamics

Concurrent partnerships are defined as partnerships that overlap in time, rather than obeying the norm of sequential monogamy. Concurrency changes the structure of a sexual partnership network, creating larger components and providing an ecology that favors the rapid spread of infectious pathogens. Simulation studies have demonstrated that concurrent partnerships can increase the speed and pervasiveness of spread in a population, even when the number of partnerships is held constant. Empirical studies have shown that concurrency is associated with higher levels of transmission. Thus, there is growing evidence that concurrency may play an important role in explaining the differentials in prevalence across population subgroups. This study uses three nationally representative data sets to identify the levels and variation of concurrency in the US, Thai, and Ugandan populations. Both the levels and the patterns of concurrent partnerships are very different in these populations. Simulation based on these patterns show transmission dynamics that replicate the observed variation in prevalence.

Mark E.J. Newman (Center for the Study of Complex Systems, University of Michigan)  mejn@umich.edu

How the Structure of Contact Networks Affects Disease Propagation
Papers:
http://arxiv.org/abs/cond-mat/0205009/
http://arxiv.org/abs/cond-mat/0205405/
http://arxiv.org/abs/cond-mat/0209450/
http://arxiv.org/abs/cond-mat/0303183/

I will discuss observational results on the statistical properties of contact networks, including degree distributions, correlation properties, transitivity, and assortativity. I will also discuss models of disease propagation on networks that have these properties and describe how the properties in question affect the spread of the disease. Some results are already well known, such as the fact that highly degree-assortative networks support epidemics at lower density, but others are not, such as the fact that high levels of transitivity cause diseases to saturate populations in regimes only slightly above the epidemic threshold.

Phillipa Pattison (Department of Psychology, University of Melbourne)  p.pattison@psych.unimelb.edu.au

Neighbourhood-based Models for Social Networks: Model Specification Issues
Slides:   html    pdf    ps    ppt

Pattison and Robins (2002) argued that social networks can be modelled as the outcome of processes that occur in overlapping local regions of the network, termed local social neighbourhoods. Within this framework, each neighbourhood is conceived as a possible site of interaction and is associated with a subset of possible network ties. Global network structure is then hypothesised to arise as the outcome of processes occurring within these overlapping local neighbourhoods. In this paper, we review theoretical arguments for various hypotheses about the forms of these local neighbourhoods. We consider Markovian neighbourhoods as well as generalized realisation-dependent neighbourhoods that are generated, in part, by interactive network processes themselves. We introduce some promising new neighbourhood forms including what we term k-triangles, multiple triadic structures sharing a common dyadic base. We also introduce hypothesized relationships between parameters representing related neighbourhood structures, such as k-stars or k-triangles, and thereby obtain simplified model specifications. Illustrative empirical analyses based on these various model specifications are presented.

Reference: Pattison, P., & Robins, G. L. (2002). Neighbourhood-based models for social networks. Sociological Methodology, 32, 301-337.

Garry Robins (Department of Psychology, School of Behavioural Science, The University of Melbourne, Australia)  http://www.psych.unimelb.edu.au/staff/robins.html

Exponential Random Graph (p*) Models for Social Networks: The Global Outcomes of Local Model Specifications

Exponential random graph models, when derived from a dependence graph using the Hammersley-Clifford theorem, are specified in terms of local network structures. But as these localized patterns agglomerate, the global outcomes are often not apparent. We review our recent work on simulating distributions of Markov random graphs, examining the resulting global structures by comparison with appropriate Bernoulli distributions of graphs. We provide examples of various stochastic global "worlds" that may result, including small worlds, long path worlds and dense non-clustered worlds with many four-cycles. Degeneracy in these models relates to the movement from structure to randomness, when parameter scaling results in a phase transition occurring at a certain "temperature". Degenerate or "frozen" deterministic structures may be merely empty or full graphs, but also include more interesting highly clustered "caveman" graphs, bipartite structures, and global cyclic structures involving structurally equivalent groups.

But Markov random graphs are only one possible way to specify exponential random graphs. We present recent results from simulations for two other new model specifications. The first specification includes binary attribute measures on the nodes, with network ties and actor attributes mutually contingent, resulting in joint social influence/social selection models. The second specification includes aggregations of triangle and star counts, permitting an explicit model form for the degree distribution and a new transitivity concept, k-triangles, reflecting the distribution of triangles across the graph.

Richard Rothenberg, MD (Department of Family and Preventive Medicine, Emory University School of Medicine)  rrothen@emory.edu

Large Network Concepts and Small Network Characteristics
Slides:   html    pdf    ps    ppt

The characteristics of large networks—degree distribution, small world phenomena, community structure, assortatitivity, clustering, vulnerability to attack, etc.—may not be fully recognizable in the smaller (by 5-7 orders of magnitude) networks within which disease transmission takes place. The smoothing afforded by size may not protect small network from unpredictable manifestations that result from underlying heterogeneity and attendant sampling variability. To explore the characteristics of small networks, we have assembled 15 data sets from completed network studies that focused on the transmission of STDs and HIV. These studies reveal underlying heterogeneity in their demographic characteristics, risk behaviors, and disease prevalence, but some similarities with regard to degree distribution, clustering and, depending on the predominant risks, assortatitivity. For example, the aggregated degree distribution (a composite totaling >14,000 dyads) is scale-free (that is, the Cumulative Probability Distribution is linear in the log-log scale, thus fitting a power law curve with an coefficient of ~2.0), as are most of the degree distribution for individual studies (albeit with considerably more “noise”). Clustering greater than that predicted for random graphs is present in all the network studies that permitted examination of components. Short mean path lengths between persons within components, a manifestation of the small world effect, are universally present. Such observations provide substantiation that small networks may behave similarly to large ones, despite greater variability and sampling uncertainties and provide some empirical validation of the theoretical basis for an apparent lack of epidemic threshhold and continued low level endemic disease transmission of some STDs and HIV in these microsettings.

Matthew Salganik (Department of Sociology, Columbia University)  mjs2105@columbia.edu http://www.columbia.edu/~mjs2105

Sampling and Estimation in Hidden Populations Using Respondent-Driven Sampling (poster session)

The task of slowing the spread of HIV is complicated by our difficulties in collecting accurate information about certain key subpopulations, such as injection drug users and commercial sex workers. Using a new sampling and estimation method called respondent-driven sampling, researchers are now able to collect information about some of these key subpopulations more quickly, cheaply, and accurately than before.

A respondent-driven sample is selected with a snowball-type design (sample members recruit their friends). Despite the numerous biases inherent in this sample selection process, an estimation procedure is developed which, under specified (and quite general) conditions, can be used to make unbiased estimates about the proportion of the population with a specific trait -- for example the percentage of injection drug users in a city with HIV. The estimation procedure uses the sample to make inference about the social network connecting the subpopulation. This network information is then used to make inference about the characteristics of the subpopulation. It is also the case that these estimates are asymptotically unbiased no matter how the seeds (initial members of the sample) are selected.

Anne Schneeberger (Department for Infectious Disease Epidemiology, Imperial College, London)  a.schneeberger@imperial.ac.uk

Sacle-free Networks and Sexually Transmitted Diseases: A Description of Observed Patterns of Sexual Contacts in Britain and Zimbabwe (poster session)

Sexually transmitted infections spread through a network of contacts created by the formation of sexual partnerships. Methods developed in physics can characterise a wide range of networks through a description of the distribution of numbers of sex partnerships. It has been suggested that in the Swedish population this 'degree' distribution follows a power law and therefore indicates a 'scale-free' network. Our objectives were to test statistically whether distributions of numbers of sexual partners reported by different populations and over different time periods are well described by power laws and to estimate their exponent and its implications. Maximum likelihood estimates of the exponent of a scale free network fitted to reported distributions of numbers of partners are compared with the fit for an exponential null model. Data are taken from 4 population based surveys, three from Britain and one from rural Zimbabwe. We find that the networks can be described by a power law over a number of orders of magnitude. In addition, exponents differ significantly and meaningfully, with an 'accelerating network' formed between men who have sex with men (MSM). Networks with an exponent indicating the lack of a 'critical spread rate' are also found for the other populations except for women in Britain. Thus statistical analyses demonstrate that a scale-free network approach provides a reasonable description of distributions of reported numbers of sexual partners. Further, if these networks are formed over a short time only a very small transmission probability will be sufficient to lead to persistence of infection.

Markus Schwehm (Department of Medical Biometry, University of Tübingen, Germany)  schwehm@informatik.uni-tuebingen.de  http://www-ra.informatik.uni-tuebingen.de/mitarb/schwehm/

Stochastic Simulation of Epidemics on Large Contact Networks (poster session)

Joint work with Martin Eichner (Department of Medical Biometry, University of Tübingen, Germany).

We have implemented a fast stochastic individual-based simulator the analysis of disease transmission and containment interventions. The simulator consists of a discrete event simulator for the processing of event-based models and plug-ins for different contact network topologies.

The discrete event simulation distinguishes tree types of events. The first type implements the standard SEIRS infection dynamics with susceptible, exposed, infectious and recovered states as well as vaccination and a simple birth/death process. The second type models the visibility of the disease according to none, detectable or obvious symptoms. The third type allows to model intervention strategies (like contact tracing, quarantine and case isolation), which influence the contact structure of individuals. Events can trigger further events for the same individual and via the contact network for other individuals. All events are processed in a discrete event simulator which is optimized for large numbers of events using a priority queue (indirect heap algorithm) and can process about 50.000 events per second.

The inhabitants of the population are represented by their internal state (infection, symptom and contact status) and represent nodes in a contact network. The modular design allows to exchange the contact network independent of the chosen discrete event model. For each individual the contact network allows to identify a limited number of contacts for transmission of the infection or for implementing contact tracing interventions. Currently there exist parameterized network generators for local, global, random and scalefree contact networks. Moreover, the data struc-ture allows to maintain arbitrary networks consis-ting of several independent layers. We were able to simulate populations of two million individuals on a personal computer.

Tom A.B. Snijders (Department of Sociology / ICS, University of Groningen)  t.a.b.snijders@ppsw.rug.nl  http://stat.gamma.rug.nl/snijders/

Simulation-Based Statistical Inference for Evolution of Social Networks
Slides:   pdf

Social networks are structures of social ties between individuals (or other social actors, e.g., companies or countries). The most common representation of a social network is a directed graph, with individuals as nodes, in which the arcs indicate for each of the ordered pairs of individuals whether the tie in question (e.g., friendship) is present or not. In addition, there can be covariate data, referring to the individuals or the dyads (ordered or unordered pairs of nodes).

Social mechanisms can be brought to light much better using longitudinal observations on social networks, than by using single observations. The most common type of longitudinal observations are repeated measures, or panel data. Repeated measures on social networks represent a complicated data structure. Computer simulation offers fruitful possibilities here, because it greatly expands the scope of modeling beyond the models for which likelihood and other functions can be analytically calculated. Continuous-time models are more appropriate for modeling longitudinal social network data than discrete-time models because of the endogenous feedback processes involved in network evolution.

Probability models for the evolution of social networks are discussed which are based on the idea of actor-oriented modeling: the nodes in the network represent actors who change their relations in a process of optimizing their "objective function", plus a random component representing unexplained change. The resulting model constitutes a continuous-time Markov chain, and can be simulated in a straightforward manner. Similar models can be proposed which are tie- oriented, in which ties can change randomly as a result of optimizing an objective function. In all these models, the change in the network is modeled as the stochastic result of network effects (reciprocity, transitivity, etc.) and effects of covariates. The model specification is given by the rate function, defining the rate at which ties may change; the objective function, indicating the "preferred" state of the network; and the gratification function, representing change tendencies for which the drive for creation of a new tie is not the opposite of the drive for deletion of this tie when it exists. These three functions may depend on endogenous and/or exogenous actor and dyad characteristics.

The parameters of this model are weights in the rate, objective, and gratification functions, which may depend on network structure and on covariates. The parameters can be estimated using a stochastic version of the method of moments, implemented by a Robbins-Monro-type algorithm. An example is given of the evolution of the friendship network in a group of university freshmen students.

Elaborations which may be discussed include alternative model specifications and alternative estimation methods. Further information about this research is at http://stat.gamma.rug.nl/snijders/siena.html.

Duncan J. Watts (Department of Sociology, Columbia University)  djw24@columbia.edu

Universal Behavior in a Generalized Model of Contagion
Slides:   html    pdf    ps    ppt

Models of contagion arise broadly both in the biological and social sciences, with applications ranging from the transmission of infectious disease (1, 2) to the diffusion of innovations (3, 4) and the spread of cultural fads (5-7). We present a general model of contagion which, by explicitly incorporating memory of past exposures to, for example, an infectious agent, rumor, or new product, includes the main features of existing contagion models as special limiting cases, and interpolates between them. We study in detail a simple version of the model, finding that under general conditions only three classes of collective dynamics exist, two of which correspond to familiar epidemic threshold (8) and critical mass (9) dynamics, while the third is a distinct intermediate case. Furthermore, we find that for a given length of memory, the class into which a particular system falls is determined entirely by the values of two variables, each of which ought to be measurable empirically. Our model suggests novel measures for assessing the susceptibility of a population to large contagion events, and also a possible strategy for inhibiting or facilitating them.

Photo Gallery       Material from Talks

Networks and the Population Dynamics of Disease Transmission, November 17-21, 2003