Random graph structures and their scaling limits

点击翻译按钮获取中文摘要

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.