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

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2018
Hartmann, Alexander K.; Mezard, Marc
File in questo prodotto:
File
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
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11565/4064278`