Search

We model customer mobility and congestion in supermarkets and investigate how these two processes depend on the layout of a store. Our motivation is twofold: we seek to understand how customers move in supermarkets and how to arrange the layout of a supermarket to reduce congestion in it. Congestion affects both the shopping experience and the bottom line of supermarkets, so models that can estimate customer mobility and congestion in new store layouts are of great interest to retailers. We use random-walk models and population-level mobility models to model customer mobility, and we use queues and queueing networks to model congestion. We represent a store as a network in which the nodes are zones in a supermarket and edges connect adjacent zones. Customers traverse the network from node to node and queue at each node. We measure congestion by the total mean queue size Q (which is equivalent to the total number of customers in a store). We are interested in how network topology (representing store layout) affects Q. We first examine a simple model of single-source, single-sink queueing networks with unbiased random walkers. We analyse the relationship between congestion (specifically, Q) and network topology, and we describe network topologies that minimize Q. We also present efficient greedy algorithms for edge addition and deletion to reduce Q. We then consider human-mobility models and use them to estimate mobility flows between zones in a supermarket. These models have, to our knowledge, not been applied previously to problems with such small spatial scales. We applied the human-mobility models to 17 supermarkets, and we find that they can successfully estimate 65-70% of the mobility flow in a supermarket. We also find that the parameters in our models do not change markedly between different stores and different time periods of the same store. One can therefore calibrate the parameters of our models on one store and then use the models to estimate mobility flow in all other stores using only purchase data and the store layouts. Finally, we integrate the human-mobility models into a queueing-network framework to estimate congestion in supermarkets. We present a simple optimization algorithm that swaps the locations of aisles and finds store layouts with significantly smaller values of Q. In these store layouts, popular nodes are often moved from the centre of a store to the perimeter. Our research helps improve understanding of customer mobility and congestion in supermarkets, especially the relationship between congestion and store layout. Our models and ideas are also relevant for complex systems on similar spatial scales (eg, mobility of visitors in a museum).

Robustness and entropy are widely used concepts in the study of networks in various disciplines. There exist various notions of network robustness and network entropy, because there are many network properties that can be robust to perturbations and there are many network-associated distributions for which one can calculate a notion of entropy. In this dissertation, we explore several notions of robustness and entropy --- and connections between them --- on networks. We investigate the robustness of structural properties of protein-interaction networks to the targeted removal of nodes and propose a test for identifying structural properties that are plausible proxies for measures of performance or viability of a protein-interaction network. Several researchers have suggested that structural redundancy and functional redundancy are important mechanisms by which a biological system can achieve robustness. A connection between redundancy and the mean subsystem entropy of a network with Ornstein--Uhlenbeck dynamics motivates our study of the relationship between the entropy of a multivariate Ornstein--Uhlenbeck process and the structure of an underlying network. We introduce walk graphs as a type of network motif that can help one understand the relationship between network structure and the covariance and entropy of a multivariate Ornstein--Uhlenbeck process. Because of the large number of subsystems in systems with as few as 20 nodes, studying the mean entropy of subsystems computationally is a difficult task. To address this issue, we derive sampling guarantees that indicate that one can calculate a very accurate sample mean of subsystem entropy by sampling very few subsystems. The results in this dissertation offer new approaches to studying performance, viability, and robustness of systems on the basis of network structure and dynamics on networks. They demonstrate the importance of the choice of an appropriate performance measure for the study of network robustness and provide a framework for identifying plausible performance measures or plausible proxies of performance measures. The analysis of walk graphs and their contribution to covariance and entropy demonstrates that it can be useful to consider dynamics on a network (instead of just a network's structure) as a composite entity that one can decompose into many small parts. This decomposition of dynamics on networks provides a framework for studying the mechanisms by which dynamics and network structure contribute to covariance, entropy, redundancy, and other properties of dynamics on networks.

Phenomena related to disorder and nonlinearity have been studied in many different context in physics, from condensed-matter physics to optics, with a substantial potential for applications. In particular, in mechanical systems, one can think of "smart" materials that adapt their properties, such as thermal conductivity or wave-transmission properties, depending on external stimuli, such as changes in pressure. It is the aim of this dissertation study transport and localization properties of one-dimensional disordered and quasiperiodic granular crystals as a function of an external precompression on the system. To archive this, we first study the scattering problem of a single impurity in a homogeneous granular chain and we demonstrate the existence of analogs to quantum resonances. We then study spreading of initially localized excitations. We thereby investigate localization phenomena in strongly nonlinear systems, which are fundamentally different from such phenomena in linear and weakly nonlinear systems. We conduct a thorough comparison of wave dynamics in chains with three different types of disorder: an uncorrelated (Anderson-like) disorder and two types of correlated disorders (which are produced by random dimer arrangements). We find that, in most of the cases studied the behavior of the second moment and the inverse participation ratio for large times are given by power laws. However, for low levels of precompression and initial perturbations on the displacement of the particles, we find out that there is not a clear trend for the second moment. For an Anderson-like uncorrelated disorder, we find some regimes in the parameter space where a transition from subdiffusive to superdiffusive dynamics emerges depending on the amount of precompression in the chain. By contrast, for the correlated disorders, we find that the dynamics is superdiffusive for any precompression level. Additionally, for large precompression, the inverse participation ratio decreases slowly and the dynamics leads to partial localization around the initial wave. This localization phenomenon does not occur in the sonic vacuum regime, which yields that spontaneous localization is no longer possible. We also study quasipediodic granular crystals, in particular, localization of waves in strongly precompressed granular chains induced by quasiperiodicity. We propose three different set-ups, inspired by the Aubry--André (AA) model, of quasiperiodic chains; and we use these models to compare the effects of on-site and off-site quasiperiodicity. When there is purely on-site quasiperiodicity, which we implement in two different ways, we show for a chain of spherical particles that there is a localization transition (as in the original AA model). However, we observe no localization transition in a chain of cylindrical particles in which we incorporate quasiperiodicity in the distribution of contact angles between adjacent cylinders by making the angle periodicity incommensurate with that of the chain. For each of our three models, we compute the Hofstadter spectrum and the associated Minkowski--Bouligand fractal dimension, and we demonstrate that the fractal dimension decreases as one approaches the localization transition (when it exists). We also show, using the chain of cylinders as an example, how to recover the Hofstadter spectrum from the system dynamics. Finally, in a suite of numerical computations, we demonstrate localization and also that there exist regimes of ballistic, superdiffusive, diffusive and subdiffusive transport.

Networks are abstract representations of systems in which objects called "nodes" interact with each other via "edges", typically in a pairwise fashion. Examples of networks include neurons interacting via synapses in the brain, people connected on an online social network, and cities linked by roads. Most real-world networks have a complex structure that is neither fully random nor fully regular, and characterising their "mesoscale" structures is an important topic in network science that is traditionally known as "community detection". Two of the most popular approaches for community detection are maximising an objective function called "modularity" and performing statistical inference using stochastic block models, and these both play a prominent role in our work. For many applications, an ordinary graph is an inadequate representation of the underlying data. In this thesis, we study community detection in networks that incorporate additional features beyond a set of nodes linked together by edges. First, we study annotated networks, which include additional data as node labels that help describe the network architecture. We then consider multilayer networks, which combine a collection of related networks into a single object. We uncover a deep connection between multilayer modularity maximisation and some multilayer stochastic block models, and we use this result to guide the selection of tuning parameters in modularity maximisation. Finally, we study correlated multilayer networks, in which we sample edges that connect a given pair of nodes across multiple layers from multivariate distributions, rather than as independent events. Throughout this thesis, we are guided by consumer-behaviour applications. Specifically, we study "bipartite" networks in which customers are linked to products that they previously purchased. Detecting communities in these networks is valuable for designing personalised recommendation systems and for other business insights. We illustrate our main methodological contributions on consumer-product networks that we construct using "pseudonymised" transaction data from several stores of a large UK retailer.

Protein interaction networks (PINs) are mathematical representations of interactions between proteins within organisms. Studying their properties can give insights into biological functions and the importance of proteins, and it can therefore aid in drug- discovery. Graphs are the most common mathematical object used to represent PINs. In this thesis, we investigate generalised mathematical representations of PINs. In particular, we examine multilayer networks (MLNs) and node-weighted networks. These mathematical objects allow the construction of temporal PINs and tissue-specific PINs by combining gene-expression data with PINs. We introduce promiscuity as an information-theoretical measure of a node's distribution of neighbours across different layers in MLNs. We examine promiscuity in synthetic networks and tissue-specific PINs and find that the vast majority of proteins are not cell-type specific. Integrating temporal gene-expression data with PINs allows us to create temporal PINs in the form of MLNs. We investigate an eigenvector-based temporal centrality in a temporal PIN of yeast during the cell cycle. We thereby examine the change of proteins' importance over time, which reflects their activity during the cell cycle. We then discuss the detection of community structure in node-weighted networks. For synthetic networks, we show that considering node weights can alter detected community structure. We combine a human PIN with gene-expression data to construct tissue-specific PINs and investigate their community structure. Comparing the detected communities with gene-ontology information, we find some tissue-specific functions of these PINs. Overall, the case studies in this thesis suggest that MLN and node-weighted networks are suitable for the integration of protein-interaction data with other biological data sets.

Animals perform an extraordinary variety of movements over many different time scales. To support this diversity, the motor cortex (M1) exhibits a similarly rich repertoire of activities. Although recent neuronal-network models capture many qualitative aspects of M1 dynamics, they can generate only a few distinct movements all with the same duration. Therefore, these models can still not explain how M1 efficiently controls movements over a wide range of shapes and speeds. In this thesis, we demonstrate that simple modulation of neuronal input-output gains in recurrent neuronal-network models with fixed connectivity can dramatically reorganise neuronal activity and thus downstream muscle outputs. Consistent with the observation of diffuse neuromodulatory projections to M1, our results suggest that a relatively small number of modulatory control units provide sufficient flexibility to adjust high-dimensional network activity on behaviourally relevant time scales. Such modulatory gain patterns can be obtained through a simple reward-based learning rule. Novel movements can also be assembled from previously learned primitives, thereby facilitating fast acquisition of hitherto untrained muscle outputs. Moreover, we show that it is possible to separately change movement speed while preserving movement shape, thus enabling efficient and independent movement control in space and time. Our results provide a new perspective on the role of neuromodulatory systems in controlling cortical activity and suggest that modulation of single-neuron responsiveness is an important aspect of learning.

Drosophila courtship song has been studied for over 60 years and remains an area of active research today. Several studies have investigated the physiological mechanisms for fly song production, but no unifying account exists. We review fly song production and integrate published data to a mathematical model of courtship song production. We hypothesize that muscle dynamics underlie fluctuations in the amplitude of courtship song. Our model suggests that these fluctuations can be measured and we introduce the term 'song amplitude structure' (SAS) for those measurements. We predict that SAS signals muscle power and we validate our prediction in muscle mutants of the Drosophila myosin light chain (Dmlc2) gene. We then investigate whether SAS is a communication signal in Drosophila. We show that the two species D. melanogaster and D. simulans differ in their SAS and that both females and males behaviourally discriminate their species SAS from other SAS. This suggests that SAS is a communication signal in Drosophila. Perception of SAS may be affected by noise and we therefore examine the effect of noise on responses to SAS. We find that female auditory responses are not impaired by noise in SAS, however male auditory responses are impaired by noise in SAS. This suggests that males and females may be processing noise in SAS differently. Future work should investigate whether sexually dimorphic auditory neurons respond differently to noise in SAS. We hope that our work will be helpful for investigating fluctuations in amplitude of fly song. We also wish that researchers can use our work for studying the mechanisms underlying both the production of SAS and the perception of SAS.

Many real-world applications in the social, biological, and physical sciences involve large systems of entities that interact together in some way. The number of components in these systems can be extremely large, so some simplification is typically needed for tractable analysis. A common representation of interacting entities is a network. In its simplest form, a network consists of a set of nodes that represent entities and a set of edges between pairs of nodes that represent interactions between those entities. In this thesis, we investigate clustering techniques for time-dependent networks. An important mesoscale feature in networks is communities. Most community-detection methods are designed for time-independent networks. A recent framework for representing temporal networks is multilayer networks. In this thesis, we focus primarily on community detection in temporal networks represented as multilayer networks. We investigate three main topics: a community-detection method known as multilayer modularity maximization, the development of a benchmark for community detection in temporal networks, and the application of multilayer modularity maximization to temporal financial asset-correlation networks. We first investigate theoretical and computational issues in multilayer modularity maximization. We introduce a diagnostic to measure persistence of community structure in a multilayer network partition and we show how communities one obtains with multilayer modularity maximization reflect a trade-off between time-independent community structure within layers and temporal persistence between layers. We discuss computational issues that can arise when solving this method in practice and we suggest ways to mitigate them. We then propose a benchmark for community detection in temporal networks and carry out various numerical experiments to compare the performance of different methods and computational heuristics on our benchmark. We end with an application of multilayer modularity maximization to temporal financial correlation networks.

Networks are an abstract representation of connections (the "edges") between entities (the "nodes"). One can represent many different types of data in this way, including many social, biological, technological and physical systems. Examples we discuss in this thesis include networks of friendship ties between individuals on Facebook, coauthorship networks between scientists, and similarities in voting patterns between members of the US Congress. Analysing intermediate-sized (or "meso-scale") features often reveals insights about a network's structure and function. A particular type of meso-scale feature are "communities", where one typically thinks of a community as a set of nodes that is particularly "well-connected" internally but has "few" connections to other nodes in a network. A complementary interpretation of a community is as a set of nodes that "trap" a diffusion-like dynamical process for a "long" time. Based on this dynamical interpretation, we investigate "size-resolved community structure" in networks by identifying bottlenecks of locally-biased dynamical processes that start at seed sets of nodes. By sampling many different local communities for different seeds and different strengths of the locality bias of the dynamical process, we obtain a picture of the way communities at different size scales compare in a network. This "size-resolved community structure" provides a signature of community structure in a network and its qualitative features are related to the way local communities combine to form the larger scale structure of a network. For many data sets, ordinary networks are not sufficient to represent the detailed connectivity patterns. For example, connections often evolve over time and one may have different types of connections between the same entities. Multilayer networks provide a framework to represent these different types of situations. The perspective of communities as bottlenecks to dynamical processes extends in a natural way to multilayer networks and we use it to illustrate that two types of random walk on a multilayer network that have been used as the basis for identifying communities in a multilayer network correspond to very different notions of what it means for a set of nodes to be a good multilayer community. This exemplifies the need for multilayer benchmark networks with known community structure to compare the ability of different methods to identify intuitive community structure. We propose a method for generating benchmark networks with general multilayer structure and use it as the basis for a preliminary comparison of different multilayer community detection methods. Finally, we use multilayer community detection to analyse survey data about people's perception of their hair. One key advantage of this type of data compared to most traditional network data sets is that we have a large number of potential explanatory variables that we can use to interpret the results of identifying communities which allows us to identify some potentially interesting hypothesis.

The landscape of world migration involves multiple interacting movements of people at various geographic scales, posing significant challenges to the dyadic-independence assumption underlying standard migration models. To account for emerging patterns of multilateral migration relationships, we represent world migration as a time-evolving, spatial network. The nodes in the World Migration Network (WMN) are countries located in geographic space, and the edges represent migratory movements for each decade from 1960-2000. In the first part of the thesis, we characterise the spatial network structure of the WMN, with a particular focus on detecting and mapping mesoscopic structures called 'communities' (i.e., sets of countries with denser migration connections internally than to the rest of the WMN). We employ a method for community detection that simultaneously accounts for multilateral migration, spatial constraints, time-dependence, and directionality in the WMN. We then introduce an approach for characterising local (intracommunity) and global (intercommunity) connectivity in the WMN. On this basis, we define a threefold typology that distinguishes 'cave', 'bi-regional', and 'bridging' communities. These are characterised with distinct migration patterns, spatial network structures, and temporal dynamics: cave communities are tightly-knit enduring structures that channel local migration between contiguous countries; bi-regional communities merge migration between two distinct geographic regions; bridging communities have hub-and-spoke dynamic structures that emerge from globe-spanning movements. Our results suggest that the WMN is neither a globally interconnected network nor reproducing geographic boundaries but involves heterogeneous patterns of global and local ('glocal') migration connectivity. We examine a set of relational, homophily, and spatial mechanisms that could have possibly generated the 'glocal' structure we observe. We found that communities of different types arise from significantly different mechanisms. Our results suggest that migration communities can have important implications for world migration, as different types of community structure provide distinct opportunities and constraints, thereby distinctively shaping future migration patterns.

Networks are a useful quantitative representation for complex systems of interacting entities arising in fields such as biological, physical and social sciences. A network representation provides a degree of simplification while capturing key connectivity patterns. This thesis focuses on two main themes: the study of community structure, an important mesoscopic feature of many networks, and its application to study spatiotemporal spread of infectious diseases. Community detection seeks to partition a network into dense sets of nodes that are connected sparsely to other dense sets. The notion of denseness is often relative to some "null model" that describes baseline connectivity that can be construed to occur randomly. In the first part of the thesis, we discuss the incorporation of spatial information into null models for community detection. We develop a spatial null model based on the radiation model of mobility. We test different spatial null models using static and temporal (multilayer) spatial benchmarks with planted partitions that represent interactions between human populations. Our results indicate that it is important to incorporate spatial information into null models for community detection, but it is best to incorporate only relevant information into null models, as extraneous information can lower performance. In the second part of the thesis, we present the results of community detection with different null models on disease-correlation networks generated form real and synthetic time series of disease occurrence. We use data sets for endemic diseases (established in a region, with occasional epidemic outbreaks) and emerging diseases (newly-discovered or introduced into a region for the first time). We study the spatial and temporal organization of partitions. Finally, we apply community detection with different null models to synthetic time series generated from an agent-based model (ABM) simulating the spread of endemic and emerging diseases between spatially-embedded cities with a planted, transport-based community structure. We compare the findings on real and synthetic data sets, and we searched for model parameter regimes in which we are able to detect planted partitions or other interesting communities. For emerging diseases, we find spatial communities that are associated with the first times the infection reached a node in both ABM and disease data. For endemic diseases, we are unable to find planted or spatial communities in the ABM data, but we detect spatial communities for two of the three disease data sets. For these diseases, we also detect temporal communities corresponding to some of the important time points in disease history. We hope that these results show that community structure of disease correlation networks appears to be more complicated than simple spatial patterns and is a fascinating topic to study.

Traditionally, differential-equation models for population dynamics have considered organisms as "fixed" entities in terms of their behaviour and characteristics. However, there have been many observations of adaptivity in organisms, both at the level of behaviour and as an evolutionary change of traits, in response to the environmental conditions. Taking such adaptiveness into account alters the qualitative dynamics of traditional models and is an important factor to be included, for example, when developing reliable model predictions under changing environmental conditions. In this thesis, we consider piecewise-smooth and smooth dynamical systems to represent adaptive change in a 1 predator-2 prey system. First, we derive a novel piecewise-smooth dynamical system for a predator switching between its preferred and alternative prey type in response to prey abundance. We consider a linear ecological trade-off and discover a novel bifurcation as we change the slope of the trade-off. Second, we reformulate the piecewise-smooth system as two novel 1 predator-2 prey smooth dynamical systems. As opposed to the piecewise-smooth system that includes a discontinuity in the vector fields and assumes that a predator switches its feeding strategy instantaneously, we relax this assumption in these systems and consider continuous change in a predator trait. We use plankton as our reference organism because they serve as an important model system. We compare the model simulations with data from Lake Constance on the German-Swiss-Austrian border and suggest possible mechanistic explanations for cycles in plankton concentrations in spring.

Krivelevich and Patkós conjectured in 2009 that χ(G(n, p)) ∼ χ=(G(n, p)) ∼ χ∗=(G(n, p)) for C/n < p < 1 − ε, where ε > 0. We prove this conjecture for n−1+ε1 < p < 1 − ε2 where ε1, ε2 > 0. We investigate several measures that have been proposed to indicate centrality of nodes in networks, and find examples of networks where they fail to distinguish any of the vertices nodes from one another. We develop a new method to investigate core-periphery structure, which entails identifying densely-connected core nodes and sparsely-connected periphery nodes. Finally, we present an experiment and an analysis of empirical networks, functional human brain networks. We found that reconfiguration patterns of dynamic communities can be used to classify nodes into a stiff core, a flexible periphery, and a bulk. The separation between this stiff core and flexible periphery changes as a person learns a simple motor skill and, importantly, it is a good predictor of how successful the person is at learning the skill. This temporally defined core-periphery organisation corresponds well with the core- periphery detected by the method that we proposed earlier the static networks created by averaging over the subjects dynamic functional brain networks.

During the past 30 years, the proliferation of electronic trading has catalysed profound structural change in the global foreign exchange (FX) spot market. Today, more than 60% of the market's volume occurs via electronic trading platforms, which provide traders with round-the-clock market access from anywhere in the world. Such platforms offer several practical benefits that have encouraged market participation from a broad new class of financial institutions and have thereby spurred market growth. The most widely used electronic trading platforms in the FX spot market incorporate several features that differentiate them from those used in other financial markets. These features raise many important questions about order flow, market state, price formation, trader behaviour, and volatility. Despite the enormous trade volumes that such platforms facilitate, these questions have received almost no attention to date. In this thesis, we study a recent, high-quality data set from a large electronic trading platform in the FX spot market in order to investigate several aspects of trading via this mechanism. We calculate a wide range of statistics regarding order flow and market state, and we highlight how our findings contrast to those reported by empirical studies of electronic trading platforms in other markets. We study the autocorrelation properties of returns, absolute returns, and order flow, and we investigate the extent to which the market's organization impacts price formation. We also introduce a model designed to reproduce the most important properties of trading via such a platform. We derive several results regarding the model's temporal evolution, and we simulate the model to investigate how the interactions between individual traders influence volatility. We conclude that electronic trading platforms in the FX spot market retain many desirable features of centralized markets while providing traders with explicit control over their personal trading partnerships.

In this thesis we propose some new approaches to the study of complex networks, and apply them to multiple domains, focusing in particular on protein-protein interaction networks. We begin by examining the roles of individual proteins; specifically, the influential idea of 'date' and 'party' hubs. It was proposed that party hubs are local coordinators whereas date hubs are global connectors. We show that the observations underlying this proposal appear to have been largely illusory, and that topological properties of hubs do not in general correlate with interactor co-expression, thus undermining the primary basis for the categorisation. However, we find significant correlations between interaction centrality and the functional similarity of the interacting proteins, indicating that it might be useful to conceive of roles for protein-protein interactions, as opposed to individual proteins. The observation that examining just one or a few network properties can be misleading motivates us to attempt to develop a more holistic methodology for network investigation. A wide variety of diagnostics of network structure exist, but studies typically employ only small, largely arbitrarily selected subsets of these. Here we simultaneously investigate many networks using many diagnostics in a data-driven fashion, and demonstrate how this approach serves to organise both networks and diagnostics, as well as to relate network structure to functionally relevant characteristics in a variety of settings. These include finding fast estimators for the solution of hard graph problems, discovering evolutionarily significant aspects of metabolic networks, detecting structural constraints on particular network types, and constructing summary statistics for efficient model-fitting to networks. We use the last mentioned to suggest that duplication-divergence is a feasible mechanism for protein-protein interaction evolution, and that interactions may rewire faster in yeast than in larger genomes like human and fruit fly. Our results help to illuminate protein-protein interaction networks in multiple ways, as well as providing some insight into structure-function relationships in other types of networks. We believe the methodology outlined here can serve as a general-purpose, data-driven approach to aid in the understanding of networked systems.

Knowledge of protein sequences has exploded, but knowledge of protein function is needed to make use of sequence information, and this lags behind. A protein's function must be understood in context and part of this is the network of interactions between proteins. What are the relationships between protein function and the structure of the interaction network? In the first part of my thesis, I investigate the functional relevance of clusters, or communities, of proteins in the yeast protein interaction network. Communities are candidates for biological modules. The work I present is the first to systematically investigate this structure at multiple scales in such networks. I develop novel tests to assess whether communities are functionally homogeneous, and demonstrate that almost every protein is found in a functionally homogeneous community at some scale. The evolution of protein sequences is well-studied, but comparatively little is known about the evolution of protein function. Such knowledge is needed to understand when it is appropriate to annotate newly sequenced proteins by transferring functional information from homologs-i.e. evolutionarily related proteins. In the second part of my thesis, I assess the success of transferring protein-protein interactions across species and use this to estimate the rate at which interactions are lost in evolution. At levels of sequence similarity associated with functional annotation transfer, I demonstrate that protein-protein interaction transfer is unreliable. The relevance of community structure for understanding protein function and the low conservation of individual interactions, suggests a possible role for communities in the evolution of cellular function. I discuss this possibility in my conclusions.