Thursday 3 June 2020
Chair
- Michel Mandjes – University of Amsterdam
- Viresh Patel – University of Amsterdam
- Jop Briët – Center for Mathematics and Computer Science
- Nicos Starreveld – University of Amsterdam
The theory of large deviations is a branch of probability concerning probabilities of rare events as well as understanding the behaviour of distributions conditioned on rare events. It has many applications throughout a wide range of disciplines, including statistical physics, information theory and operations research. This mini-workshop considers large deviations in the context of networks. Topics that will be covered include understanding the structures of random graphs conditioned on very high or very low subgraph counts, the breaking of ensemble equivalence in statistical physics, and the assessment of rare event in large stochastic networks.
Speakers
Pietro Caputo (keynote)
Universitá Roma Tre
Random walks on random directed networks
Abstract: Exploration via random walks is often very useful for the analysis of directed networks. For instance, the walk’s stationary distribution plays a prominent role in ranking systems and search algorithms. In this lecture, we present some recent progress in the analysis of random walks for a class of sparse directed networks generated by the so-called configuration model. We discuss various properties of the stationary distribution, including bulk behaviour and extremal values. We also consider the mixing time, that is the time needed to reach stationarity, and show that the walk typically displays a cutoff behaviour. Moreover, we obtain the asymptotic behaviour of the cover time, that is the expected time it takes the random walk to cover the whole network. Finally, we analyse the convergence to stationarity when the walk experiences regeneration events such as teleportation, as in the PageRank algorithm, or resampling of the underlying graph, as in a dynamically evolving network.
Perla Sousi
University of Cambridge
The uniform spanning tree in 4 dimensions
Abstract: A uniform spanning tree of Z^4 can be thought of as the ‘’uniform measure’’ on trees of Z^4. The past of 0 in the uniform spanning tree is the finite component that is disconnected from infinity when 0 is deleted from the tree. We establish the logarithmic corrections to the probabilities that the past contains a path of length n, that it has volume at least n and that it reaches the boundary of the box of side length n around 0. Dimension 4 is the upper critical dimension for this model in the sense that in higher dimensions it exhibits “mean-field” critical behaviour. An important part of our proof is the study of the Newtonian capacity of a loop erased random walk in 4 dimensions. This is joint work with Tom Hutchcroft.
Ayalvadi Ganesh
University of Bristol
Large deviations for Cox processes, and applications
Abstract: We show that a sequence of Cox processes on a Polish space E satisfy a large deviation principle (LDP), provided their directing measures do so on the space of finite measures on E equipped with the weak topology. Next, we consider a sequence of infinite server queue with general iid service times, where the arrivals constitute Cox processes with translation invariant directing measures assumed to satisfy an LDP. We show that the corresponding sequence of queue occupancy measures also satisfy an LDP. These questions were motivated by the problem of describing fluctuations of molecule numbers in biochemical reaction networks within cells.
Joint work with Justin Dean and Edward Crane
Diego Garlaschelli
Leiden University and IMT School of Advanced Studies, Lucca
Multiscale network renormalization: scale-invariance without geometry
Networks embedded in metric spaces can be renormalized exploiting their coordinates, which naturally define the coarse-grained nodes. By contrast, complex networks defy the usual techniques because of their small-world character and lack of explicit geometric embedding. Current network renormalization approaches require strong assumptions (e.g. community structure, hyperbolicity, scale-free topology), thus remaining incompatible with generic graphs and ordinary lattices. Here we introduce a graph renormalization scheme valid for any hierarchy of coarse-grainings, thereby allowing for the definition of `block nodes’ across multiple scales. This approach reveals a necessary and specific dependence of network topology on an additive hidden variable attached to nodes, plus possible dyadic factors. Renormalizable networks turn out to be consistent with a unique specification of the fitness model, while they are incompatible with preferential attachment, the configuration model or the stochastic blockmodel. These results highlight a deep conceptual distinction between scale-free and scale-invariant networks, and provide a geometry-free route to renormalization. If the hidden variables are annealed, the model spontaneously leads to scale-free networks with cut-off. If they are quenched, the model can be used to renormalize real-world networks with node attributes and distance-dependence or communities. As a concrete example we derive an accurate multiscale model of the International Trade Network applicable across arbitrarily defined geographic regions.
Matan Harel
Tel Aviv University
Upper tails for subgraphs of the Erdos-Renyi random graph via high moments and entropic stability
Let X_H be the number of copies of a fixed, Delta-regular subgraph H in the sparse random graph G(n,p_n), p_n –> 0. We study the large deviation regime of X_H – i.e. the probability that it exceeds its expectation by a multiplicative factor of (1+ delta). We give sharp estimates on the logarithmic large deviation probability for X_H for nearly all relevant values of p in terms of an associated variational problem. This is an application of a general method for random variables which can be expressed as a bounded-degree polynomial in the p-biased hypercube whose associated variational problem satisfy an extremal property we call “entropic stability.” In the case where H is a clique on k vertices, we can also describe the structure of G(n,p) conditioned on the rare event {X_H > (1+ delta) E[X_H]}. This is joint work with Frank Mousset and Wojcieh Samotij.