Spectra of Random Networks

Complex networks are often modelled as random graphs subject to certain constraints, e.g. on the number of edges and triangles or on the degree sequence. Statistical physics prescribes what probability distribution on the set of possible graphs should be chosen given a particular type of constraint. Two important choices are the microcanonical ensemble (where the constraints are hard) and the canonical ensemble (where the constraints are soft, i.e., hold as ensemble averages only). For random graphs that are large but finite, the two ensembles are obviously different and, in fact, represent different empirical situations. As the size of the graph gets large, the two ensembles are traditionally assumed to become equivalent, i.e., the soft constraints are expected to behave asymptotically like hard constraints. This assumption of ensemble equivalence is one of the corner stones of statistical physics, but it does not hold in general. 

The goal of the project is to identify what effect breaking of ensemble equivalence has on the probability distribution of the largest eigenvalue of the adjacency matrix of the network, and related quantities. Both spare and dense networks are of interest. It is also interesting to investigate what happens when the network is dynamic.

The project lies at the interface between probability theory, combinatorics and statistical physics. Mathematical tools come from information theory, large deviation theory and the theory of graphons.