Metastable behaviour of random graphs

For reversible Markov processes on arbitrary graphs, average crossing times from one set to another can be computed with the help of potential theory. Especially in metastable situations, where to tunnel from one set to another the process has to overcome a "high energetic hill", average crossing times can be well approximated via a computation of capacities.

The latter are given by variational principles, such as the Dirichlet principle for potentials or the Thomson principle for flows. These typically reduce from high-dimensional to low-dimensional in metastable situations. Such situations may be expected to occur when the graph has a small number of hubs and the crossover is most likely to take place via one of these hubs.

An interesting challenge is to study metastability in a setting where the network transports information. A general paradigm is that large complex networks perform well up to a critical level of transportation and break down beyond. This breakdown ought to be reflected in the metastable behaviour of the network.