Random graph structures and their scaling limits

图是网络的数学模型。它由一组节点组成，其中一些节点由边链接。在许多应用领域中，例如在为互联网或社交网络建模时，很自然地会认为图表是随机生成的。最简单的模型是Erdos-Renyi随机图(ERRG)，其中有n个结点，每对结点由概率为p的一条边直接相连，否则，对于不同的结点对，不同的结点对是相互独立的。(如果存在一条通过其他节点的链接路径，我们可以使用链接路径从一个节点到达另一个节点，那么我们仍然能够在两个不直接链接的节点之间传输；在这种情况下，我们说这两个节点位于图形的同一组件中。)这个模型的许多吸引人的特征之一是它经历了相变，这是参数p的值发生微小变化时的数量行为的巨大变化。(相变这个术语借用自物理学，在物理学中用来描述物理系统中的这种突然变化，例如，水在0度和100度时分别变成冰或蒸汽。)在ERRG中，相变与分量大小有关，在p的临界值以下相对较小，而在其上方有一个巨大的分量(包含正比例的节点)，所有其他分量又都很小。最微妙的行为恰好发生在这个临界点，这里有一个中等大小的缩放和许多大小相当的组件。人们很自然地会问，随着节点数量的增加，图形会发生什么。如果我们同时收缩边的长度，那么图就有可能收敛。这是比例限制的概念；它告诉我们有关组件的宏观结构的信息。在早期的工作中，我和我的合著者能够准确地描述关键ERRG中组件的比例限制。据推测，这一比例限制对于范围广泛的高维临界随机图模型应该是相同的，这些模型是通过从某个基图开始，然后执行随机攻击而获得的，在该随机攻击中，随机选择的某一比例的边被变为不活动的(这被称为逾渗)。证明这是我的目标之一。有许多随机图模型的行为与ER的情况略有不同，而且它们可能的比例限制通常更难理解；我也将研究这些模型。另一种不太发达的设置，即图形的边被定向，使它们从一个节点指向另一个节点。这是对万维网建模的自然方式，其中链接从一个网页指向另一个网页，这将形成我的项目的另一个焦点。树是一个只有一个组件并且没有循环的图形。树的应用范围很广，从模拟种群的系谱到理解数据结构。随机树及其比例限制目前是一个密集研究的主题，它们构成了我的项目的关键部分。这里有太多不同的模式出现在不同的环境中。经典优化问题的一个例子是所谓的最小生成树(MST)。在任何连通图中，都有(通常是几种可能的)生成树，它们代表了用最少的边数连接节点的不同方式。如果每条边都有一个与其使用相关的(潜在随机的)成本，并且我们仍然希望连接所有的顶点，那么我们感兴趣的是寻找图的MST。事实证明，这与我们简单地随机选择一棵生成树的情况有惊人的不同。我的目标之一是探索这类树中可能的行为范围。

A graph is a mathematical model for a network. It consists of a collection of nodes, some of which are linked by edges. In many application areas, for example in modelling the Internet or a social network, it is natural to think of the graph as generated randomly. My proposed research is about models of random graphs and, in particular, what we may say about large instances of them.The simplest model is the Erdos-Renyi random graph (ERRG) in which there are n nodes, each pair of which is directly linked by an edge with probability p and not linked otherwise, independently for different pairs of nodes. (We may still be able to travel between two nodes which are not directly linked if there is a path of links leading through other nodes which we may use to get from one to the other; in this case, we say that the two nodes are in the same component of the graph.) One of the many fascinating features of this model is that it undergoes a phase transition, that is a huge change in quantitative behaviour for a small change in the value of the parameter p. (The term phase transition is borrowed from physics, where it is used to describe such sudden changes in physical systems, e.g. water turning into ice or vapour at 0 and 100 degrees respectively.) In the ERRG, the phase transition concerns the component sizes, which are relatively small below the critical value of p, whereas above it, there is one giant component (containing a positive proportion of the nodes) and all of the other components are again small. The most delicate behaviour occurs exactly at this critical point, where there is an intermediate size-scaling and many components of comparable size.It is natural to ask what happens to the graph as the number of nodes grows. If we simultaneously shrink the lengths of the edges then it is possible that the graph converges. This is the idea of a scaling limit; it tells us information about the macroscopic structure of the components. In earlier work, my co-authors and I were able to give a precise description of the scaling limit of the components in the critical ERRG. It is conjectured that this scaling limit should be the same for a wide range of "high-dimensional" critical random graph models which are obtained by starting from some base graph and then performing a random attack in which some proportion of the edges, chosen at random, are rendered inactive (this is known as percolation). Proving this is one of my aims.There are many random graph models which behave appreciably differently to the ER case, and their possible scaling limits are typically much more poorly understood; I will investigate these also. Another setting which is much less developed and is where the edges of the graph are directed, so that they point from one node to another. This is the natural way to model the World-Wide Web, where links point from one webpage to another, and will form another focus of my project.A tree is a graph which has a single component and no cycles. Trees have applications which range from modelling the genealogy of populations through to understanding data structures. Random trees and their scaling limits are currently a topic of intense study, and they form a key part of my project. There is a plethora of different models here arising in a variety of settings. An example which is motivated by a classical optimisation problem is the so-called minimum spanning tree (MST). Inside any connected graph, there are (usually several possible) spanning trees, which represent different ways to connect up the nodes using the smallest number of edges. If each edge has a (potentially random) cost associated for its use, and we still wish to connect all the vertices, then we are interested in finding the MST of the graph. This turns out to behave surprisingly differently to the case where we simply pick a spanning tree uniformly at random. One of my goals is to explore the range of possible behaviours in such trees.