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.