Complex Systems Summer School 2016

Computer hackers use specific strategies to penetrate systems. These strategies evolve over time, usually in response to the defense mechanisms employed by the system administrators. Being able to identify the strategies and when they change is of paramount importance to ensure the safety of the systems. Because data to help this effort is scarce, this paper explores the possibility of using competitive, strategic video game data as a proxy to identify strategies and their change points. The data chosen for this project is from the Defense of the Ancients (DOTA 2). This game is a rich data source of real-time adaptive adversaries. DOTA 2 is a multiplayer game where two teams of five individuals each compete against each other to complete objectives and to destroy the other team’s base in a time frame of ∼ 20 to ∼ 90 minutes, while taking on the guise of a ”hero” character. Professional games also include a draft, where heroes are chosen (or banned from being chosen) from a pool of ∼ 120 characters, each with specific abilities. The players deploy various in-game and between-game tactics and procedures to achieve a specific measurable objective. Professional players vie for tens of millions of dollars in prize pools each year, and over 2 billion games have been played. The results in this paper are using data from a cache of 500 GB of aggregated game data (∼ 2.5 million games played over one year) and raw, event-by-event data of ∼ 100 Mb per game. The goal is to use this data to shed light on how one can 1) detect and 2) quantify the rate of change of strategies in co-evolutionary systems. This paper will cover the complexity of the draft and employ hidden Markov models (HMM) to determine underlying structure both in the draft and in the gameplay itself. For the gameplay, the relative, normalized positions of all ten players were converted into system ”states”, which served as the observable input to the HMM. The time evolution of these observable states, and the results from the HMM for this part of the analysis are shown in Fig. 1. The dashed lines in the figure denote the breaks between stacked games. The code to estimate the model parameters and the most likely hidden state sequence was provided by Simon DeDeo ∗ . Also included in the figure is perhaps the most interesting aspect: the modules. These represent the stationary state that the system eventually evolves to and its longest lasting perturbation. As shown in the figure, for this set of data, a given game will be in either module 1 or 2 throughout the entirety of the game. Very little oscillation between these modules is observed within games. This is indicative of some underlying structure to be analyzed in future studies.LINK

Swidden farming in the Toledo district of Belize is a relatively young subsistence agricultural technique in which each farmer enlists help from his friends to clean a patch of land, grow crops, and harvest. The resulting near-reciprocal social network of exchange of agricultural labor constitutes an essential component of the coupled human natural system that operates in this region. This paper describes a preliminary effort to develop an agent-based model of this system, which started as a demonstration model in NetLogo and evolved into 3 candidate models that were evaluated for basic viability criteria to exhibit fundamental features of the Toledo district, such as its characteristic cultivation cycle in which a patch is usually farmed for 2 years at most, then left to fallow for 7 years at least. In our evaluation, we were able to conclude that the 3 proposed models cannot meet the proposed criteria, thus leaving us with the alternative of introducing the cycle as an explicit constraint. We plan to use what we have learned and the tools we have built in the development of future models that produce viable scenarios in order to move on to the study of social properties and emergent phenomena of such models.LINK

Human decision-making processes are inevitably influenced by mental images, which are triggered by cues such as objects, concepts, and words. The cognitive associations between words can be captured and represented as a semantic network, in which words represent nodes and association between words are edges. How efficiently can humans traverse this word association network to a given target word if, at each moment, they can only make choices about the next word they will visit? Using participant traversal data from the appropriately designed semantic game MindPaths, we show that human players do not rely on guessing, but navigate this association network quite efficiently, finding a specified target word often in the minimal number of steps. We construct models to capture human paths within the MindPaths game. We find that similarity in overall game length is easy to achieve with a trained random walker. We then consider a model of individual choices using Bayesian estimation of transition probabilities conditional on local network connectivity. We find that it is difficult to capture the individual decisions or the decision making process of human players. More complex models driven by semantic similarities and other types of relations between words are necessary to fully understand how individuals choose a particular path within this semantic word game.LINK

Opening wholesale power markets to speculative trading is a deliberate attempt to incorporate the benefits of competition and price discovery to a historical monopoly. Whether those benefits are being realized is an ongoing discussion, but it begs the question: do the new policies unintentionally make the grid more vulnerable to cascading failure? More importantly can we measure that vulnerability and take steps to minimize it, making our critical infrastructure more resilient and secure? Much of the power market research to date focuses on the optimization algorithms required to dispatch power and solve for location based pricing. Agent-based models have been constructed to investigate the economic impact of market deregulation, and the financial industry has employed data analytics and machine learning algorithms to measure financial risk associated with congestion contracts and other financial instruments (e.g.1–5 ). The perspective of most of these studies are the economic benefits and improvement of normal day-to-day business practices. Few studies, if any, have taken a grid security perspective at the Independent Service Operator level, which necessarily changes the study objectives and focus. This research takes a bottom-up approach to market operations in an effort to understand the risks of cascading failures at the national level. We analyze the processes employed by market participants to deliver power, and investigate if the underlying grid network structure and vulnerabilities can be inferred from the analysis.LINK

There are still considerable breaches between purely qualitative and quantitative approaches in many working models for group dynamics in psychology and social sciences. We argue that an interdisciplinary approach may help bridge these gaps towards more integrative models. We ran a discussion group based on the Operative Group Model (OGM), using a complex systems approach to reinterpret its dynamics, and applied network theory as well as thematic discourse analysis (DA). Finally, we consider the potential advantages of performing an acoustic analysis on the audio recordings from the group sessions. To our knowledge, this integrative approach has never been applied in the context of an OGM. In this study we provide two main levels of analysis: the participant’s personal and group experience, and the experimentation and analysis methods’ aspect. For the former, we gather data from group theory in psychology, psychoanalysis, the OGM, and the participants’ feedback. We then use DA and a bipartite graph identifying weighted “thematic nodes” as a research framework. Finally we explore possible ways to incorporate an acoustic analysis, notably implementing a Hidden Markov Model (HMM). The goal is to identify appropriate interdisciplinary models to analyze human group dynamics with both quantitative and qualitative methods. We present some preliminary results from overlapping data that might pinpoint movements towards group cohesion. We then discuss further considerations on the analysis framework and future applications. Finally we consider the advantages of implementing the OGM to foster meaningful interdisciplinary dialogue in research groups, notably to overcome communication difficulties between researchers and enhance collaboration.LINK

Lichenization is an evolutionarily and ecologically successful strategy for Ascomycete fungi, resulting in an estimated 18,000 lichen species. Although the nature of the lichen symbiosis is still widely debated, many sources agree that the lichen symbiosis represents an ecologically obligate mutualistic interaction whereby the net fitness of all partners is maximized. In order to elucidate the potential factors driving the evolution of the lichen symbiosis and the broader ecological and evolutionary interactions in the Lobaria pulmonaria model organism, an agent-based model was constructed using the ECHO framework. The ECHO tag system was used to model molecular recognition (receptors and physical embedding) between algal and fungal agents, two of the partners necessary to reconstitute the L. pulmonaria lichen symbiosis. We compared the simulations’ results with a bipartite reconstruction of L. pulmonaria microsatellite data and our model reproduced some features of this data. Molecular data have shown that the mode of reproduction significantly affects within-population genetic structure of L. pulmonaria, most likely contributing to the modular structure of this population. Our results also show that the interaction type does not significantly alter network metrics (modularity and nestedness), showing that fungal-algal interactions ranging from parasitic to mutualistic can support a successful or a stable biological organism.LINK

Modeling migratory paths of birds is an emerging area of complexity science in which attracts interdisciplinary collaborations from ornithologists, computer scientists, epidemiologist, and policy makers. However, due to the unpredictability of climate and habitat changes, our understanding of bird migratory paths is still limited. Not accounting for environmental changes when modeling bird migration will mislead our conservation efforts. Hence, in this paper, we are using validated training data to predict future stopover sites of migratory bird species. We used white-fronted geese migratory paths as training data and modeled stopover sites with Markov Chains to predict future changes on the stopover sites.This prediction will allow researchers to realize how to better conserve the habitat locations at and around stopover sites in the light of current climate changes. Since birds often stop and interact with the nearby environment, our work will also allow researchers to predict potential dangers emerged from long-range migrations, such as new avian viruses along these routes.LINK

Hierarchical organizations typically rely on a chain of command in which supervisors instruct subordinates to perform certain actions in order to advance the interests and objectives of the organization. The trust between supervisors and subordinates is essential for the functioning of such hierarchical organizations, as it ensures the eventual execution of instructions. Despite this, blind trust and obedience may lead to the execution of instructions with negative consequences, which may have been avoided had a subordinate been more critical of a supervisor’s instructions. We thus aim to model the development of trust between subordinates, their supervisors and the structures of the organization itself, subject to the understanding of the consequences of instructions by subordinates and the eventual outcomes of executed instructions. This is achieved through the construction of an agent-based model that is capable of replicating a number of intuitive behaviors and the use of this model to provide an indication of how trust develops over time.LINK

This research aims to explore the complexity inherent in the physical mass of cities—specifically in the materials that are stored within buildings and infrastructure. There is an important link between stocked materials and urban sustainability, particularly related to better understanding the resource requirements for the maintenance and growth of cities. This research explores materials stocked in Japanese cities, using a database with detailed GIS data of materials stored in buildings and roads at a resolution of one square kilometer. The analysis focuses on a single year, 2009 for buildings and 2010 for roads, and it includes two primary investigations: 1) urban scaling analyses to explore relationships between mass stocked, urban population, and other variables; and 2) non-parametric kernel estimations to better understand influential factors contributing to per-capita mass values. Results show a linear scaling relationship between mass stocked in buildings and urban area population, as well as a sublinear scaling relationships between mass stocked in roads, urban area population, and land area. The non-parametric kernel estimations revealed population density as a potentially influential factor.LINK

Complex networks of oscillatory components are ubiquitous in the natural and engineered worlds. These networks can display highly nontrivial dynamic behavior, which relies on an efficient and flexible communication structure for the synchronization of their subsystems. Crucially, these networks tend to show collective oscillatory dynamics in which information about the global state is shared between the distributed components. Quantifying the communication of information among these components has recently been addressed by Kirst et al. (Nat. Comm. 7, 2016). The authors found that the global “information routing pattern” (IRP) could be affected both by modifying a parameter in the dynamics of a single oscillator and by moving the system to a differing attractor of the global dynamics. To date, there is no established theory for information routing, and diverse information theoretic measures, each capturing different aspects of information transfer, that are typically applied. Kirst et al. adopted delayed versions of differential mutual information (dMI) and differential transfer entropy (dTE) to define information transfer and thus identify the IRPs. These measures are based on continuos (or differential) Shannon entropy. Discrete Shannon entropy has a clear interpretation in Information Theory; however, there are dilemmas in interpreting the continuous version. Interpretations have been suggested, but the meaning of “differential entropy” over continuous random variables is not satisfactorily explained. In this work we study one measure used by Kirst et al., delayed differential mutual information, on mathematical models of small networks to better understand what the resulting IRPs can reveal about a network. Specifically, we compute the dMI between each directed pair of nodes in various networks, in which noise is “injected” at the nodes and is propagated throughout the network. The computation is done by numerically solving the integral expression for dMI as presented by Kirst, et al., derived in the limit of weak noise around a known limit cycle attractor.

In this investigation, we study how the sophistication of popular music has changed in recent years. We perform a quantitative analysis of changing trends in pitch and chord usage in popular music. Using different statistical tools and models, the analysis reveals certain insights of music evolution in a quantitative and objective manner that complements the conventional theoretical study in the music community. For our analysis, we focus on two datasets: the Million Song Dataset, which presents pitch information of songs as a series of chroma features sampled at discrete time points, and the McGill Billboard Project dataset, which contains the chord progressions of a sample of 800 songs from the Billboard Hot 100 chart from 1958 to 1991. Regarding the pitch information, firstly, our result rejects one of the main conclusions of Serra et al (2012, Scientific Reports 2), which claims that the distribution of the usage frequency of codewords follows a power law. After a more careful analysis, we show that the distribution is much closer to lognormal through the usage of the BIC criteria. Hence the self-information of each codeword follows a normal distribution. Considering that the very notion of codewords is more mechanical than musically meaningful, we analyze the evolution of chord transitions in the McGill Billboard Project dataset through topic modeling (Latent Dirichlet Allocation). For certain types of popular songs, the chord transitions can be viewed as a layout of the underlying mood and the skeleton of a song. The topic model is able to identify some of the most popular chord progressions, and we can observe the evolution of their usage in different years, showing an increase in the variety of progressions during the 60’s, which has stayed static since then without significant changes. Finally, through the usage of information theoretic techniques, we investigate the temporal changes in the Shannon entropy of both the pitch chroma features extracted from the Million Song Dataset, and the chord transition topics extracted from the McGill Billboard Project. These calculations show evidence of a gradual increase in the sophistication in the usage of pitch information during the 1960s and 1970s, eventually peaking and remaining stable in the 1980s. Another crucial feature of how music has changed over time is the emergence of a greater range of genres. We assessed how the self-information of songs varied over time both within and between genres using Multilevel regression models which show there is significant variation in information between genres as well as between songs.

In this paper, we introduce a mechanistic model of migratory movement patterns in birds, inspired by ideas and methods from physics. Previous studies have shed light on the factors influencing bird migration but have mainly relied on statistical correlative analysis of tracking data. Our novel method offers a “bottom up” explanation of population-level migratory movement patterns. It differs from previous mechanistic models of animal migration and enables predictions of pathways and destinations from a given starting location. We define an “environmental potential” landscape from environmental data and simulate bird movement within this landscape based on simple decision rules drawn from statistical mechanics. We explore the capacity of the model by qualitatively comparing simulation results to the non-breeding migration patterns of a seabird species, the Black-browed Albatross (Thalassarche melanophris). This minimal, two-parameter model was able to capture remarkably well the previously documented migration patterns of the Black-browed Albatross, with the best combination of parameter values conserved across multiple geographically separate populations. Our physics-inspired mechanistic model could be applied to other bird and highly-mobile species, improving our understanding of the relative importance of various factors driving migration and making predictions that could be useful for conservation.

Species and interactions are being lost at alarming rates and it is imperative to understand how communities assemble if we have to prevent their collapse and restore lost interactions. Using an 8-year dataset comprising nearly 20 000 pollinator visitation records, we explore the assembly of plant–pollinator communities at native plant restoration sites in an agricultural landscape. We find that species occupy highly dynamic network positions through time, causing the assembly process to be punctuated by major network reorganisations. The most persistent pollinator species are also the most variable in their network positions, contrary to what preferential attachment – the most widely studied theory of ecological network assembly – predicts. Instead, we suggest assembly occurs via an opportunistic attachment process. Our results contribute to our under- standing of how communities assembly and how species interactions change through time while helping to inform efforts to reassemble robust communities.LINK

We have explored the evolution of stylized artificial languages using a spatial model in which agents are free to move and interact when in close proximity. Interactions consist of communication attempts, which can either succeed or fail depending on the distance between the vocabularies used by each partner. The aggregate rate of successful communications is defined as global mutual intelligibility. A unit of communication is a set of words composed by syllables. Language evolves either through inter-agent influence (an agent may adopt his partner’s inflections) or random mutations. We look for unexpected, emerging properties of the system. Our findings indicate that simple rules are sufficient to generate statistically significant language communities, that the introduction of memory changes the emergent language in non-intuitive ways and that geography has a significant impact on language structure.

The global world order is increasingly experiencing a rise in “populism”, a national trend that argues for more closed borders and an inward focus. The broader trend is often rooted in a backlash against the great era of globalization that has been expanding since the close of Cold War. While these sentiments are often unsettling in geopolitics, and in global economics, they are not unique to the 21st century. Such public outcries formed in the era that closed the 19th century and led to the first World War. While we are unable to tell the trajectory of today’s populism, in the 19th century, it came on the heals of an unprecedented era of globalization. Led by Great Britain, the 19th century was marked by massive global trend, open borders, and a vastly increasing shipping industry. Those trends, among many others, led to a vastly complex system of shifting and growing global populations, evolving national borders, conflicts between nations, and a greater demand for goods. Even today, while historians and economists are able to point to the many hallmarks of the 19th century era of globalization, few are able to articulate how these systems were connected, how they interacted and ultimately, what the ‘physical world wide web’ was driven by. In this paper, a large trove of publicly accessible data from the Port of Trieste is used as the first in a series of studies to build data on the flow of goods between ports, and how that flow reflects geopolitical changes around the world. This data is significant in that it was captured by two reliable sources: the historical leger of the Chamber of Commerce of Trieste and, Generali, a major insurance company of the 19th century. The work aims to identify how global export and import trends display the underlying behavior that led toward “populism” in the late 19th century and ultimately, two World Wars. An information theoretic measure, Kullback-Leibler divergence, is leveraged to overlay the data of Generali’s insurance legers, investments, and risk analytics to further identify the complex interplay of global trade in geopolitics. In a first of several iterations on this research, a focus was put on using quantitative tools to extract patterns from data, in order to understand the dynamics of trade. A complementary approach is then to understand the processes at the origin of those patterns. No concrete findings are yet apparent. However, correlations in insurance data, specifically, financial risk in bond investments as a forecast for global uncertainty is one of many fascinating trends. Next iterations will overlay more variables, especially those from human and environmental disasters that would further correlate to shipping patters on specific goods, insurance investment strategy, and ultimately how a global economy moved from radically open to an intractable geopolitical system that sparked WWI.

Walking behavior is central to all mobile animals. However, it is still an open question as to Whether this behavior can be affected or even regulated by learning in animal models. In this paper, we addressed this question by using a fruit fly walking behavior Bob Dylan Box data se. Fruit flies have robust walking behavior in the Bob Dylan box (see figure below), and this walking behavior can be perturbed by heat stress. Using four flies as examples, we segmented the behavioral traces according the two distinct behavioral states: walking and pause, and found that after heat stress training, the initial robust walking behavior of a fly, the long and continuous walking segments separated by brief pause, changed into irregular bursty walking pattern: short walk spaced between long and short pauses. Our methods and analysis can be used for the rest of the Bob Dylan data set.

Mobility and movement of people is a driver for growth, development, and culture within a city. In a world where urbanization is becoming more and more important, unravelling the interplay between these topics is crucial. A proxy for such mobility are residential flows, or movement between residences. Using a novel dataset, we studied the residential mobility of the city of Madrid, Spain, over a 11-year period from 2004 to 2015, and assessed the effect of the 2008 financial crisis on residential mobility flows. We characterized mobility flows within and in and out of the city of Madrid, stratified by age, education and country of origin. We characterized the mobility network using centrality measures and looked for communities of residential mobility. We explored the characteristics of these communities and the mobility preferences within and between them. Residential mobility flows followed a strong temporal pattern mirroring the economic performance of the housing market: large mobility flows appear in the mid 2000s, in the midst of the economic boom, and were reduced afterwards. Nonetheless, some of the areas displayed strong mobility flows through the entire period. These areas were almost entirely developed through the 2000s and some of them even continued developing after the recession. We observed a spatial pattern in the communities of residential mobility flows. We found six groups of neighborhoods that represented areas in different stages of development and socioeconomic status. The evolution of these six communities in terms of sociodemographic and socioeconomic characteristics diverged over time and allowed for a very detailed description of each (e.g.: one of the communities displayed clear signs of gentrification). Mobility preferences within and between communities changed widely after the economic recession, as some areas became more segregated while others mixed more. In summary, we managed to describe a residential mobility network of an entire city finding promising patterns for future research. Of special interest are the changes that happened after the 2008 recession, where future research will be headed to.

Hierarchical organizations typically rely on a chain of command in which supervisors instruct subordinates to perform certain actions in order to advance the interests and objectives of the organization. The trust between supervisors and subordinates is essential for the functioning of such hierarchical organizations, as it ensures the eventual execution of instructions. Despite this, blind trust and obedience may lead to the execution of instructions with negative consequences, which may have been avoided had a subordinate been more critical of a supervisor’s instructions. We thus aim to model the development of trust between subordinates, their supervisors and the structures of the organization itself, subject to the understanding of the consequences of instructions by subordinates and the eventual outcomes of executed instructions. This is achieved through the construction of an agent-based model involving a hierarchical network structure that is capable of replicating a number of intuitive behaviors and the use of this model to provide an indication of how trust develops over time. As one would expect, we find that in organizations where the information accessible to members is relatively sparse, which is likely the case in many hierarchical organizations where the upper echelons of leadership have sole access to most organizational secrets, that good leadership inspires an overall higher level of relational trust within the organization than in the case of poor leadership. Despite this, however, we demonstrate that in our hypothetical, hierarchical organization that good leadership is not a prerequisite for organizational success, provided that members of the organization are allowed to disobey orders if perceived that doing so is in the interests of the organization. We show that in such organizations, agents are capable of learning to identify who and who not to trust based on iterative adjustments of trust based on the overall outcome of specific tasks or missions, eventually resulting in a robust organization in the cases of both good or bad leadership. In the case of highly-informed agents, we demonstrate that bad leadership may lead to greater stability, with agents tending to make decisions based on available information rather than trust, eventually relegating the leader to a symbolic role. In contrast to this, good leadership may result in the development of trust which is desirable in most cases, but may also result in the propagation of bad orders if a historically good leader unexpectedly gives a bad order, which may lead to disaster for the organization.

In this paper, we introduce a mechanistic model of migratory movement patterns in birds, inspired by ideas and methods from physics. Previous studies have shed light on the factors influencing bird migration but have mainly relied on statistical correlative analysis of tracking data. Our novel method offers a bottom up explanation of population-level migratory movement patterns. It differs from previous mechanistic models of animal migration and enables predictions of pathways and destinations from a given starting location. We define an environmental potential landscape from environmental data and simulate bird movement within this landscape based on simple decision rules drawn from statistical mechanics. We explore the capacity of the model by qualitatively comparing simulation results to the non-breeding migration patterns of a seabird species, the Black-browed Albatross (Thalassarche melanophris). This minimal, two-parameter model was able to capture remarkably well the previously documented migration patterns of the Black-browed Albatross, with the best combination of parameter values conserved across multiple geographically separate populations. Our physics-inspired mechanistic model could be applied to other bird and highly-mobile species, improving our understanding of the relative importance of various factors driving migration and making predictions that could be useful for conservation.LINK