权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Random walks on random graphs in critical regimes

关键状态下随机图上的随机游走

基本信息

批准号：
EP/K029657/1
负责人：
David Croydon
金额：
$ 12.42万
依托单位：
University of Warwick
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2013
资助国家：
英国
起止时间：
2013 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FK029657%2F1
关键词：
Random walks random graphs critical

项目摘要

Random walks on random graphs have in recent decades been studied from a number of different perspectives. Many of these have arisen in the physical sciences or computer science, where a suitably representative random walk on a random graph can offer an insight into the transport properties of a disordered medium or a complex network. The models proposed to understand these systems are often simple to define mathematically, but nonetheless have, in several particularly important cases, been shown to lead to a rich array of behaviour, which is sometimes rather counterintuitive. Although the situation in some of these fundamental examples is becoming increasingly well understood, the random walks on the random graphs in question continue to present deep challenges for mathematicians. This is particularly the case for random walks on random graphs in critical regimes, where a 'fractal' structure often makes the objects that arise difficult to analyse. The proposed research aims to tackle a number of key problems in this area. To begin with, in studying the dynamical properties of random graphs, there is a particular focus at the moment on determining the effect of an external field, that is, a bias that makes a random walk on the graph more likely to jump in a particular direction on each step. Indeed, some notable results have been proved in this area. For instance, it has been shown for certain supercritical models that the dead-ends of the random environment create traps which become stronger as the bias is increased, so that when the bias is set above a certain critical value, the speed of the biased random walk is zero. This is a striking contrast to the case of a random walk on a regular lattice, where it is easily shown that the speed increases monotonically with the bias strength. In critical regimes, one would expect more extreme trapping behaviour - not only because the dead-ends are typically larger, but also because the asymptotic shapes of the sparse paths in the graph will themselves have an impact on the rate of escape of a biased random walk. Describing these effects will be the first aim of this project.Secondly, a natural property of a random walk on a finite graph to study is its cover time, that is, the number of steps it takes until the random walk has visited every vertex of the graph. As well as being a focus of attention for probabilists and combinatorialists, this quantity is of interest to theoretical computer scientists seeking to answer such questions as: 'How long should a randomised algorithm be run until it has explored the entire state space?'. It has recently been shown that there is a precise link between the expected cover time and a mathematical structure called the 'Gaussian free field' that, for certain sequences of graphs, has given a great insight into the asymptotic growth rate of cover times. However, many critical graphs do not fall into the class of graphs where these Gaussian free field estimates will yield optimal results, including in particular the critical version of the 'Erdos-Renyi random graph', which is a fundamental building block in theories of complex networks. This project will seek to provide alternative techniques for dealing with these casesFinally, in order to further understand random walks on random graphs, it can be extremely informative to study the properties of their diffusion scaling limits. In the case when the random graph falls into a critical regime, it is routinely the case that these diffusions will have complex random fractal state-spaces, and behave anomalously - typically, sub-diffusively. The third part of this project will involve identifying 'new' types of behaviour that arise as a result of the interplay between the random processes considered and the irregularity of the media they traverse.

随机图上的随机游动在近几十年来已经从许多不同的角度进行了研究。其中许多已经出现在物理科学或计算机科学中，其中随机图上的适当代表性随机游走可以提供对无序介质或复杂网络的输运性质的洞察。为理解这些系统而提出的模型往往很容易在数学上定义，但在几个特别重要的案例中，这些模型已被证明会导致一系列丰富的行为，这有时是违反直觉的。虽然这些基本例子中的一些情况越来越好理解，但所讨论的随机图上的随机游动仍然给数学家带来了深刻的挑战。这是特别的情况下，随机游走的随机图中的关键制度，其中的“分形”结构往往使对象出现难以分析。拟议的研究旨在解决这一领域的一些关键问题。开始，在研究随机图的动力学性质时，目前特别关注的是确定外部场的影响，也就是说，使图上的随机游走更有可能在每一步中向特定方向跳跃的偏差。事实上，在这方面已经证明了一些显著的成果。例如，对于某些超临界模型，已经表明随机环境的死端会产生陷阱，这些陷阱随着偏置的增加而变得更强，因此当偏置设置为高于某个临界值时，偏置随机游走的速度为零。这是一个鲜明的对比的情况下，一个规则的晶格上的随机行走，它很容易表明，速度单调增加的偏置强度。在临界状态下，人们会期望更极端的捕获行为-不仅因为死端通常更大，而且因为图中稀疏路径的渐近形状本身会对有偏随机游动的逃逸率产生影响。描述这些效应将是本项目的首要目标。其次，要研究的有限图上的随机游动的一个自然属性是它的覆盖时间，即随机游动到达图的每个顶点所需的步数。除了成为概率学家和组合学家关注的焦点之外，这个量也是理论计算机科学家感兴趣的问题，他们试图回答这样的问题：“一个随机算法应该运行多久，直到它探索了整个状态空间？”'.它最近已被证明，有一个精确的链接之间的预期覆盖时间和数学结构称为“高斯自由场”，对于某些序列的图形，已经给了一个很大的洞察覆盖时间的渐近增长率。然而，许多临界图不属于这些高斯自由场估计将产生最佳结果的一类图，特别是包括“Erdos-Renyi随机图”的临界版本，这是复杂网络理论中的基本构建块。最后，为了进一步理解随机图上的随机游动，研究其扩散标度极限的性质可以提供非常丰富的信息。在随机图福尔斯落入临界状态的情况下，通常情况下，这些扩散将具有复杂的随机分形状态空间，并且表现出不稳定性-典型地，亚扩散性。该项目的第三部分将涉及识别“新”行为类型，这些行为类型是由于所考虑的随机过程与它们所穿越的介质的不规则性之间的相互作用而产生的。