Markov chain theory and its applications

马尔可夫链理论及其应用

• 批准号: RGPIN-2021-03775
• 负责人: Breen, Jane
• 金额: $ 1.31万
• 依托单位: University of Ontario Institute of Technology
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=765021
• 关键词: Markov; chain; theory; its; applications

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.

我对我的研究计划的长期愿景是，通过进行由实际应用驱动的基础理论研究，扩大马尔科夫链理论在工业中的应用。特别是，我将进行原创性研究，以开发和改进具有广泛应用范围的度量、算法和创新计算工具的工具包。马尔可夫链是一种数学模型，它被用来描述无数类型的动力系统，从城市道路网络中的交通行为，到分子动力学及其在药物设计中的作用。马尔可夫链被用来表示可以占据多个状态中的任何一个的系统，并且通过描述系统在状态之间的随机运动的概率转移矩阵来确定系统的行为。给出一个马尔可夫链，有许多衡量标准来确定它的“良好连接”程度。人们还希望知道每个州有多“中心”。例如：在传染病的联系网络中，连通性指标确定图表的密度(对应于疾病的快速传播)，并且为了控制传播，应从网络中移除(隔离)最中心的节点以减少连通性。我的计划的一个目标是研究连通性和中心性的度量，这些度量源于图上随机行走的动态过程。一个关键的连通性度量被称为Kemeny常量，它代表系统的全局连通性；即系统在不同状态之间平均移动的速度。对Kemeny常数的考虑是相对较新的，仍有许多有待理解。这项建议的一个目的是了解凯门尼常数的计算对转移矩阵中的误差有多敏感，以便在这些应用之一的情况下对凯门尼常数计算值的可信度进行衡量。我还计划开发比目前最先进的计算凯门尼常数更新、更有效的方法。最后一个目标是考虑有向复杂网络；即其中关系可能只是单向的网络或数据集(例如，社交网络Twitter涉及不一定是互惠的友谊连接)。有向网络历来很难分析；例如，识别和分析集群是一个非常困难的问题。基于我过去在该领域的工作，我计划开发和实现马尔可夫链理论中的新技术来解决这个问题。作为这项提议的一部分，将培训4名硕士学生、1名博士生和几名理科学生。他们将从事理论和应用研究，这将有助于促进马尔科夫链理论在广泛的工业环境中的理论理解和适用性，如车辆交通模型、数据科学和社会网络。