Stochastic processes on random graphs with clustering

随机图是研究复杂网络特性的数学工具，这些网络在我们的日常生活中无处不在（社交网络、互联网、万维网等）。以社交网络为例，它们的几何结构有两个共同特征：异质性和集群性。前者是指存在少数高度连接的节点（即“影响者”），后者通常用来解释我朋友的朋友也是我的朋友的现象。近年来，人们对共享真实网络特征的随机图模型越来越感兴趣，并特别关注异质性对网络的影响。与异质性相比，在数学上严格的聚类研究相对较少，而提出的研究计划的目的是提供一个这样的研究。研究的主要对象，即所谓的随机相交图模型，有一个简单而灵活的机制来产生聚类。通过在不同聚类机制下对这些图进行并行研究，并通过比较这些研究的结果，该程序可以产生令人信服的证据，证明聚类影响网络的各种属性。更准确地说，将要研究的研究问题涉及到网络的以下几个方面：1)当图的大小增加到无穷大时的宏观结构。2)图上某些动态过程（渗透过程和接触过程）的大时间行为。与许多其他随机图模型一样，随机交点图随着其边缘密度的增加，其分量大小也会发生剧烈的变化。这种现象通常被称为相变。如果我们取一个越来越大的随机相交图的序列，每个都冻结在相变的精确点上，我们预计会看到有趣的行为出现。该计划的第一部分旨在详细描述这些图的宏观结构，依靠“缩小”过程，大致如下。当图越来越大时，我们以适当的方式缩小图的边缘长度，使图的变化模式稳定下来，出现一个“极限对象”。通过确定合适的边缘长度尺度和极限对象，我们将能够获得关于图序列本身的有价值的信息。在课程的第二部分，我们将研究随机交集图的特定结构如何影响在其上运行的两个随机过程，即渗透过程和接触过程。渗透过程与上述相变有关。通过观察这个过程，我们将能够辨别图形中的组件彼此合并并形成一个巨大组件的模式。接触过程是另一种经典的概率模型，已被用来模拟计算机病毒在网络上的传播。对于这两个过程，我们期望在图的不同聚类机制中看到不同的行为。该方案的目的是确认这一期望，并详细描述每种制度下这些过程的长期行为。

Random graphs are mathematical tools for studying the properties of the complex networks that are ubiquitous in our everyday life (social networks, the Internet, the World Wide Web, among others). In the case of social networks, two common features about their geometries stand out: heterogeneity and clustering. The former refers to the presence of a small number of highly connected nodes (i.e. the "influencers"), and the latter is often used to explain the phenomenon that friends of my friends are also my friends. Recent years have witnessed growing interests on random graph models that share real-world network features and particular attention has been paid to the impact of heterogeneity on the networks. Compared with heterogeneity, mathematically rigorous studies on clustering have been relatively few, and it is the aim of the proposed research programme to provide one such study. The main object under scrutiny, the so-called model of random intersection graphs, has a simple yet flexible mechanism to produce clustering. By conducting parallel studies on these graphs in different clustering regimes and by comparing the results from these studies, the programme can produce convincing evidence that clustering impacts various properties of the networks. More precisely, the research questions that will be studied pertain to the following aspects of the networks:1) Macroscopic structures as the graph size increases to infinity. 2) Large-time behaviours of certain dynamic processes (percolation and contact process) on the graphs. Like many other random graph models, the random intersection graph experiences a drastic change in the component sizes as its edge density increases. This phenomenon is often referred to as a phase transition. If we take a sequence of increasingly large random intersection graph, each frozen at the precise point of the phase transition, it is expected that we will see interesting behaviours emerge. The first part of the programme aims to give a detailed description on the macroscopic structures of these graphs, relying upon a "zooming-out" procedure that runs roughly as follows. As the graphs grow larger and larger, we shrink the edge lengths therein in a suitable way so that the changing pattern of the graphs stabilises and a "limit object" appears. By identifying the suitable scale of edge lengths and the limit object, we will be able to gain valuable information on the sequence of graphs itself. In the second part of the programme, we will look at how the particular structures of the random intersection graphs influence the two stochastic processes, percolation and contact process, running on them. The percolation process is connected to the aforementioned phase transition. By looking at this process, we will be able to discern the patten in which the components in the graphs merge with each other and form a giant component. Contact process is another classical probabilistic model and has been used to model the spread of computer virus on a network. For both processes, we expect to see distinct behaviours in the different clustering regimes of the graphs. It is the aim of the programme to confirm this expectation as well as to give a detailed description on the large-time behaviours of these processes in each regime.