Scaling limits of critical directed random graphs

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.

Probabilistic modelling permeates the Financial services, healthcare, technology and other Service industries crucial to the UK's continuing social and economic prosperity, which are major users of stochastic algorithms for data analysis, simulation, systems design and optimisation. There is a major and growing skills shortage of experts in this area, and the success of the UK in addressing this shortage in cross-disciplinary research and industry expertise in computing, analytics and finance will directly impact the international competitiveness of UK companies and the quality of services delivered by government institutions.
By training highly skilled experts equipped to build, analyse and deploy probabilistic models, the CDT in Mathematics of Random Systems will contribute to
- sharpening the UK's research lead in this area and
- meeting the needs of industry across the technology, finance, government and healthcare sectors

MATHEMATICS, THEORETICAL PHYSICS and MATHEMATICAL BIOLOGY

The explosion of novel research areas in stochastic analysis requires the training of young researchers capable of facing the new scientific challenges and maintaining the UK's lead in this area. The partners are at the forefront of many recent developments and ideally positioned to successfully train the next generation of UK scientists for tackling these exciting challenges.
The theory of regularity structures, pioneered by Hairer (Imperial), has generated a ground-breaking approach to singular stochastic partial differential equations (SPDEs) and opened the way to solve longstanding problems in physics of random interface growth and quantum field theory, spearheaded by Hairer's group at Imperial. The theory of rough paths, initiated by TJ Lyons (Oxford), is undergoing a renewal spurred by applications in Data Science and systems control, led by the Oxford group in conjunction with Cass (Imperial). Pathwise methods and infinite dimensional methods in stochastic analysis with applications to robust modelling in finance and control have been developed by both groups.
Applications of probabilistic modelling in population genetics, mathematical ecology and precision healthcare, are active areas in which our groups have recognized expertise.

FINANCIAL SERVICES and GOVERNMENT

The large-scale computerisation of financial markets and retail finance and the advent of massive financial data sets are radically changing the landscape of financial services, requiring new profiles of experts with strong analytical and computing skills as well as familiarity with Big Data analysis and data-driven modelling, not matched by current MSc and PhD programs. Financial regulators (Bank of England, FCA, ECB) are investing in analytics and modelling to face this challenge. We will develop a novel training and research agenda adapted to these needs by leveraging the considerable expertise of our teams in quantitative modelling in finance and our extensive experience in partnerships with the financial institutions and regulators.

DATA SCIENCE:

Probabilistic algorithms, such as Stochastic gradient descent and Monte Carlo Tree Search, underlie the impressive achievements of Deep Learning methods. Stochastic control provides the theoretical framework for understanding and designing Reinforcement Learning algorithms. Deeper understanding of these algorithms can pave the way to designing improved algorithms with higher predictability and 'explainable' results, crucial for applications.
We will train experts who can blend a deeper understanding of algorithms with knowledge of the application at hand to go beyond pure data analysis and develop data-driven models and decision aid tools
There is a high demand for such expertise in technology, healthcare and finance sectors and great enthusiasm from our industry partners. Knowledge transfer will be enhanced through internships, co-funded studentships and paths to entrepreneurs