Matthew Macauley
Postdoctoral Associate, NDSSL, VBI.Professional Preparation
- University of California, Santa Barbara. Ph.D., Mathematics, 2008.
- University of California, Santa Barbara. M.A., Mathematics, 2005.
- Los Alamos National Laboratory. Graduate Research Assistant, 2003-2004.
- Harvey Mudd College. B.S., Mathematics, 2003.
Research Interests
Discrete, finite dynamical systems, in particular Sequential Dynamical Systems (SDS). Coxeter groups. Geometric combinatorics. Mathematical modeling of disease transmission. Epidemiology. Structure of complex networks. Mechanism design over networks.Selected Publications
- J. Chen, M. Macauley,& A. Marathe. Network Topology and Locational Market Power Computational Economics, Forthcoming 2009.
- M. Macauley and H.S. Mortveit. On enumeration of conjugacy classes of Coxeter elements. Proceedings of the American Mathematical Society. In press.
- M. Macauley, J. McCammond, and H.S. Mortveit. Order independence in asynchronous cellular automata. Journal of Cellular Automata. 3(1), 2008:37-56
- K. Atkins, J. Chen, A. Kumar, M. Macauley and A. Marathe. Locational market power in power markets. Journal of Economic Behavior and Organization. To appear.
- M. Macauley and H.S. Mortveit. Cycle equivalence of graph dynamical systems. Submitted to Nonlinearity.
- M. Macauley and H.S. Mortveit. Equivalences on acyclic orientations. Submitted to Discrete Mathematics.
- J. Chen, M. Macauley and A. Marathe. Role of Network and Production Capacity in Allocating Market Power. Proceedings of Trans-Atlantic INFRADAY Conference on Applied Infrastructure Modeling and Policy Analysis. College Park, MD, November 2007.
- M. Macauley, J. McCammond, and H.S. Mortveit. Dynamics groups of asynchronous cellular automata. Submitted to Foundations of Computational Mathematics.
- M. Macauley, B. Rabern, and L. Rabern. A novel proof of the Heine-Borel theorem. Submitted to Mathematics Magazine.
- A. Kumar, M. Macauley and H.S. Mortveit. Update order instability in graph dynamical systems. In preparation.
Current research projects
Graph dynamical systemsGraph dynamical systems are a type of discrete dynamical system that arise in modeling of computer simulations, epidemiology, and biological networks. They are interesting mathematical objects in their own right, and have some surprising connections to diverse topics such as Coxeter groups, combinatorics, graph theory, hyperplane arrangements, and matroids. The pure mathematical results obtained from studying them can additionally provide useful insight when working with larger models and more applied problems, such the structure of complex systems in the setting of epidemiology. There are also many questions about equivalence of dynamical systems, and several different ways to define this, each one capturing certain key properties of the dynamics. This leads to questions about dynamical stability with respect to changes in the update order and/or dependency graph, as well as questions about morphisms between dynamical systems over different graphs. This is joint work with J. McCammond (UCSB), H.S. Mortveit, and A. Vullikanti.
Stochastic sequential dynamical systems
In most settings that are modeled with discrete dynamical systems, there is some amount of stochasticity. A key component of a stochastic graph dynamical systems is its phase space, which can be represented by a Markov chain. In this project, we study how changes in the update order and in the function are reflected through changes in the global dynamics by studying certain properties of the Markov chains. Of particular interest is to understand how robust the system is with respect to equivalent update orders, using one of the notions of equivalence that we have developed and studied in the last few years. We hope to exploit the strong connection between these equivalence classes, certain combinatorial properties of the underlying graphs and functions, and the dynamical properties of the corresponding systems. This is joint work with E. Dimitrova, A. Jarrah, R. Laubenbacher, H.S. Mortveit, and A. Vullikanti.
Subgraph mining for epidemiology
One way to describe an epidemiological outbreak is to construct a directed acyclic graph that encodes transmission (infection) of the disease between individuals. If more information is known, then one can add vertex labels to denote certain characteristics (adult, child, senior, etc), and edge labels can be added to denote the time of infection. This project consists of running simulations to create large amounts of outbreak data and then analyzing it. One central question is which small (vertex-labeled) subgraphs appear frequently in these outbreaks, which will help us better understand the most common ways the disease spreads, and in turn help us determine the best way to prevent it. Naturally, this will depend on parameters such as transmissibility in the SIR model. We are also studying the basic reproductive number between and within different different age-groups and seeing how this correlates to the different types of outbreaks, as measured using principal component analysis (PCA) techniques. Another question is to quantify how similar or different two outbreaks are from each other, as measured by these large labeled directed graphs. These questions are analyzed mathematically, as well as aided by software of customized graph libraries written using Boost, to be used for implementing data mining algorithms. This is joint work with R. Beckman, M. Khan, M. Marathe, E. Nsoesie, and A. Vullikanti.
Role of transmissibility and network topology in discrete epidemiological models
The focus of this project is on studying how the transmissibility of a disease determines the distribution of the size of the outbreak, and what this distribution looks like over different types of complex networks. Through large simulations, we see that this distribution consists of two sharp narrow peaks, one corresponding to outbreaks that never took off, and another corresponding to outbreaks that infected some fraction of the population. Two key characteristics of such a distribution is (i) the average size of an outbreak that took off (mean of the 2nd peak), and (ii) the percentage of outbreaks that took off. Both of these depend on the transmissibility, and so we can describe this relationship by a curve in the plane. The shape of this curve is a property of the underlying social network, and we would like to understand how sensitive it is to different network topologies. To do this, we are running these disease simulations over different networks, including the New River Valley social network, Erdős-Rényi random graphs, Watts-Strogatz small-world networks, and scale-free networks. This is joint work with A. Apolloni, R. Beckman, J. Chen, S. Eubank, and B. Lewis.
Mechanism design over networks
Consider a market consisting of buyers and sellers situated across a network, where the good to be sold must be delivered subject to capacity and flow constraints. There are many classical mechanisms and algorithms that no longer work under these conditions. We are interested in understanding how to modify these mechanisms, design new mechanisms, analyze the complexity of the algorithms, and how all of this is affected by the the topology of the network. One way to understand this better is to define the market power function, which measures the decrease in maximum flow of a particular subset of sellers. We have studied this function, how it behaves under collusion, and its shape with respect to changes in supply and demand. It is also closely related to the celebrated VCG mechanism. Using data of the Portland electricity grid from FERC, we have run large simulations that have computed this function, which has given us a better understanding of what it looks like in a real-world market. This is joint work with J. Chen, A. Marathe, and A. Vullikanti.