Markov Chains and Spectral Graph Theory: Interactions and Applications

马尔可夫链是一种概率模型，这些模型在科学和工程中无处不在，在计算药物设计、车辆交通网络和网页排序等领域都有应用。Kemeny常数是与马尔可夫链相关的一个关键量，在某种意义上，它提供了马尔可夫链整体短期效率的全局衡量标准。尽管在50多年前就被引入，但人们对凯门尼常数的了解相对较少，拟议的研究方案将对这一数量进行彻底调查。通过阐明Kemeny常数的数学性质，我希望为设计具有理想效率性质的马尔可夫链提供一些见解。 图(或网络)是一种数学结构，它记录了以某种方式相关的对象(称为顶点)的信息。这些例子包括通过“友谊”联系在一起的Facebook用户，一起执行某些功能的细胞中的蛋白质，以及通过电阻连接的电子网络中的终端。有一种自然的方法将马尔可夫链与任何图相关联，事实证明，马尔可夫链的某些参数可以用来衡量每个顶点在图中的中心程度。这种马尔可夫链中心性已经得到了实证研究，但目前关于这一主题的严谨理论还很少。拟议的研究方案将发展这种马尔科夫链中心性的数学理论，从而加强对这种中心性所反映的图论性质的理解，并告知在实际应用中对这种中心性的使用。 量子行走的概念产生于所谓的量子线--一种量子计算机内部信息传输的模型。量子行走的保真度衡量的是信息沿着量子线正确传输的概率。这项研究计划还将调查保真度对信息传输所需时间的敏感性，以及与量子线相关的物理参数。这一结果将有助于量子行走的设计和实现。 这一研究方案预计将在几个不同领域产生影响。从理论上研究马尔可夫链的研究人员，以及在实际环境中应用马尔可夫链技术(如流量建模、迁移模型和网络分析)的科学家和工程师，将从凯门尼常数的研究中受益，因为这个量将变得更深入地理解，因此将成为更有用的工具。马尔可夫链中心性的研究将通过发展该中心性的数学理论，对网络科学及其众多应用产生影响。最后，对量子行走的研究将在量子计算领域产生影响。

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.