FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 | 4 | 5 |   ...   | 7 |


-- [ Page 1 ] --




A Thesis

Presented to

The Academic Faculty


Rick Quax

In Partial Fulfillment

of the Requirements for the Degree

Master of Science in

Computer Science

College of Computing

Georgia Institute of Technology

August 1, 2008




Approved by:

David Bader, Ph.D., Committee Chair Computational Science and Engineering Georgia Institute of Technology Peter Sloot, Ph.D., Advisor Section of Computational Science University of Amsterdam Richard Vuduc, Ph.D.

Computational Science and Engineering Georgia Institute of Technology Date Approved: July 7, 2008


I would like to thank my thesis advisors, who have guided me in the presentation of my thesis, and Shan Mei, with whom I have had many insightful discussions.

iii Contents ACKNOWLEDGEMENTS............................ iii LIST OF TABLES................................. vii LIST OF FIGURES................................ viii SUMMARY..................................... ix I INTRODUCTION.............................. 1

1.1 The thesis................................ 1

1.2 Problem statement........................... 1

1.3 Using complex networks........................ 2 1.3.1 Overview............................ 2 1.3.2 The SEECN framework.................... 2

1.4 Applicability to other domains.................... 3

1.5 Our contribution............................ 4 II PREVIOUS WORK............................. 5

2.1 Graph properties............................ 5

2.2 Kronecker and RMAT......................... 6

2.3 Simulating ep

–  –  –


–  –  –

For explanation and prediction of the evolution of infectious diseases in populations, researchers often use simplified mathematical models for simulation. We believe that the results from these models are often questionable when the epidemic dynamics becomes more complex, and that developing more realistic models is intractable.

In this dissertation we propose to simulate infectious disease propagation using dynamic and complex networks. We present the Simulator of Epidemic Evolution using Complex Networks (SEECN), an expressive and high-performance framework that combines algorithms for graph generation and various operators for modeling temporal dynamics. For graph generation we use the Kronecker algorithm, derive its underlying statistical structure and exploit it for a variety of purposes. Then the epidemic is evolved over the network by simulating the dynamics of the population and the epidemic simultaneously, where each type of dynamics is performed by a separate operator. All dynamics operators can be fully and independently parameterized, facilitating incremental model development and enabling different influences to be toggled for differential analysis.

As a prototype, we simulate two relatively complex models for the HIV epidemic and find a remarkable fit to reported data for AIDS incidence and prevalence. Our most important conclusion is that the mere dynamics of the HIV epidemic is sufcient to produce rather complex trends in the incidence and prevalence statistics, e.g. without the introduction of particularly effective treatments at specific times.

We show that this invalidates assumptions and conclusions made previously in the literature, and argue that simulations used for explanation and prediction of trends

–  –  –

than is currently done. In addition, we substantiate a previously predicted paradox that the availability of Highly Active Anti-Retroviral Treatment likely causes an increased HIV incidence.

–  –  –

1.1 The thesis Our thesis is that realistic simulations of epidemics over population networks are more easily and more adequately performed using annotated complex networks and independent dynamics operators. Traditional mathematical models are sufficient for relatively simple simulations but quickly become intractable as more influences and interactions are added. In contrast, using an explicit representation of a population network annotated with variables, where an epidemic is evolved through the application of separate operators, models can easily be extended in an incremental way, be specified in arbitrary detail and different effects can be toggled for differential analysis. We also claim that this method can be practical in terms of running time.

1.2 Problem statement Understanding patterns of prevalence and incidence of infectious diseases is a major challenge for various reasons. Static population networks consist of heterogeneous agents in multiple respects, and are characterized by distinctive global properties such as power-law degree distribution, community-structure and small diameter. In addition, sociological processes change the network over time but depend on the epidemic status, and conversely the propagation of an epidemic depends on both the static and dynamic properties of the population network.

At present, most simulations of epidemics are performed using mathematical models of complex real-world dynamics with only a handful of parameters. Popular methods are coupled differential equations and discrete Markov models. However, such approaches have significant drawbacks: the model complexity quickly becomes intractable for more realistic simulations, incrementally extending existing models is non-trivial and simplifying assumptions may have unexpected but dramatic effects on the simulation results. We argue that these models are adequate in limited cases, but that different methods should be used for more detailed and realistic knowledge discovery.

1.3 Using complex networks 1.3.1 Overview We propose to explicitly simulate the dynamics of virus propagation using annotated complex networks. Firstly, a graph representative of the target population is generated where the nodes represent agents and the edges represent possible infection pathways in a time step. A number of operators is then applied to the graph to model temporal epidemiological and sociological dynamics of the population. Nodes and edges are annotated with static and dynamic variables, and operators are parameterized independent of each other. This enables the incremental development of models of an epidemic, toggling of different influences for differential analysis and allows for models of arbitrary complexity. For instance, an agent’s infection stage and gender could influence its social behavior, infectivity, connectivity and life expectancy; at the same time, an agent’s behavior and connectivity could influence the probability of becoming infected and infecting someone else.

1.3.2 The SEECN framework We present SEECN1, a simulation framework that is designed to be expressive, modular and high-performance. The temporal operators support addition and deletion of nodes and edges, propagation of a disease over edges and its local progression within

nodes. They can be fully parameterized by the variables of the involved entities:

SEECN is available at www.science.uva.nl/∼rquax and easily pronounced as “season”.

nodes have a static ‘type’ and a dynamic ‘status’, and edges have a static ‘type’ and store the node variables at both sides. Time is discretized in time steps and all model parameters can be changed in each time step, for instance to reflect the introduction of a new treatment.

SEECN is comprehensively engineered for performance. It is written in C++ and parallelized with OpenMP, and both the graph generation and temporal dynamics algorithms are optimized for NUMA and cache efficiency using novel theory of Kronecker graphs. Even though the algorithms are bounded by memory-bandwidth and have inherently unpredictable access patterns, we were able to achieve a speed-up of one order of magnitude in single-processor performance and almost perfect scalability in the number of threads.

1.4 Applicability to other domains SEECN was developed for simulating infectious diseases, but we expect that it can be used for many other applications as well. The paradigm of studying the spread of some ‘virus’ over a domain of nodes and edges is a general one, although we currently only generate social interaction networks which are characterized by distinctive properties such as power-law degree distribution, small diameter and community structure. Such

properties and dynamics are found in e.g.:

• Information dissemination in blog communities;

• Interaction between proteins;

• Connectivity simulations of file-sharing networks;

• Robustness of autonomous system networks against failures.

1.5 Our contribution The contribution of this dissertation is twofold. In chapter 3 we choose Kronecker graphs for modeling social networks, derive novel and complete statistical properties of the total edge count, degrees of individual nodes and edge configuration, and exploit these in a variety of applications that were impossible or impractical before. RMAT is an algorithm that has been proposed to generate Kronecker graphs efficiently, and is described in chapter 2. In particular, we show how the results enable load-balancing and cache efficiency of the RMAT algorithm; combined with a refactored graph data structure and the use of the same techniques in the dynamics operators, we expect that SEECN is practical. We also suggest how the posterior probability of a graph can be computed efficiently and how a simple mathematical model can incorporate the statistical structure of a Kronecker graph.

Combining the graph generator with modules for network dynamics, infection propagation and local virus progression, we present and validate our framework in chapter 4. In chapter 5 we then showcase its expressiveness by performing a nontrivial simulation of the HIV epidemic. Firstly, we find a surprising phenomenon that could have caused the observed drop in AIDS annual incidence that invalidates earlier assumptions and conclusions, namely that the HIV epidemic itself is sufficient to produce such complex trends in reported data, and demonstrate that the use of simplistic mathematical models is insufficient as basis for complex predictions.

As a corollary we also add further evidence to support a much-debated paradoxical prediction that the introduction of treatment could be counter effective and find indeed that it likely results in higher stabilized HIV incidence.

–  –  –

Here we introduce some terminology, review important graph properties and summarize previous work on graph generation and modeling and simulation of epidemics.

2.1 Graph properties In this dissertation we define a graph (or ‘network’) G as a set of nodes and edges V, E, and we define |V | = N = 2n where n is an integer. All our graphs are undirected, i.e. ∀x,y∈V (x, y) ∈ E ⇒ (y, x) ∈ E; if this does not hold the graph is said to be directed. A graph has a power-law distribution when the number of nodes that has a particular degree k decreases monomially as k increases, i.e. pk ∝ k −γ where γ is the power-law exponent and typically 1 γ 3. For increasing N, a graph follows the densification law if |E| ∝ N α, α 1 where typically 1 α 2. In other words, the average degree increases as the graph size increases. This was recently observed to be true for various ubiquitous graphs such as social networks and the World Wide Web [16] and appears to coincide with a shrinking diameter (while it was long debated whether these networks have e.g. O(log N ) or O(log log N ) diameter growth). The diameter of a graph is typically defined as the maximum path length of all possible shortest paths, although in practical situations effective diameter is often used; this states a diameter such that some considerable fraction of shortest paths is shorter than this, where the fraction is typically ≥ 90%. This accommodates isolated nodes and excessively rare long paths.

Figure 1: An illustration of a step in the Kronecker algorithm. The scalar entries of matrix Gi are multiplied with the matrix itself and replaced with the result, to yield Gi+1.

2.2 Kronecker and RMAT Leskovec et al. [17], proposes to adopt the Kronecker matrix multiplication to generate realistic and mathematically tractable graphs. A large body of mathematical theory has already been developed for this operator, which they intended to exploit.

Conceptually, the Kronecker multiplication of a q ×q matrix with itself yields a q 2 ×q 2 matrix where each original (scalar) entry is multiplied by the entire original matrix, and replaced with the result. When a small matrix G1 is repeatedly Kroneckermultiplied with itself, the result can be interpreted as an adjacency matrix; with the right choice of parameters, properties such as a power-law distribution and hierarchical community-structure can be obtained. See figure 1 for an illustration.

In the stochastic case, a small initiator matrix contains edge probabilities 0 ≤ Θi,j ≤ 1. The result P = Θt after t Kronecker time steps is a probabilistic adjacency

–  –  –

the probability of edge (x, y) being present [15].1 This initiator matrix is typically very small and often of size 2 × 2, so that the bit-representations of two unique ids i, j ∈ [0, N ) of two particular nodes uniquely identify such a permutation with n factors.

Pages:   || 2 | 3 | 4 | 5 |   ...   | 7 |

Similar works:

«Reconsidering Scientific Threats to Free Will Manuel Vargas University of San Francisco In “Free Will and Substance Dualism: The Real Scientific Threat to Free Will?” Al Mele extends his groundbreaking work on scientific arguments against free will.1 He replies to charges that he has missed the real threat to free will posed by experimental work, and he focuses on two issues: (1) the claim that the “real” threat of scientific work is bound up with substance dualism and (2) recent...»

«Originalveroffentlichung in: B. Le Guen (ed.), De la scene aux gradins. Theatre et representations dramatiques apres Alexandre le Grand dans les cites hellenistiques. Actes du Colloque, Toulouse 1997 (Pallas, 41), Toulouse 1997, 219-259. De la scene aux gradins (ed. B. Le Guen), PALLAS, 47, 1997, pp. 219-259. Theatricality Beyond the Theater. Staging Public Life in the Hellenistic World* Angelos C H A N I O T I S (New York University) ecopaiccbs TrdvTa TO: EKET TrpdyuaTct T p a y c p S l a v...»

«Oceanside Community Plan CHAPTER II “Oceanside’s ideal is to safeguard our natural resources and preserve those elements of our community that enrich the spirit and quality of life for those living and visiting here.” Table of Contents Executive Summary Plan Purpose and Process Introduction to Oceanside Description of Applicable Regulations Goal 1 CITIZEN INVOLVEMENT – Findings and Conclusions Goal 10 HOUSING – Findings and Conclusions Goal 11 PUBLIC FACILITIES – Findings and...»

«Legislación Forestal de la República de Panamá http://www.anam.gob.pa Autoridad Nacional del Ambiente Ley N° 1 Por La Cual Se Establece La Legislaci ón Forestal En La República D Panamá Y Se Dictan Otras Disposiciones D ECRETA: TITULO I De Los Objetivos Clasificaciones Y Definiciones Capitulo I Disposiciones Generales Art ículo 1. La presente Ley tiene como finalidad la protección conservaci ón, mejoramiento, acrecentamiento, educación, investigación, manejo y aprovechamiento...»

«Application Report SPRA872A – January 2003 How to Optimize Your Target Application for RTDX Throughput Dustin Allensworth and Jason Smathers Software Development Systems/RTDX Team ABSTRACT Real-Time Data Exchange (RTDX) is a technology developed by Texas Instruments that enables real-time bi-directional communication between a digital signal processor (DSP) or microcontroller and a host application. This document describes how to increase the target-to-host throughput of an RTDX target...»

«Foreword Kneller Gardens are a vitally important asset for local people and visitors to the borough. The London Borough of Richmond upon Thames will aspire to maintain and manage the Gardens to the highest standards. This management plan is based on the use of an audit of the Gardens following central government guidance known as PPG 17. This is explained within this document but the approach is based on common sense. We believe that it is important to get the simple things right. Is the green...»

«no. 08-34 september 2008 working paper Midnight Regulations and RegulatoRy Review By Jerry Brito and Veronique de Rugy The ideas presented in this research are the authors’ and do not represent official positions of the Mercatus Center at George Mason University. MIDNIGHT REGULATIONS & REGULATORY REVIEW Jerry Brito * & Veronique de Rugy ** INTRODUCTION The term “midnight regulations” describes the dramatic spike of new regulations promulgated at the end of presidential terms, especially...»

«Elementary surveying, by William Horace Rayner. Rayner, William Horace, b. 1884. New York, D. Van Nostrand company, inc., 1937. http://hdl.handle.net/2027/wu.89078559739 Generated for Cornelius, Ian (Yale University) on 2014-08-14 04:40 GMT / http://hdl.handle.net/2027/wu.89078559739 Public Domain, Google-digitized http://www.hathitrust.org/access_use#pd-google Public Domain, Google-digitized / http://www.hathitrust.org/access_use#pd-google This work is in the Public Domain, meaning that it is...»

«European Commission DG Environment Establishment of guidelines for the inspection of mining waste facilities, inventory and rehabilitation of abandoned facilities and review of the BREF document No. 070307/2010/576108/ETU/C2 Annex 2 Guidelines for the inspection of mining waste facilities April 2012 Prepared by DHI in cooperation with Cantab Consulting Ltd University of Tartu Mecsek-Öko Miskolc University and VTT Inspection Guidelines Contents TERMS AND DEFINITIONS ABBREVIATIONS AND ACRONYMS...»

«ELIAS 1 The Implications of Modernity for Language Retention and Related Identity Issues: Applying the Thought of Charles Taylor by Vivian Elias Copyright © 2008 Vivian Elias. Presented on August 23, 2008, at the 2008 International Congress on Arctic Social Sciences (ICASS VI), hosted by the International Arctic Social Sciences Association (IASSA), which took place in Nuuk, Greenland, August 22–26, 2008. ELIAS 1 Preamble I’d like to acknowledge the Kalaallit of Greenland, on whose...»

«1 Lot’s Wife Lot’s Wife: The Woman To Remember Luke 17:32 Remember Lot’s Wife!! A wretch thou art, wheresoever thou be and wheresoever thou turn thee, if thou turn thee not to God. Thomas a Kempis Her names She has been called by some the Mayor’s wife; the Frozen Face; by others Mrs. Lot or simply Lot’s wife; and by everyone a foolish woman. 2 Key Genesis 18:16-19:29, Luke 17:28-33, Scriptures Promises In Genesis 19:16, Deuteronomy 13:17, Psalm 25:6, Jeremiah 3:12 Scripture Her...»

«134 Int. J. Biometrics, Vol. 2, No. 2, 2010 Contextual affect analysis: a system for verification of emotion appropriateness supported with Contextual Valence Shifters Michal Ptaszynski*, Pawel Dybala, Wenhan Shi, Rafal Rzepka and Kenji Araki Graduate School of Information Science and Technology, Hokkaido University, Kita-ku, Kita 14 Nishi 9, Sapporo 060-0814, Japan Fax: +81-11-709-6277 E-mail: ptaszynski@media.eng.hokudai.ac.jp E-mail: paweldybala@media.eng.hokudai.ac.jp E-mail:...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.