Thursday 11 June

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

Universality of cutoff for quasi random graphs

Abstract: We add a random matching to a bounded degree graph and consider a simple random walk on the resulting graph. We prove that the walk exhibits cutoff with high probability. This is joint work with Jonathan Hermon and Allan Sly.

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.