Scaling limits of critical directed random graphs

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

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.