- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

Export citation

Export citation

Choose format for download:

Download Citation
  • Open Access
  • Access by Xinjiang University

Large deviation properties of minimum spanning trees for random graphs

Mahdi Sarikhani1 and Alexander K. Hartmann2

PDF

Phys. Rev. E 114, 024314 – Published 27 August, 2026

DOI: https://doi.org/10.1103/xc5g-t9dj

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 on being connected. By using large-deviation Markov-chain sampling, we can 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.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (56)

  1. R. Albert and A.-L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74, 47 (2002).
  2. M. E. J. Newman, The structure and function of complex networks, SIAM Rev. 45, 167 (2003).
  3. S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D. U. Hwang, Complex networks: Structure and dynamics, Phys. Rep. 424, 175 (2006).
  4. S. N. Dorogovtsev and J. F. F. Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW (Oxford University Press, Oxford, 2003).
  5. M. Newman, Networks: An Introduction (Oxford University Press, Oxford, 2010).
  6. A. Barrat, M. Barthélemy, and A. Vespignani, Dynamical Processes on Complex Networks (Cambridge University Press, Cambridge, 2012).
  7. M. Biskup, L. Chayes, and S. A. Smith, Large-deviations/thermodynamic approach to percolation on the complete graph, Random Struct. Algorithms 31, 354 (2007).
  8. A. K. Hartmann, Large-deviation properties of largest component for random graphs, Eur. Phys. J. B 84, 627 (2011).
  9. H. Schawe and A. K. Hartmann, Large deviations of connected components in the stochastic block model, Phys. Rev. E 102, 052108 (2020).
  10. T. Łuczak, Random trees and random graphs, Random Struct. Algorithms 13, 485 (1998).
  11. A. K. Hartmann and M. Mézard, Distribution of diameters for Erdős-Rényi random graphs, Phys. Rev. E 97, 032128 (2018).
  12. M. Mézard and G. Parisi, On the solution of the random link matching problems, J. Phys. 48, 1451 (1987).
  13. G.-Y. Shi, Y.-X. Kong, H. Liao, and Y.-C. Zhang, Analysis of ground state in random bipartite matching, Physica A 444, 397 (2016).
  14. C. Lucibello, E. M. Malatesta, G. Parisi, and G. Sicuro, The random fractional matching problem, J. Stat. Mech. (2018) 053301.
  15. E. M. Malatesta, G. Parisi, and G. Sicuro, Fluctuations in the random-link matching problem, Phys. Rev. E 100, 032102 (2019).
  16. J. Houdayer, J. H. Boutet de Monvel, and O. C. Martin, Comparing mean field and Euclidean matching problems, Eur. Phys. J. B 6, 383 (1998).
  17. R. L. Graham and P. Hell, On the History of the Minimum Spanning Tree Problem, IEEE Ann. Hist. Comput. 7, 43 (1985).
  18. R. C. Prim, Shortest connection networks and some generalizations, Bell Syst. Tech. J. 36, 1389 (1957).
  19. L. L. Cavalli-Sforza and A. W. F. Edwards, Phylogenetic analysis: Models and estimation procedures, Evolution 21, 550 (1967).
  20. J. C. Gower and G. J. S. Ross, Minimum spanning trees and single linkage cluster analysis, J. R. Stat. Soc. C: Appl. Stat. 18, 54 (1969).
  21. J. Wu, X. Li, L. Jiao, X. Wang, and B. Sun, Minimum spanning trees for community detection, Physica A 392, 2265 (2013).
  22. R. E. Osteen and P. P. Lin, Picture skeletons based on eccentricities of points of minimum spanning trees, SIAM J. Comput. 3, 23 (1974).
  23. Z. Zhang, B. Wu, and Y. Lin, Counting spanning trees in a small-world Farey graph, Physica A 391, 3342 (2012).
  24. T. Li and W. Yan, Enumeration of spanning trees of 2-separable networks, Physica A 536, 120877 (2019).
  25. C. Dussert, G. Rasigni, M. Rasigni, J. Palmari, and A. Llebaria, Minimal spanning tree: A new approach for studying order and disorder, Phys. Rev. B 34, 3528 (1986).
  26. D. V. Ktitarev, S. Lübeck, P. Grassberger, and V. B. Priezzhev, Scaling of waves in the Bak-Tang-Wiesenfeld sandpile model, Phys. Rev. E 61, 81 (2000).
  27. Z. Wu, L. A. Braunstein, S. Havlin, and H. E. Stanley, Transport in weighted networks: Partition into superhighways and roads, Phys. Rev. Lett. 96, 148702 (2006).
  28. D.-H. Kim, J. D. Noh, and H. Jeong, Scale-free trees: The skeletons of complex networks, Phys. Rev. E 70, 046126 (2004).
  29. G. Bonanno, G. Caldarelli, F. Lillo, and R. N. Mantegna, Topology of correlation-based minimal spanning trees in real and model markets, Phys. Rev. E 68, 046130 (2003).
  30. J.-P. Onnela, A. Chakraborti, K. Kaski, J. Kertész, and A. Kanto, Dynamics of market correlations: Taxonomy and portfolio analysis, Phys. Rev. E 68, 056110 (2003).
  31. T. S. Jackson and N. Read, Theory of minimum spanning trees. I. Mean-field theory and strongly disordered spin-glass model, Phys. Rev. E 81, 021130 (2010).
  32. T. S. Jackson and N. Read, Theory of minimum spanning trees. II. Exact graphical methods and perturbation expansion at the percolation threshold, Phys. Rev. E 81, 021131 (2010).
  33. S. M. Sweeney and A. A. Middleton, Minimal spanning trees at the percolation threshold: A numerical calculation, Phys. Rev. E 88, 032129 (2013).
  34. T. I. Fenner and A. M. Frieze, On the connectivity of randomm-orientable graphs and digraphs, Combinatorica 2, 347 (1982).
  35. A. M. Frieze, On the value of a random minimum spanning tree problem, Discrete Appl. Math. 10, 47 (1985).
  36. C. McDiarmid, in Surveys in Combinatorics, edited by J. Siemons (Cambridge University Press, Cambridge, 1989), pp. 148–188.
  37. S. Janson, The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph, Random Struct Algorithms 7, 337 (1995).
  38. A. D. Flaxman, The lower tail of the random minimum spanning tree, Electron. J. Combin. 14, N3 (2007).
  39. W. V. Li and X. Zhang, On the difference of expected lengths of minimum spanning trees, Comb. Probab. Comput. 18, 423 (2009).
  40. C. Cooper, A. Frieze, N. Ince, S. Janson, and J. Spencer, On the length of a random minimum spanning tree, Comb. Probab. Comput. 25, 89 (2016).
  41. J. A. Bucklew, Introduction to Rare Event Simulation (Springer New York, 2004).
  42. F. den Hollander, Large Deviations (American Mathematical Society, Providence, 2008).
  43. H. Touchette, The large deviation approach to statistical mechanics, Phys. Rep. 478, 1 (2009).
  44. P. Erdős and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5, 17 (1960).
  45. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (MIT Press, Cambridge, 2001).
  46. A. K. Hartmann, Sampling rare events: Statistics of local sequence alignments, Phys. Rev. E 65, 056102 (2002).
  47. A. K. Hartmann, Numerical aspects of large deviations, SciPost Phys. Lect. Notes 100 (2025).
  48. N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. Teller, and E. Teller, Equation of state calculations by fast computing machines, J. Chem. Phys. 21, 1087 (1953).
  49. W. K. Hastings, Monte Carlo sampling methods using Markov chains and their applications, Biometrika 57, 97 (1970).
  50. M. E. J. Newman and G. T. Barkema, Monte Carlo Methods in Statistical Physics (Oxford University Press, Oxford, 1999).
  51. D. P. Landau and K. Binder, A Guide to Monte Carlo Simulations in Statistical Physics (Cambridge University Press, Cambridge, 2005).
  52. One could optimize the performance by changing more entries, with the number of changes depending on N and θ, but with our simple choice we could obtain sufficient performance.
  53. The data generated in this work are publicly available in the DARE repository of the University of Oldenburg [56].
  54. J. M. Steele, in Mathematics and Computer Science II, edited by B. Chauvin, P. Flajolet, D. Gardy, and A. Mokkadem (Birkhäuser Basel, Basel, 2002), pp. 223–245.
  55. A. K. Hartmann, P. Le Doussal, S. N. Majumdar, A. Rosso, and G. Schehr, High-precision simulation of the height distribution for the KPZ equation, Europhys. Lett. 121, 67004 (2018).
  56. M. Sarikhani and A. K. Hartmann, Data and gnuplot plot files, DARE public repository, doi: 10.57782/BKJRBF (2025).

Outline

Information

Phys. Rev. E 114, 024314– Published 27 August, 2026
  • Received 23 November 2025
  • Accepted 22 July 2026
Crossmark - Check for updates button
Creative Commons Logo

Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.

Published by the American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation