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.