Stochastic processes on random graphs with clustering

具有聚类的随机图上的随机过程

• 批准号: EP/W033585/1
• 负责人: Minmin Wang
• 金额: $ 32.4万
• 依托单位: University of Sussex
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2023
• 资助国家: 英国
• 起止时间: 2023 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FW033585%2F1
• 关键词: Stochastic; processes; random; graphs; clustering

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.

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