Grant: Discovery Grants Program - Individual

My long-term vision for my research program is to expand the use of Markov chain theory in industry by performing fundamental theoretical research that is driven by practical applications. In particular, I will undertake original research to develop and refine a toolkit of metrics, algorithms, and innovative computational tools with a wide range of applications. A Markov chain is a type of mathematical model which has been used to describe countless types of dynamical systems, from traffic behaviour in an urban road network, to molecular dynamics and their role in drug design. A Markov chain is used to represent systems which can occupy any of a number of states, and the behaviour of the system is determined via a probability transition matrix, which describes the random movement of the system between the states. Given a Markov chain, there are many metrics which determine how 'well-connected' it is. It is also desirable to know how 'central' each state is. For example: in a contact network for a communicable disease, connectivity metrics determine how dense the graph is (corresponding to fast spread of the disease) and to control the spread, the most central nodes should be removed (quarantined) from the network to reduce connectivity. One objective of my program is to research measures of connectivity and centrality that derive from the dynamical process of a random walk on a graph. One key connectivity metric is called Kemeny's constant, and it represents the global 'connectedness' of the system; i.e. how quickly the system moves between states on average. The consideration of Kemeny's constant is relatively recent, and much remains to be understood. One objective of this proposal is to provide an understanding of how sensitive the calculation of Kemeny's constant is to errors in the transition matrix, in order to give a measure of confidence in the computed value of Kemeny's constant in the context of one of these applications. I also plan to develop newer, more efficient methods of computing Kemeny's constant than the current state-of-the-art. A final objective is to consider directed complex networks; that is, networks or datasets in which the relationship may be one-way only (for example, the social network Twitter involves friendship connections which are not necessarily reciprocated). Directed networks have historically been difficult to analyse; for example, identifying and analysing clusters is a very hard problem. Based on my past work in the area, I plan to develop and implement novel techniques from Markov chain theory to solve this problem. As part of this proposal, 4 MSc students, 1 PhD student, and several BSc students will be trained. They will engage in theoretical and applied research that will contribute towards the long-term goal of advancing the theoretical understanding and applicability of Markov chain theory in a wide range of industrial settings, such as vehicle traffic models, data science, and social networks.