Grant: Discovery Grants Program - Individual
University of Manitoba
$18,000.00
Markov Chains and Spectral Graph Theory: Interactions and Applications
FY 2017-18
Summary
A Markov chain is a certain type of probabilistic model, and these models are ubiquitous in science and engineering, finding applications in such diverse areas as computational drug design, vehicle traffic networks, and ranking of web pages. The Kemeny constant is a key quantity associated with a Markov chain, and it provides, in some sense, a global measure of the overall short term efficiency of the Markov chain. Despite having been introduced more than 50 years ago, relatively little is known about the Kemeny constant, and the proposed research programme will undertake a thorough investigation of that quantity. By illuminating the mathematical properties of the Kemeny constant, I hope to provide insights into the design of Markov chains with desirable efficiency properties. A graph (or network) is a mathematical structure that records information about objects (called vertices) that are related in some way. Examples include Facebook users that are related by 'friendship', proteins in a cell that perform some function together, and terminals in an electrical network that are connected by resistors. There is a natural way to associate a Markov chain with any graph, and it turns out that certain parameters of the Markov chain can be used to measure how central each vertex is in the graph. This Markov chain centrality has been investigated empirically, but at present there is little in the way of rigorous theory on the topic. The proposed programme of research will develop the mathematical theory of this Markov chain centrality, thus enhancing the understanding of the graph-theoretic properties that are reflected by that centrality, and informing the use of that centrality in practical applications. The notion of a quantum walk arises in a so-called quantum wire -- a model for information transport inside a quantum computer. The fidelity of a quantum walk measures the probability that the information is transferred correctly along the quantum wire. This research programme will also investigate the sensitivity of the fidelity in terms of the time taken for the information to transfer, and the physical parameters associated with the quantum wire. The results will help to inform the design and implementation of quantum walks. This programme of research is expected to have impact in several different domains. Researchers working on Markov chains from the theoretical side, as well as scientists and engineers applying Markov chain techniques in practical settings (such as traffic modelling, migration models and network analysis) will benefit from the research on the Kemeny constant, as that quantity will become more deeply understood, and will hence be a more useful tool. The research on Markov chain centrality will, by developing the mathematical theory of that centrality, have an impact on network science and its numerous applications. Finally the research on quantum walks will have an impact in the area of quantum computing.
Program
Discovery Grants Program - Individual
Recipient
Location
Manitoba, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2014-06123
Name nom
Kirkland, Stephen
Department département
Mathematics
Organization id
19
Institution établissement
University of Manitoba
Province en
Manitoba
Province fr
Manitoba
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2014
Award amount
18000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2908
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Algebra
Research subject fr
algèbre
Partie
4
Nb partie
5
Application title
Markov Chains and Spectral Graph Theory: Interactions and Applications
Keyword
NSERC
Application summary
A Markov chain is a certain type of probabilistic model, and these models are ubiquitous in science and engineering, finding applications in such diverse areas as computational drug design, vehicle traffic networks, and ranking of web pages. The Kemeny constant is a key quantity associated with a Markov chain, and it provides, in some sense, a global measure of the overall short term efficiency of the Markov chain. Despite having been introduced more than 50 years ago, relatively little is known about the Kemeny constant, and the proposed research programme will undertake a thorough investigation of that quantity. By illuminating the mathematical properties of the Kemeny constant, I hope to provide insights into the design of Markov chains with desirable efficiency properties. A graph (or network) is a mathematical structure that records information about objects (called vertices) that are related in some way. Examples include Facebook users that are related by 'friendship', proteins in a cell that perform some function together, and terminals in an electrical network that are connected by resistors. There is a natural way to associate a Markov chain with any graph, and it turns out that certain parameters of the Markov chain can be used to measure how central each vertex is in the graph. This Markov chain centrality has been investigated empirically, but at present there is little in the way of rigorous theory on the topic. The proposed programme of research will develop the mathematical theory of this Markov chain centrality, thus enhancing the understanding of the graph-theoretic properties that are reflected by that centrality, and informing the use of that centrality in practical applications. The notion of a quantum walk arises in a so-called quantum wire -- a model for information transport inside a quantum computer. The fidelity of a quantum walk measures the probability that the information is transferred correctly along the quantum wire. This research programme will also investigate the sensitivity of the fidelity in terms of the time taken for the information to transfer, and the physical parameters associated with the quantum wire. The results will help to inform the design and implementation of quantum walks. This programme of research is expected to have impact in several different domains. Researchers working on Markov chains from the theoretical side, as well as scientists and engineers applying Markov chain techniques in practical settings (such as traffic modelling, migration models and network analysis) will benefit from the research on the Kemeny constant, as that quantity will become more deeply understood, and will hence be a more useful tool. The research on Markov chain centrality will, by developing the mathematical theory of that centrality, have an impact on network science and its numerous applications. Finally the research on quantum walks will have an impact in the area of quantum computing.