School of Mathematics and Statistics - Theses
Permanent URI for this collection
Search Results
1 - 10 of 226
-
ItemInstance Space Analysis for the Maximum Flow Problem( 2023)The Maximum Flow Problem (MFP) is a fundamental network flow theory problem, for which many algorithms, supported by strong theoretical worst-case analyses, have been proposed. Due to its theoretical and practical importance in network theory, designing effective algorithms for the Maximum Flow Problem (MFP) remains a focus of research efforts. Although the worst-case performance analysis is the main tool for examining the performance of these algorithms, their practical efficiency depends on the network structure, making it unclear which algorithm is best for a particular instance or a class of MFP. Instance Space Analysis (ISA) is a methodology that provides insights into the such per-instance analysis. In this thesis, the instance space of MFP is constructed and analysed for the first time. To this end, novel features from the networks are extracted, capturing the performance of MFP algorithms. Additionally, this thesis expands the ISA methodology by addressing the issue of how benchmark instances should be selected to reduce bias in the analysis. Using the enhanced ISA (EISA) methodology with MFP as the case study, this thesis demonstrates that the most important features can be detected, and machine learning methods can identify their impact on algorithm performance, whilst reducing the bias caused by over-representation within the selected sample of test instances. The enhanced methodology enables new insights into the performance of state-of-the-art general-purpose MFP algorithms, as well as recommendations for the construction of comprehensive and unbiased benchmark test suites for MFP algorithm testing. To get further insight into the strengths and weaknesses of the algorithms, CPU time and fundamental operations counts are used as algorithm performance measures. Using EISA, it is revealed that the arc/path finding strategies employed by the algorithms explain critical differences in the algorithms’ behaviours. We leverage these insights to propose two new initialisation strategies, which are an essential part of the arc/path finding strategy. To employ these new strategies on our previously studied algorithms, we propose modifications that result in 15 new algorithmic variants. We examine the impact of these proposed initialisation strategies on the algorithm performance and discuss the conditions under which each initialisation strategy is expected to improve the performance. The implementations of the new algorithmic variants are also presented. Finally, the limitations of the study and opportunities for interesting future work are discussed.
-
ItemCayley graphs and graphical regular representations( 2022)A graph is vertex-transitive if its full automorphism group acts transitively on the vertex set of the graph. Cayley graphs form one of the most important families of vertex-transitive graphs. A graphical regular representation (GRR for short) of a group G is a Cayley graph of G whose full automorphism group is equal to the right regular permutation representation of G. In 1982, Babai, Godsil, Imrich and Lovasz conjectured that except for Cayley graphs of two infinite families of groups---abelian groups of exponent greater than 2 and generalized dicyclic groups---almost all finite Cayley graphs are GRRs. In the study of GRRs of finite simple groups of small valencies, Fang and Xia conjectured that with finitely many exceptions, every finite non-abelian simple group has a cubic GRR; and Spiga conjectured that except for two-dimensional projective special linear groups and a finite number of other cases, every finite non-abelian simple group admits a cubic GRR with connection set containing only one involution. In 1998, Xu introduced the concept of normal Cayley graphs: A Cayley graph of a group is called normal if the right regular permutation representation of the group is normal in the full automorphism group of the graph. Xu conjectured that except for Cayley graphs of Hamiltonian 2-groups, almost all finite Cayley graphs are normal. The purpose of this thesis is to study these problems. The main work of the thesis consists of two parts, which are presented in Chapter 3 and Chapter 4 respectively. In the first part, we study cubic GRRs of some families of classical groups and, based on some previously known results, confirm the conjecture of Fang-Xia and a modified version of Spiga's conjecture. In the second part, we estimate the number of GRRs of a given finite group with large enough order and confirm the conjecture of Babai-Godsil-Imrich-Lovasz as well as the conjecture of Xu.
-
ItemViral dynamics models to explore biological mechanisms for highly pathogenic influenza viruses( 2023)Understanding biological mechanisms that cause pathogenicity for influenza viruses may help to develop and implement effective antiviral treatments and pharmaceutical interventions, reducing the economic and public health burden of influenza. In vivo viral load and immune cell data show that viral encoded proteins are associated with and contribute to viral pathogenicity. High viral loads and extensive infiltration of macrophages are the hallmarks of highly pathogenic influenza viral infections. However, it remains unclear what biological mechanisms primarily determine the kinetics of viral load and macrophages in high-pathogenic (HP) and low-pathogenic (LP) viral infections, and how the mechanistic differences are associated with viral pathogenicity. Viral dynamics models provide a powerful tool to understand viral pathogenicity, providing mechanistic explanations for experimental observations. This thesis establishes a mathematical framework that reproduces observations of viral load and macrophage kinetics during HP and LP influenza viral infections. The framework enables the exploration of the underlying biological processes underpinning high pathogenicity for influenza viruses. Following an introduction (Chapter 1) and a literature review covering biological (Chapter 2), mathematical (Chapter 3) and statistical background (Chapter 4), Chapter 5 presents a new model of virus--macrophage dynamics. The model is used to explain observed in vivo viral load and macrophage data for HP influenza viral infections. The model explicitly describes the detailed dynamics of three types of macrophages and essential interactions between macrophages and influenza viruses. Using model simulations, I identify a non-monotonic relationship between the number of macrophages and the magnitude of the viral load. Viruses with an enhanced ability to infect host target cells always lead to a higher viral load, but not necessarily to a higher number of macrophages. To further investigate the differences in biological mechanisms causing pathogenicity between HP and LP virus strains, an interferon-mediated immune response is incorporated into the virus--macrophage dynamics model. The extended model is fitted to experimental data to quantify the roles of each biological mechanism in determining viral pathogenicity. Due to a large number of parameters, a simulation-estimation study is conducted in Chapter 6 to determine if the availability of time-series data on macrophage kinetics (in addition to viral kinetic data) for model fitting improves the estimates of model parameters under a Bayesian framework. The study shows that the inclusion of macrophage data enables accurate estimation of the recruitment rate of macrophages, and inference on the timing and magnitude of macrophage activation during influenza viral infection. In contrast, with only viral kinetic data available, these quantities are not able to be recovered reliably. Having studied the importance of macrophage data for estimating parameters, I then fit the extended model to both in vivo viral load and macrophage data from mice infected with HP and LP strains of H1N1 or H5N1 viruses to estimate biological parameters that differ between HP and LP virus strains (Chapter 7). I show that HP viruses have a higher viral infection rate, a lower interferon production rate and a lower macrophage recruitment rate compared to LP viruses. These three quantities are strongly associated with more severe tissue damage (quantified by a higher percentage of epithelial cell loss). Chapter 8 presents a study of the immunological effects of the cell surface mucin, MUC1, on viral and macrophage dynamics. Two effects of MUC1 are hypothesised in the study: a reduction in target cell susceptibility to infection, and down-regulation of macrophage dynamics. I analyse in vivo kinetic data for both virus and macrophage populations in wildtype and MUC1 knockout mice using two different viral dynamics models. The models differ in how they categorise the mechanisms of viral control. Under both models, I find that MUC1 significantly reduces the basic reproduction number of viral replication as well as the number of cumulative macrophages but has little impact on the cumulative viral load. Chapter 9 provides a discussion for further research opportunities based on the PhD work.
-
ItemAGT for N=2 SU(N) gauge theories on C^2/Z_n and minimal models( 2022)Building upon a correspondence between N=2 SU(N) supersymmetric (SUSY) gauge theories on C^2 and A_{N-1}-Toda conformal field theories (CFTs) known as AGT-W, we study a conjectured correspondence for N=2 SU(N) gauge theories on the ALE space C^2/Z_n, which we refer to as coset AGT. In this case, the dual CFT is a combined system whose symmetry algebra has 3 factors: A free boson, an sl(n)_N-Wess-Zumino-Witten (WZW) model, and what is known as an n-th W_N-parafermion model. We specialize this last factor to its minimal models and show that, in this case, both sides of the duality have interesting combinatorics defined in terms of Young diagrams which are coloured. For the SUSY gauge theories AGT dual to these minimal models, we show that the usual definition of their fundamental object to this conjecture, known as Nekrasov's instanton partition function, is ill-defined and has non-physical poles. We remove these poles by a redefinition of this instanton partition function, encoded by combinatorial conditions known as the Burge conditions. We use these combinatorial conditions to check our proposal against well-known results for the CFT characters and conformal blocks of sl(n)_N-WZW models. Having checked our dictionary, we then obtain new conjectural combinatorial expressions for coset branching functions and affine sl(N)_n characters. As a corollary to these, we also obtain new combinatorial relationships between certain pairs of what is known as coloured cylindric partitions. We finish by checking our conjectured combinatorial expressions through explicit computations to a given order.
-
ItemStatistical Models For Spatio-temporal Data Forecasting( 2022)Spatio-temporal data modelling and forecasting are challenging for their spatial and temporal dependence. We proposed three statistical models to tackle Spatio-temporal forecasting problems. Specifically, they are spatial auto-regression co-integration models (SARC), spatial dynamic model (SDM) and explainable spatio-temporal forecasting model (ESTF). First, the SARC model is presented in Chapter 2 to analyze spatial dependence and temporal non-stationarity. The spatial auto-regression model aims to analyze spatial dependence via spatial weight matrix, while error terms in the spatial auto-regression model contain non-stationarity. Thus co-integration can model the temporal dependence. The residual series in the co-integration model is expected to be stationary and thus, functional principal component analysis is applied to make forecasts on these residuals by assuming they follow past patterns. In Chapter 3, the underlying spatio-temporal process is assumed to be decomposed into two components, deterministic trend and stochastic. We model the spatio-tempoal process using differential equations by considering spatial dependence. The solutions to the differential equations can be used to make forecasts and indicate how the system will evolve in the future. The stochastic components are modelled by stochastic differential equations and forecasted by corresponding numerical solutions. Therefore we propose spatial dynamic model with stochastic differential equation analysis. Both SARC model and SDM model use spatial weight matrix to reflect spatial connection and the third model, named ESTF model, extends the limitation. Finally, the ESTF model combines a statistical model with machine learning techniques to achieve high performance and explainability. We apply these models to landslide and air quality data.
-
ItemA shape theorem for the half-orthant model and the features of its shape( 2022)We study degenerate random environments which are site-based models of random media involving a parameter p in [0,1]. We are focused on a particular case, the half-orthant model, and will prove a shape theorem for this model when pp_c(2), which is not addressed in this thesis. At last, we prove the general case when p
-
ItemScheduling in Queueing Systems( 2022)The optimal control of arrivals to a service system is an area of research with applications in many industries, for example, manufacturing systems, call centres, hospitals, retail and computer systems. Scheduling is a well-known solution to the problem of controlling arrivals, and a proper scheduling approach can hugely increase a system's efficiency. There are two scheduling approaches: static scheduling and dynamic scheduling. Static scheduling also known as offline scheduling, is where we derive the optimum schedule to achieve desired objectives before starting the service period. On the other hand, dynamic scheduling, also known as online scheduling, considers uncertainties between two consecutive arrivals when deciding the next arrival time. The objectives change from system to system. For example, a surgeon whose time is expensive may prioritise minimising his expected idle time, while nurses at a donor centre may prioritise customers' expected waiting times. In this thesis, we derive static scheduling models for different queueing systems. We start with a simple single server queueing system with stochastic service times and extend the system to a multi-server system. Our objectives are to minimise a linear combination of customers' total expected waiting cost and the server's total expected idle cost. Our primary aim in this thesis is analysing systems that accept both scheduled and randomly arriving customers. Many real-world scenarios such as medical clinics, barbershops, motor mechanics and restaurants accept randomly arriving customers and customers by appointment. However, the problem of scheduling customers in an environment where random arrivals occur has not been addressed widely. We consider a complicated system with added uncertainty brought by randomly arriving customers on top of the uncertainty of stochastic service times. The objective of this problem is to determine the optimum schedule for $N$ customers so that the total expected cost of customers' waiting and that of the server being idle is minimised, whilst the system's expected revenue is maximised. We also consider different systems by changing objectives. Simply stated, this thesis gives an in-depth discussion on the static scheduling approach for determining optimum schedules in different queueing systems.
-
ItemStochastic Matching Models( 2022)Stochastic Matching Models are buffer queues that track and match items which are submitted over time. Items are matched based on their compatibility with other items which are present in the buffer. In the presence of multiple suitable matches, the match is chosen based on some predetermined priority discipline. After finding a match, the item and its pair will depart the system. Stochastic matching models are stochastic in the sense that the ‘type’ and ‘arrival pattern’ of items into the system over time is governed by some stochastic process. Whilst this process can be very general, throughout this work we will take it to be a marked Poisson process over some space of items’ types and compatibilities. We will formalise what this space will be in the context of the different models we will consider. Depending on these settings, stochastic matching models can describe a diverse range of phenomena in business, healthcare or economics. A few such examples are the double auctions underlying stock markets or organ donation registers. In this work, we will review some emerging results concerning First Come First Served priority matching models and their equilibrium behaviour. We will develop the notion of benevolent arrivals and extend the results for matching models to models which also contain these types of arrivals. Benevolent arrivals are items which match compatible items that are already in the buffer queue; however, they will otherwise depart unmatched and not join the buffer to wait for a later compatible arrival with which they can match. In addition, we will explore how a novel reversibility argument, first proposed by Adan, Busic, Mairesse and Weiss (2018), can be used to find tractable performance measures for First Come First Served priority systems. We will then explain how these could be used to optimise performance by, for instance, minimising expected congestion. We will also review results on double auctions; stochastic matching models with an ordered priority discipline. We will then study the behaviour of double auctions with the First Come First Served priority discipline. This is done in order to shine some light on the similarities and difference which may arise by altering the priority discipline and using the better understood First Come First Served priority.
-
ItemA novel SNP heritability model for heritability analyses and genomic prediction( 2022)The SNP heritability model refers to a statistical model parameterising the variance of SNP effect sizes. Most SNP heritability analyses to date assume a 1-parameter model that assigns the same variance to each SNP, which is unrealistic and has led to sub-optimal modelling of the genetic architecture and inaccurate estimates. Recent works have incorporated additional parameters to incorporate properties of SNPs such as the minor allele fraction (MAF), local LD patterns, and functional knowledge into the model to better capture heritability. This has led to the development of models such as the LDAK model, the Baseline LD model, and recently the BLD-LDAK model. The BLDLDAK heritability model is a complex (66 df) model containing highly correlated sets of predictors. My thesis is focused on exploring and testing existing and new predictors of SNP heritability and combining these to build a parsimonious heritability model, and compare its performance with the BLD-LDAK model. I start by evaluating the BLD-LDAK heritability model using data from the UK Biobank project over 14 traits and provide updated results of SNP heritability and functional enrichment analyses. In the next step, I collect a comprehensive set of functional annotations that might be predictive of heritability from public databases and subject them to systematic variable selection to construct a new 10-parameter BIC10 heritability model. I then perform heritability analyses of traits recorded in the UK Biobank project to compare models. I also compare heritability models based on phenotype prediction accuracy across a range of diverse traits from the UK Biobank and assess the portability of heritability models across human ancestries. I show that the BIC10 and BLD-LDAK heritability models have equivalent performance, however, the BIC10 model has 56 fewer parameters. The fewer degrees of freedom provide better interpretability and computational advantages for heritability analysis without loss of accuracy.
-
ItemDeformation quantisation and Airy structures( 2022)Following the work of Kontsevich and Soibelman, we study Airy structures and the relation to an algorithm known as topological recursion, which solves interesting enumerative problems. Airy structures encode the data of a Lagrangian subvariety in an infinite dimensional symplectic vector space. First, with examples, we examine the deformation quantisation of the structure sheaf of a Lagrangian sub-variety. Deformation quantisation is an algorithm that replaces a commutative algebra with a non-commutative algebra. Looking for modules over these non-commutative rings, leads to objects called wavefunctions. Wavefunctions are generators for particular cyclic modules. With some choice of initial conditions, wavefunctions encode the data of topological recursion. Next we examine how these wavefunctions behave under symplectic reduction. In particular we give an example of a particular integral formula involving wavefunctions. Finally we put these discussions into a bigger context. The infinite dimensional symplectic space required to explicitly produce the topological recursion invariants is a space of differentials over a curve in a surface. Symplectic reduction relates this to a deformation space of curves over this surface. A new interesting consequence is that some data from the Airy structure defines the variation of the period matrix, the so called Donagi-markman cubic, generalising a result of Baraglia and Huang.