Search

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Includes bibliographical references (p. 167-175)., Over the last ten years, the interest in network phenomena and the potential for a global pandemic have produced a tremendous volume of research exploring the consequences of human interaction patterns for disease propagation. The research often focuses on a single question: will an emerging infection become an epidemic? This thesis clarifies the relationships among different epidemic threshold criteria in deterministic disease models, and discusses the role and meaning of the basic reproductive ratio, R0. We quantify the incorporation of population structure into this general framework, and identify conditions under which interaction topology and infection characteristics can be decoupled in the computation of threshold functions, which generalizes many existing results in the literature. This decoupling allows us to focus on the impact of network topology via the spectral radius of the adjacency matrix of the network. It is rare, however, that one has complete information about every potential disease-transmitting interaction; this uncertainty in the network structure is often ignored in deterministic models. Neglecting this uncertainty can lead to an underestimate of R0, an unacceptable outcome for public health planning. Is it possible to make guarantees and approximations regarding disease spread when only partial information about the routes of transmission is known? We present methods for making predictions about disease spread over uncertain networks, including approximation techniques and bounding results obtained via spectral graph theory, and illustrate these results on several data sets. We also approach this problem by using simulation and analytical work to characterize the spectral radii that arise from members of the exponential random graph family, commonly used to model empirical networks in quantitative sociology. Finally, we explore several issues in the spatiotemporal patterns of epidemic propagation through a network, focusing on the behavior o, by Laura A. Zager., Ph.D.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005., Includes bibliographical references (p. 85-88)., Measures of graph similarity have a broad array of applications, including comparing chemical structures, navigating complex networks like the World Wide Web, and more recently, analyzing different kinds of biological data. This thesis surveys several different notions of similarity, then focuses on an interesting class of iterative algorithms that use the structural similarity of local neighborhoods to derive pairwise similarity scores between graph elements. We have developed a new similarity measure that uses a linear update to generate both node and edge similarity scores and has desirable convergence properties. This thesis also explores the application of our similarity measure to graph matching. We attempt to correctly position a subgraph GB within a graph GA using a maximum weight matching algorithm applied to the similarity scores between GA and GB. Significant performance improvements are observed when the topological information provided by the similarity measure is combined with additional information about the attributes of the graph elements and their local neighborhoods. Matching results are presented for subgraph matching within randomly-generated graphs; an appendix briefly discusses matching applications in the yeast interactome, a graph representing protein-protein interactions within yeast., by Laura Zager., S.M.