Large Deviation Properties of Minimum Spanning Trees for Random Graphs

Abstract

We study the large-deviation properties of minimum spanning trees for two ensembles of random graphs with $N$ nodes. First, we consider complete graphs. Second, we study Erdős-Rényi (ER) random graphs with edge probability $p=c/N$ conditioned to be connected. By using large-deviation Markov chain sampling, we are able to obtain the distribution $P(W)$ of the spanning-tree weight $W$ down to probability densities as small as $10^{-300}$. For the complete graph, we confirm analytical predictions with respect to the expectation value. For both ensembles, the large deviation principle is fulfilled. For the connected ER graphs, we observe a remarkable change of the distributions at the value of $c=1$, which is the percolation threshold for the original ER ensemble.

9 pages, 12 figures

References in corpus (16)

• The large deviation approach to statistical mechanics
• Transport in weighted networks: Partition into superhighways and roads
• Scale-free trees: the skeletons of complex networks
• Large-deviation properties of largest component for random graphs
• High-precision simulation of the height distribution for the KPZ equation
• Theory of minimum spanning trees I: Mean-field theory and strongly disordered spin-glass model
• Counting spanning trees in a small-world Farey graph
• Distribution of diameters for Erdös-Rényi random graphs
• Theory of minimum spanning trees II: exact graphical methods and perturbation expansion at the percolation threshold
• On the length of a random minimum spanning tree
• Large-deviations/thermodynamic approach to percolation on the complete graph
• Fluctuations in the random-link matching problem
• Minimal spanning trees at the percolation threshold: a numerical calculation
• Numerical Aspects of Large Deviations
• The Random Fractional Matching Problem
• Large deviations of connected components in the stochastic block model