Large deviation properties of random graphs and other random models

Alexander Hartmann,  Institut für Physik, Oldenburg University, Germany


When describing random objects or statistical processes, within analytical and numerical simulations one often just studies the behavior of means or variances. Nevertheless, as for any random process, a complete description is only given if the full distribution of the measurable quantity is available. In this talk sophisticated
large-deviation algorithms are described which allow to obtain the distributions of properties of equilibrium and non-equilibrium processes. Probabilities as small as 10^-180 can be accessed using an artificial finitetemperature (Boltzmann) ensemble.
Results from this approach are first shown for various properties of random graphs, in particular Erdoes-Renyi random graphs. First, distributions of the size of the largest component, in particular the large-deviation tail, are studied. The distributions for the Erdoes-Renyi ensemble agree well with previously obtained analytical results.
Next, the distribution of the size of the 2-core is shown. Third, the distributions of the diameter are presented.
Here, partial analytic results are available from previous studies for Erdoes-Renyi random graphs in the small connectivity region. The numerical results follow a Gumbel distribution and agree well with the analytics. For higher connectivities, where no analytic results are available, the simulation results show that the
distributions are qualitatively different from the low-connectivity region.
Finally, it is outlined how the approach can be used in general for various problems. Examples which are given here include the distribution of endpoints of Fractional Brownian motion, the distribution of convex hulls for random walks, the distribution of heights of the Kardar-Parisi-Zhang equation, and the distribution of work for an Ising model in non-equilibrium.