Markov Chains and Spectral Graph Theory: Interactions and Applications

马尔可夫链和谱图论：相互作用和应用

• 批准号: RGPIN-2014-06123
• 负责人: Kirkland, Stephen
• 金额: $ 1.31万
• 依托单位: University of Manitoba
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=612046
• 关键词: Markov; Chains; Spectral; Graph; Theory

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.

马尔可夫链是一种特定类型的概率模型，这些模型在科学和工程中无处不在，在计算药物设计、车辆交通网络和网页排名等不同领域都有应用。Kemeny常数是与马尔可夫链相关的一个关键量，它在某种意义上提供了马尔可夫链整体短期效率的全局度量。尽管凯梅尼常数是50多年前提出的，但人们对它的了解相对较少，拟议的研究计划将对该常数进行彻底的调查。通过阐明Kemeny常数的数学性质，我希望为具有理想效率性质的马尔可夫链的设计提供见解。