Research Experiences for Undergraduates 2011-Project Presentations

Research Experiences for Undergraduates 2011 Home Logistics Participants Schedule Photos Project Presentations Final Papers

"Urban Scaling in the United Kingdom"

Kevin Carlson, Indiana University

Recently, many scaling laws have been reported to model relationships between American urban areas' population and a broad class of economic metrics. Such techniques improve on traditional per capital measures, which risk confounding the general nonlinear effects fundamental to the nature of dense human populations with deviations from these due to local influences. We intend to extend this work in an analysis of data regarding energy use and criminal activity collected in the United Kingdom. We will aggregate reports from Local Administrative Units to the city level, considering all 65 UK centers with population above ca. 100,000, and apply maximum likelihood estimation techniques to compare various distributions' explanatory power over the observed trends. If power-law scaling is found, we will have a broader domain of support for this theoretical explanation of urban phenomena and the impetus to further generalize understanding of this fundamental constraint on mass social phenomena. The complement to this work will be measuring cities' deviations from the theoretical predictions derived in this way, which information may find applicability to a range of further research in urban planning and public policy.

Mentors: Luis Bettencourt, Geoffrey West, Hyejin Youn and Scott Ortman.

"A Network Approach to Interbank Lending and Systemic Risk"

Thomas Catanach, University of Notre Dame

The recent global financial collapse has highlighted the need for a more complete understanding of systemic risk within financial markets, and particular attention has been devoted to the risk stemming from the interconnectedness of banks and other financial entities. We intend to study models of banks with linked balance sheets forming a weighted directional network where edges correspond to interbank assets and liabilities. The study of systemic risk in financial networks will first be addressed using traditional static methods of stress tests, in particular to characterize the emergence of cascading failures stemming from a single bank default. With this approach we will also study the effects of different network topologies on contagion, focusing in particular on the differences between homogeneous and heterogeneous degree distributions. After exploring the static model, we will begin to create a more realistic model in which consumer deposits, interbank loans, external assets, investments, prices, and interest rates are all dynamic and bank assets, liabilities, and investment opportunities are heterogeneous. This model will help us understand economic cycles in which bank assets grow through investment but then fluctuations in assets/liabilities produces a small number of bank defaults which cause a liquidity shortage and eventually propagate to systemic collapse. Through these analysis we hope to explain the robust yet fragile nature of the global financial system, and the fact that banks seeking to minimize their individual risk can inadvertently increase the risk of failures at the systemic level.

Mentor: Fabio Caccioli

"The Onset of Difficulty in A Variant of Graph Coloring and the Jamming Transition"

Ronnie Garduño, University of New Mexico

If we are working with random graphs, it has been shown that there is an edge density level at which the probability of there being a 3-coloring of the nodes of the graph becomes zero. [Stated another way, no 3-coloring can exist of any random graph once a certain fraction of the edges possible in the graph are present.] This phase transition marks the edge of solvability for this class of problem, but there remain questions about the relative difficulty of finding solutions. It seems probable that many problems in the solvable range will require a great deal of computation to solve. Another conjecture is that the difficulty of finding these solutions will scale with the density of the random graphs involved. In order to investigate these problems, we will perform computational experiments measuring the average number of changes that are needed to correct the coloring of random graphs of various sizes and densities. Rather than working with the original discrete formulation of the coloring problem, we will instead focus on the case in which each node is associated with a real number from 0 to 1, with the restriction that any two neighboring nodes must be at least 1/3 (modulo 1) away from each other. This change to the original problem allows us to focus on changes which only affect one neighbor at a time, as opposed to the discrete formulation, in which changing the color of one node can affect every one of its neighbors simultaneously. The problem of modeling the motion of hard spheres in close proximity to each other has many applications in physics. The idea is that there are some systems which we can profitably think of as being composed of inelastic homogeneous spheres, whose interacting motions are then simulated to study various features of the system in question. Many fundamental problems in statistical mechanics are studied using this simplified model, making the difficulty of computationally simulating these interactions a serious barrier to our further understanding. Our approach to graph coloring is intended to operate in the same fashion as the event-chain algorithm for performing such simulations, and our experiments should uncover results which are useful to the design and application of such algorithms.

Mentor: Cris Moore

Jay Garlapati, University of Chicago

Nash equilibria predict the strategies of rational agents playing a game a priori. We aim to study the development of game strategies through an evolutionary process. Professor Miller has proposed an evolutionary perspective where agents are modeled as a population of automata that compete against each other and evolve their strategies through iterations of a genetic algorithm. We will use this approach to study cooperation between agents and environmental effects in n-player games. Krohn and Rhodes noted the equivalence of automata and the algebraic objects, semigroups and used it to prove the Krohn-Rhodes Theorem, which allows us to decompose an automation into an equivalent hierarchical system of permutation and reset automata. We hope to use the Krohn-Rhodes Theorem to understand the effectiveness of the evolved agents in terms of their constituent parts as well as to study their level of complexity.

Mentors: Simon DeDeo and John Miller

"Applying the Akaike Information Criterion to Degree-Corrected Stochastic Block Models"

Jacob Jensen, Columbia University

The Akaike Information Criterion (AIC) is a powerful and highly principled method of model selection. When working with probabilistic models it is typical to fit them to the data by maximum likelihood, using Markov Chain Monte Carlo or Belief Propagation. The maximum likelihood value obtained in this way gives an indication of how good a fit the model is to the data. Unfortunately, models with more parameters tend to fit the data strictly better, simply because they have more degrees of freedom and not necessarily because they describe it better. The AIC counters this by taking the maximum likelihood value and adding a k = |θ|. The best model according to the AIC is then the one that minimizes . This simple penalty has a powerful justification, but makes certain assumptions that pose major problems to models used to infer networks. The first of these assumptions, that all parameters in θ are continuous, can be remedied by a monte carlo procedure that marginalizes over these variables. The second, which assumes narrow peak around in the model’s likelihood, is normally easy to deal with given enough data to accurately estimate parameters. In the case of the Degree-Corrected block model, which includes an independently parametrized poisson distribution for every, low-degree nodes violate this assumption. We hope to overcome this problem and find an extension of the AIC that can handle this case.

Mentors: Cris Moore and Cosma Shalizi

"The rules of conflict in an animal society"

Eddie Lee, Princeton University

This projects involves collaboration with Bryan Daniels, Jessica Flack and David Krakauer in conflict dynamics embedded in time series data, collected by JF on pigtailed macaques, a gregarious species of monkey. In a recent paper (“Inductive Game Theory and the Dynamics of Animal Conflict”), Simon DeDeo, JF and DK discussed possible interaction rule sets that could explain the rise of conflicts. They noticed, however, unexplained and significant time dependent fluctuations in their measured. Also, critics noted that their measure for time correlations may have precluded some other features of the data. The purpose of this project is to investigate alternative measures of dependence that address these concerns: (1) capture other features of the data set potentially neglected by the original measures and (2) resolve the time anomalous observations made with the original measure with the new measure. Since an established methodology for measuring the underlying dynamics of conflict does not exist, we must first establish useful metrics that reliably convey the dynamics. If we fail to resolve the second goal, we will attempt determine the origin (e.g. noise or changing strategies) of the shifts. Conflict dynamics are a fundamental part of complex systems. In abiotic systems, we can conceive of conflict occurring in boundaries straddling energy gradients such between tectonic plates. How stress has built up and how it is released is crucial in explaining the evolution of the landscape. Analogously, the creation and dissipation of conflict in social systems is fundamentally linked to the stability and evolution of the system. Conflict inherently destabilizes the configuration of the system, and it is of utmost interest to know what the causes of such instability are. To be able to figure out what rules macaques implement that result in the observed pattern will be a step to understanding the mechanics of conflict and the methods of investigating it.

Mentors: Bryan Daniels, Jessica Flack and David Krakauer

Emily Lichko, University of Michigan

The primary focus of my summer project is to combine agent-based modeling with phylogenetic methods to investigate how different modes of transmitting traits between individuals within populations affect the cultural history of the traits. Specifically, I want to investigate whether traits that individuals acquire vertically (i.e. from their parents), leave a stronger phylogenetic signal than traits that are acquired horizontally (i.e. from peers), or obliquely (i.e. from individuals in the parent generation who are not the biological parents). To this end, I will develop an agent-based simulation modeling the interactions between individuals and therefore the transmission of cultural traits via the different transmission modes; the simulation will be based on documented accounts of traits transmission between individuals within traditional, small-scale populations. Using size-dependent splitting events, the populations will separate and eventually form a phylogenetic tree. This will allow me to explore the effects of other factors, such as the influence of different migration rates, on the final trait distribution at the terminal branches of the phylogenetic tree. I will then apply standard methods of phylogenetic comparative analysis to assess the degree of phylogenetic signal in the different traits, using as input data the phylogenetic tree and the distribution of the traits at the tips of the tree produced by the agent-based simulation. The results of the phylgenetic comparative analyses will provide insights into the processes that shape the observed distribution of the traits, and this will likely have implications for our understanding of human cultural diversity.

Mentors: Laura Fortunato, Tanmoy Bhattacharya and Anne Kandler

Gregory Robinson, University of California at Davis

The chemistry of life, such as genetic and metabolism, relies on complicated networks of interacting chemical reactions. The networks are naturally modeled as hypergraphs, which generalize the notion of graph connectivity to include edges that join more than two nodes. This extension is helpful because manly interesting chemical reactions involve multiple reactants and products, and are often catalyzed. Getting a better grasp on the nature of these interactions could inform the study of how early life formed. To this end, we seek to apply non-equilibrium thermodynamics to chemical reaction networks. Recent work on large-deviations theory and its application to non-equilibrium statistics mechanics provides a framework by which to do so. Large deviations theory studies the behavior of "tail" events occurring in a stochastic process, such as rare transitions between equilibrium states. The specific questions to answer are numerous. For example, we wish to determine how the topology of a reaction network affects the number of equilibrium states possible on it. Other research questions are likely to arise, as this is not yet well-charted territory. later, this study of chemical reaction networks can perhaps be abstracted to include other kinds of species and reactions, such as ecological interactions between populations of organisms.

Mentor: Eric Smith

Tom Weinrich, Brown University

My project will address the thermodynamic properties of driven systems far from equilibrium through the application of large deviations principles. Eric has previously written about extensions of the methods from classical thermodynamics into the nonequilibrium domain; the idea now is to apply them to a system of interest. The choice of that system is not yet final, but the details are less important than the methods. For the sake of being concrete, I'll write here about one likely candidate. Chemical reaction networks, such as those observed in biology, continuously receive and dissipate energy from their environment, and as a result never reach equilibrium. Despite this, they are stable over the lifetime of a cell, usually many orders of magnitude longer than the time to complete a cycle. They also seem to be very finely tuned; the most extreme example of this is the metabolic network in cells, which evolution has not altered meaningfully in any organism for approximately 4 billion years. We hope that we will be able to explain this robustness by asking questions about the properties of stable configurations of the networks under typical driven conditions, and the types of large deviations results that can be derived from them.

Mentor: Eric Smith

Brecia Young, Harvard University

Consanguineous marriage is a marriage practice that has declined in many parts of the world due to associated taboos and genetic risks; however, in many regions of North Africa, the Near East, and Central Asia, consanguineous marriage and more specifically marriage between first cousins has persisted at significant levels. Anthropologists have observed various reasons for this marital preference including a more harmonious relationship with in laws and a more stable marriage, cultural norms obliging first cousins to marry, and desires to preserve property, power and prestige within a family. In addition, there may be an evolutionary advantage for a father who knows that his wife’s offspring will be related to him regardless of whether he is assured paternity or not. The decline of consanguineous marriage in some areas, especially North America and Europe, can be attributed to deleterious effects associated with the increase in homozygous pairs of recessive genes in the offspring of related mates (otherwise known as inbreeding depression). In spite of these harmful effects, cousin marriage persists in certain regions and it is unclear what factors drive this phenomenon. Inspired by the observations of anthropologists and geneticists, I hope to develop a model that will explain this marriage pattern in terms of the cultural transmission of societal norms and the effect of inbreeding depression. This model would take into account the probability of consanguineous marriages, the effect of such marriages on inbreeding, and the transmission of cultural norms that encourage first cousin marriage. Additionally, I hope to understand why societies that encourage consanguineous marriage have remained largely uninfluenced by interactions with cultures where the practice is stigmatized.

Mentors: Laura Fortunato and Jeremy Van Cleve