David C. Bell (Affiliated Systems Corporation, Houston) firstname.lastname@example.org
Of critical importance in the transmission of HIV are "gatekeepers," the HIV-negative partners of persons who are HIV-infected. These are the persons at risk and they are the persons who can eventually spread the disease further. And since the highest infectivity comes in the first months after infection, usually before knowledge of infection, the behavior of these "gatekeepers" while they are HIV- is critical. In a sample of 267 persons from high drug use neighborhoods, we collected data on 3254 relationships involving 1271 other persons. We quantitatively describe the gradient of infection potential by which HIV can diffuse from the HIV+ population through "gatekeepers" to the rest of the population through both drug injection behaviors and sex behaviors.
Marie-Claude Boily (Department of Infectious Diseases Epidemiology, Imperial College, London) email@example.com
Empirical and theoretical studies have highlighted the importance of the local (egocentric) and the global (sociocentric) network structure on the individual risk of infection and the spread of diseases in populations. Transmission dynamics models of STI (sexually transmitted infection) and HIV/AIDS have been instrumental in highlighting the importance of quantifying sexual behaviour such as the average and variance in sexual activity, the mixing pattern, concurrency and others in order to understand epidemiological trends. Detailed individual based models of partnership formation and dissolution (micro-simulation or network models) are increasingly being used in order to capture the full complexity of sexual networks and "more realistically" simulate the course of STI and HIV/AIDS. However, at the moment, the complexity of models has outstripped the level of behavioural data currently available for most populations.
The objective of the talk is to review and discuss the limits of currently available sexual network data and the implication for mathematical modelling of STI. It will be shown how the limited network data available, compounded by our incomplete understanding of individual behaviour, has a number of consequences for the formulation and validation of network models, the interpretation of model results, and the formulation of research questions and data collection. In the case of a lethal disease, like HIV/AIDS, not only is it important to understand the impact of the network structure on the spread of disease, but is it also important to understand and assess the impact of the spread of disease on the network structure. It will be shown that this is particularly relevant to understand the different impacts of antiretroviral therapy or vaccination in heterogeneous populations largely afflicted by the epidemic.
Stephen P. Borgatti (Department of Organization Studies in the Carroll School of Management, Boston College) firstname.lastname@example.org
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) email@example.com
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) firstname.lastname@example.org
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) email@example.com
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) firstname.lastname@example.org
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.
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) email@example.com
Mixed Effects Models for Network Data
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) firstname.lastname@example.org
Exponential Random Graph Models via Maximum Likelihood
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) email@example.com
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) firstname.lastname@example.org
Small Worlds and Giant Epidemics
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.
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.
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.
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) email@example.com
the Structure of Contact Networks Affects Disease Propagation
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) firstname.lastname@example.org
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) email@example.com
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.
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) firstname.lastname@example.org
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) email@example.com 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.
Statistical Inference for Evolution of Social Networks
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) firstname.lastname@example.org
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.