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

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 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 non-percolating and the percolating regime. Using large-deviations 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.

9 figures

References in corpus (1)

• The large deviation approach to statistical mechanics

Cited by in corpus (25)

• Large-deviation properties of the largest biconnected component for random graphs
• Position distribution in a generalised run and tumble process
• Large deviation theory of percolation on multiplex networks
• Intermediate deviation regime for the full eigenvalue statistics in the complex Ginibre ensemble
• Critical behavior of the Anderson model on the Bethe lattice via a large-deviation approach
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• Edge fluctuations and third-order phase transition in harmonically confined long-range systems
• Observing symmetry-broken optimal paths of stationary Kardar-Parisi-Zhang interface via a large-deviation sampling of directed polymers in random media
• Rare-Event Properties of the Nagel-Schreckenberg Model
• Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication
• A Monte Carlo algorithm to measure probabilities of rare events in cluster-cluster aggregation
• Analytical results for the distribution of cover times of random walks on random regular graphs
• Condensation of degrees emerging through a first-order phase transition in classical random graphs
• The birth of geometry in exponential random graphs
• Statistical analysis of edges and bredges in configuration model networks
• Large-deviations of the SIR model around the epidemic threshold
• Large Deviations of Convex Hulls of the "True" Self-Avoiding Random Walk
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Numerical Aspects of Large Deviations
• Phase transitions in atypical systems induced by a condensation transition on graphs
• Large deviations of connected components in the stochastic block model
• Gelation in input-driven aggregation
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• Large Deviation Properties of Minimum Spanning Trees for Random Graphs
• Resistance distance distribution in large sparse random graphs