Séminaire ICI : Alexander Hartmann

Titre du séminaire et orateur

Large deviation properties of random graphs.

Alexander Hartmann, Institute of Physics, University of Oldenburg, Germany.

Date et lieu

Mercredi 31 mai 2017, 14h.

ENSEA, salle 384.


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. Here sophisticated large-deviation algorithms are used to obtain the distributions of properties of ensembles of random graphs. Probabilities as small as 10^-180 are accessed using an artificial finite-temperature (Boltzmann) ensemble.

First, distributions of the size of the largest component, in particular the large-deviation tail, are studied numerically for two graph ensembles, for Erdoes-Renyi random graphs with finite connectivity and for two-dimensional bond percolation. The distributions for the Erdoes-Renyi ensemble agree well with previously obtained analytical results. The results for the percolation problem, where no analytical results are available, are qualitatively similar, but the shapes of the distributions are somehow different and the finite-size corrections are sometimes much larger. Similar results are shown for a stochastic block model, which is often used to model communities structures in social networks. Here, also the distribution of the size of the largest component is studied and the role of the shape of the distribution with respect to the detectability threshold is elucidated.

Finally, 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.


From 1987 to 1993 I studied computer science at the Fernuniversität Hagen. I performed my Diploma thesis in the group of Prof. W.G. Schneeweiss on the simulation of fault-tolerant systems using importance sampling. From 1987 to 1994 I studied physics at the University of Duisburg. There I wrote 1993 my Diploma thesis in the group of Prof. K.D. Usadel on the calculation of ground states of diluted antiferromagnets in a field. In 1994 I moved to the University of Heidelberg where I worked on the simulation of polymer/noble-gas mixtures in the Computational physics group of Prof. D.W. Heermann. I completed my PhD in 1998 in the group of Prof. H. Horner. The title of my thesis is "Structure of ground states of disordered Ising systems" (in German). From 1998 I was a member of the group of Prof. A. Zippelius. In 2001 I spent seven months at the University of California Santa Cruz working with A.P. Young. Then I visited for 7 months the Ecole Normale Superieure collaborating with W. Krauth. I returned March 2002 to Göttingen and became member of the SFB (Sonderforschungsbereich) 602. From 1st of January 2003, I was heading the Junior Research group "Complex Ground States of Disorderd Systems" in Göttingen, funded by the VolkswagenStiftung. During this time, in June 2004 I completed in Göttingen my Habilitation. Since April 2007, I have been Professor for Computational Theoretical Physics at the University of Oldenburg.