Minimum spanning trees on random networks

Abstract

We show that the geometry of minimum spanning trees (MST) on random graphs is universal. Due to this geometric universality, we are able to characterise the energy of MST using a scaling distribution ($P(\epsilon )$) found using uniform disorder. We show that the MST energy for other disorder distributions is simply related to $P(\epsilon )$. We discuss the relationship to invasion percolation (IP), to the directed polymer in a random media (DPRM) and the implications for the broader issue of universality in disordered systems.

4 pages, 3 figures

Cited by in corpus (29)

• Spatial Networks
• Percolation on complex networks: Theory and application
• Optimal Paths in Disordered Complex Networks
• Transport in weighted networks: Partition into superhighways and roads
• Optimal Path and Minimal Spanning Trees in Random Weighted Networks
• Are Domain Walls in Spin Glasses Described by Stochastic Loewner Evolutions?
• Fracturing the optimal paths
• Theory of minimum spanning trees I: Mean-field theory and strongly disordered spin-glass model
• Current Flow in Random Resistor Networks: The Role of Percolation in Weak and Strong Disorder
• Fracturing ranked surfaces
• The Competition for Shortest Paths on Sparse Graphs
• Counting spanning trees in self-similar networks by evaluating determinants
• Effect of Disorder Strength on Optimal Paths in Complex Networks
• New efficient methods to calculate watersheds
• Impact of Perturbations on Watersheds
• Theory of minimum spanning trees II: exact graphical methods and perturbation expansion at the percolation threshold
• A universal approach for drainage basins
• Scale-Free Networks Emerging from Weighted Random Graphs
• Stacked triangular lattice: Percolation properties
• The traveling salesman problem, conformal invariance, and dense polymers
• The upper critical dimension of the negative-weight percolation problem
• Random manifolds in non-linear resistor networks: Applications to varistors and superconductors
• The Futility of Being Selfish -- The Impact of Selfish Routing on Uncoordinated and Optimized Transportation Networks
• Minimum spanning trees and random resistor networks in d dimensions
• Cracking urban mobility
• Phase Transition in a Self-repairing Random Network
• Loop erased random walk on percolation cluster: Crossover from Euclidean to fractal geometry
• Invasion Percolation with a Hardening Interface under Gravity
• Optimal transport with constraints: from mirror descent to classical mechanics