On large deviation properties of Erdos-Renyi random graphs

Abstract

We show that large deviation properties of Erdös-Rényi random graphs can be derived from the free energy of the $q$-state Potts model of statistical mechanics. More precisely the Legendre transform of the Potts free energy with respect to $\ln q$ is related to the component generating function of the graph ensemble. This generalizes the well-known mapping between typical properties of random graphs and the $q\to 1$ limit of the Potts free energy. For exponentially rare graphs we explicitly calculate the number of components, the size of the giant component, the degree distributions inside and outside the giant component, and the distribution of small component sizes. We also perform numerical simulations which are in very good agreement with our analytical work. Finally we demonstrate how the same results can be derived by studying the evolution of random graphs under the insertion of new vertices and edges, without recourse to the thermodynamics of the Potts model.

arXiv comment38 pages, 9 figures, Latex2e, corrected and extended version including numerical simulation results

References in corpus (9)

• Statistical mechanics of complex networks
• Boosting search by rare events
• Sampling rare events: statistics of local sequence alignments
• Floppy modes and the free energy: Rigidity and connectivity percolation on Bethe Lattices
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
• Exponentially hard problems are sometimes polynomial, a large deviation analysis of search algorithms for the random Satisfiability problem, and its application to stop-and-restart resolutions
• Properties of atypical graphs from negative complexities
• Optimal Cooperation and Submodularity for Computing Potts' Partition Functions with a Large Number of State

Cited by in corpus (39)

• Structural Properties of the Caenorhabditis elegans Neuronal Network
• Entropies of complex networks with hierarchically constrained topologies
• Large-deviation properties of largest component for random graphs
• Rare events and discontinuous percolation transitions
• Large deviations of empirical neighborhood distribution in sparse random graphs
• High-precision simulation of the height distribution for the KPZ equation
• Large-deviation properties of the largest biconnected component for random graphs
• Large deviation theory of percolation on multiplex networks
• Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art
• Rigidity percolation by next-nearest-neighbor braces on generic and regular isostatic lattices
• Probing the tails of the ground state energy distribution for the directed polymer in a random medium of dimension $d=1,2,3$ via a Monte-Carlo procedure in the disorder
• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• Ensemble inequivalence in random graphs
• Probing the large deviations of the Kardar-Parisi-Zhang equation at short time with an importance sampling of directed polymers in random media
• Large-deviation properties of resilience of transportation networks
• Sampling fractional Brownian motion in presence of absorption: a Markov Chain method
• The large deviations of the whitening process in random constraint satisfaction problems
• Finding long cycles in graphs
• Large-deviations/thermodynamic approach to percolation on the complete graph
• Large Deviations of Convex Hulls of Self-Avoiding Random Walks
• The cavity method for large deviations
• Rare-Event Properties of the Nagel-Schreckenberg Model
• A large-deviations principle for all the cluster sizes of a sparse Erdős-Rényi graph
• Percolation transition in correlated hypergraphs
• Typical and large-deviation properties of minimum-energy paths on disordered hierarchical lattices
• Properties of atypical graphs from negative complexities
• Percolation transition and distribution of connected components in generalized random network ensembles
• First-passage area distribution and optimal fluctuations of fractional Brownian motion
• Efficient large deviation estimation based on importance sampling
• Large Deviations of Convex Hulls of the "True" Self-Avoiding Random Walk
• Large-deviations of the SIR model around the epidemic threshold
• Weighted projected networks: mapping hypergraphs to networks
• A thermodynamic model for agglomeration of DNA-looping proteins
• First-passage properties of the jump process with a drift. Two exactly solvable cases
• Large deviations of extreme eigenvalues of generalized sample covariance matrices
• Importance Sampling for counting statistics in one-dimensional systems
• Approaching the thermodynamic limit in equilibrated scale-free networks
• Heterogeneity in Outcomes of Repeated Instances of Percolation Experiments