Scaling limits of critical directed random graphs

临界有向随机图的缩放限制

• 批准号: 2272117
• 金额: --
• 依托单位: University of Oxford
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2019
• 资助国家: 英国
• 起止时间: 2019 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2272117
• 关键词: Scaling; limits; critical; directed; random

Past work by Addario-Berry, Broutin and Goldschmidt has established the scaling limit of components of a critical undirected Erdos--Renyi graph to a sequence of metric spaces. These metric spaces are constructed by using tilted Brownian excursions to code real trees, then adding a finite number of point identifications. Further work has shown these limit objects exhibit universality. Work by authors Bhamidi and Sen and authors Conchon--Kerjan and Goldschmidt has established that the components of a critical configuration model (under finite moment conditions on the degree distribution) have the same scaling limit, and work by Bhamidi, Sen and Wang have shown the same is true for rank-one inhomogeneous random graphs. Real life networks, however, are usually directed. The relationships in networks like Twitter, financial transactions, the world wide web and disease transmission are all asymmetrical. Hence directed graphs provide a more realistic model of real-world networks, yet they remain relatively unstudied compared to their undirected counterparts. Luzack and Seierstad established a phase transition for the existence of a giant strongly connected component in the directed Erdos--Renyi model. In the critical regime of this phase transition, Goldschmidt and Stephenson have recently shown the strongly connected components (SCCs) can be scaled into a sequence of random weighted multi-digraphs. The goal of this research project is to show universality of these limit objects. Cooper and Frieze have shown the existence of the phase transition in the directed configuration model, and we have made progress in characterising the scaling limit of the SCCs in the critical regime. In particular with the appropriate choice of parameters, the limiting object is the same as that for the Erdos--Renyi model. We conjecture that the same will be true for certain classes of directed inhomogeneous random graphs. Extending results from the Erdos--Renyi model is important to apply these results practically. While the Erdos--Renyi model is analytically simple to work with, it is not an accurate model for real networks. For example, the degrees in real networks often exhibit a power law. This is not present in Erdos--Renyi random graphs, but the configuration model can be made to exhibit this property. Moreover, showing universality of the scaling limit means these results are less sensitive to model misspecification. The work by Conchon--Kerjan and Goldschmidt mentioned previously also looked at configuration models when the size-biased degree distribution is in the domain of attraction of a general alpha-stable Levy distribution rather than just the Gaussian distribution. This yielded a family of universality classes in a similar way to how alpha-stable Levy processes generalise Brownian motion. If successful in studying the directed configuration model with sized biased degree distributions in the domain of attraction of a Gaussian distribution, another goal of this research project would be to look at the alpha-stable case. Further there are edges between SCCs of a directed graph which we ignore when studying the scaling limit of the SCCs. This contrasts with the undirected case where all edges are included in a component. The condensation of a directed graph is a natural proxy for the edges not used in SCCs, thus another future research avenue could be studying the scaling of condensations of critical random digraphs.This project falls within the EPSRC Mathematical Analysis, Statistics and Applied Probability, and Logic and Combinatorics Research Areas. The project is supervised by Prof. Christina Goldschmidt the work is joint with Serte Donderwinkel.

Addario-Berry，Broutin和Goldschleman在过去的工作中建立了临界无向Erdos-Renyi图的分支到度量空间序列的标度极限。这些度量空间是通过使用倾斜布朗行程编码真实的树，然后添加有限个点标识来构造的。进一步的工作表明这些极限对象具有普适性。作者Bhamidi和Sen以及作者Conchon-Kerjan和Goldschleman的工作已经建立了临界配置模型的组件（在有限矩条件下的度分布）具有相同的标度极限，并且Bhamidi，Sen和Wang的工作表明对于秩1非齐次随机图也是如此。然而，真实的生活网络通常是定向的。Twitter、金融交易、万维网和疾病传播等网络中的关系都是不对称的。因此，有向图为现实世界的网络提供了一个更现实的模型，但与无向图相比，它们仍然相对未被研究。Luzack和Seierstad在有向Erdos-Renyi模型中建立了巨强连通分支存在的相变。在这种相变的临界区域，Goldschlaun和斯蒂芬森最近证明了强连通分量（SCC）可以被标度为随机加权多重有向图的序列。这个研究项目的目标是展示这些极限对象的普遍性。库珀和Frieze在定向组态模型中证明了相变的存在，我们在临界区标度极限的表征方面也取得了进展。特别是在适当选择参数的情况下，其极限对象与Erdos-Renyi模型的极限对象相同。我们猜想，这将是真实的某些类别的有向非齐次随机图。对Erdos-Renyi模型的结果进行了推广，这对这些结果的实际应用具有重要意义.虽然Erdos-Renyi模型在分析上很容易使用，但它并不是真实的网络的精确模型。例如，真实的网络中的度通常呈现幂律。这在Erdos-Renyi随机图中是不存在的，但是可以使构形模型表现出这一性质。此外，标度极限的普遍性意味着这些结果对模型误设定不太敏感。前面提到的Conchon-Kerjan和Goldschmidt的工作也研究了当尺寸偏置度分布处于一般α稳定Levy分布的吸引域而不仅仅是高斯分布时的配置模型。这产生了一个家庭的普适性类以类似的方式如何阿尔法稳定列维进程推广布朗运动。如果在高斯分布的吸引域中成功地研究了具有大小偏置度分布的有向配置模型，则本研究项目的另一个目标是研究α稳定的情况。此外，有向图的SCC之间的边，我们忽略了研究SCC的缩放限制。这与所有边都包含在一个分量中的无向情况形成对比。有向图的凝聚是SCC中未使用的边的自然代理，因此另一个未来的研究途径可能是研究临界随机有向图的凝聚的缩放。这个项目福尔斯属于EPSRC数学分析，统计和应用概率，逻辑和组合学研究领域。该项目是由克里斯蒂娜Goldschelter教授监督的工作是与Serte Donderwinkel联合。