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

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Distribution of diameters for Erdős-Rényi random graphs

A. K. Hartmann*

M. Mézard†

  • Institut für Physik, Carl von Ossietzky Universität Oldenburg, 26111 Oldenburg, Germany

  • Département de Physique de l'ENS, PSL University, 75005 Paris, France

  • *a.hartmann@uni-oldenburg.de
  • †marc.mezard@ens.fr
PDF

Phys. Rev. E 97, 032128 – Published 23 March, 2018

DOI: https://doi.org/10.1103/PhysRevE.97.032128

Abstract

We study the distribution of diameters d of Erdős-Rényi random graphs with average connectivity c. The diameter d is the maximum among all the shortest distances between pairs of nodes in a graph and an important quantity for all dynamic processes taking place on graphs. Here we study the distribution P(d) numerically for various values of c, in the nonpercolating and percolating regimes. Using large-deviation techniques, we are able to reach small probabilities like 10−100 which allow us to obtain the distribution over basically the full range of the support, for graphs up to N=1000 nodes. For values c<1, our results are in good agreement with analytical results, proving the reliability of our numerical approach. For c>1 the distribution is more complex and no complete analytical results are available. For this parameter range, P(d) exhibits an inflection point, which we found to be related to a structural change of the graphs. For all values of c, we determined the finite-size rate function Φ(d/N) and were able to extrapolate numerically to N→∞, indicating that the large-deviation principle holds.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (28)

  1. R. Cohen and S. Havlin, Complex Networks: Structure, Robustness and Function (Cambridge University, New York, 2010).
  2. M. Newman, Networks: An Introduction (Oxford University, Oxford, 2010).
  3. E. Estrada, The Structure of Complex Networks: Theory and Applications (Oxford University, Oxford, 2011).
  4. B. Doerr, M. Fouz, and T. Friedrich, Commun. ACM 55, 70 (2012).
  5. A. K. Hartmann, Eur. Phys. J. B 87, 114 (2014).
  6. A. Goldental, R. Vardi, S. Sardi, P. Sabo, and I. Kanter, Front. Neural Circ. 9, 65 (2015).
  7. B. Blonder, T. W. Wey, A. Dornhaus, R. James, and A. Sih, Meth. Ecol. Evol. 3, 958 (2012).
  8. R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002).
  9. P. Erdős and A. Rényi, Publ. Math. Inst. Hungar. Acad. Sci. 5, 17 (1960).
  10. T. Łuczak, Rand. Struct. Alg. 13, 485 (1998).
  11. A. K. Hartmann, Phys. Rev. E 65, 056102 (2002).
  12. S. Wolfsheimer, B. Burghardt, and A. K. Hartmann, Alg. Mol. Biol. 2, 9 (2007).
  13. L. Newberg, J. Comp. Biol. 15, 1187 (2008).
  14. F. den Hollander, Large Deviations (American Mathematical Society, Providence, 2000).
  15. H. Touchette, Phys. Rep. 478, 1 (2009).
  16. A. K. Hartmann, Eur. Phys. J. B 84, 627 (2011).
  17. M. E. J. Newman and G. T. Barkema, Monte Carlo Methods in Statistical Physics (Clarendon, Oxford, 1999).
  18. D. P. Landau and K. Binder, Monte Carlo Simulations in Statistical Physics (Cambridge University, New York, 2000).
  19. N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. Teller, and E. Teller, J. Chem. Phys. 21, 1087 (1953).
  20. A. M. Ferrenberg and R. H. Swendsen, Phys. Rev. Lett. 63, 1195 (1989).
  21. A. K. Hartmann, in New Optimization Algorithms in Physics, edited by A. K. Hartmann and H. Rieger (Whiley-VCH, Weinheim, 2004), p. 253.
  22. B. A. Berg and T. Neuhaus, Phys. Rev. Lett. 68, 9 (1992).
  23. F. Wang and D. P. Landau, Phys. Rev. Lett. 86, 2050 (2001).
  24. K. Mehlhorn and S. Näher, The LEDA Platform of Combinatorial and Geometric Computing (Cambridge University, New York, 1999).
  25. J. Cardy, Finite-Size Scaling (Elsevier, Amsterdam, 1988).
  26. N. Goldenfeld, Lectures on Phase Transitions and the Renormalization Group (Addison-Wesley, Reading, MA, 1992).
  27. A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications (Springer, Berlin, 2010).
  28. F. Chung and L. Lu, Adv. Appl. Math. 26, 257 (2001).

Outline

Information

Phys. Rev. E 97, 032128– Published 23 March, 2018
  • Received 16 October 2017
Crossmark - Check for updates button

©2018 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation