Distribution of diameters for Erdos-Renyi random graphs

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.