We study the distribution of diameters d of Erdos-Renyi 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 Phi(d/N) and were able to extrapolate numerically to N -> infinity, indicating that the large-deviation principle holds.

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

Mezard, Marc
2018

Abstract

We study the distribution of diameters d of Erdos-Renyi 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 Phi(d/N) and were able to extrapolate numerically to N -> infinity, indicating that the large-deviation principle holds.
File in questo prodotto:
File Dimensione Formato  
2018-Hartmann_Mezard Diameters random graphs.pdf

accesso aperto

Descrizione: arXiv
Tipologia: Documento in Pre-print (Pre-print document)
Licenza: Creative commons
Dimensione 360.04 kB
Formato Adobe PDF
360.04 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11565/4064278
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 31
  • ???jsp.display-item.citation.isi??? 27
social impact