Large-deviation properties of the largest biconnected component for random graphs

Abstract

We study the size of the largest biconnected components in sparse Erdős-Rényi graphs with finite connectivity and Barabási-Albert graphs with non-integer mean degree. Using a statistical-mechanics inspired Monte Carlo approach we obtain numerically the distributions for different sets of parameters over almost their whole support, especially down to the rare-event tails with probabilities far less than $10^{-100}$. This enables us to observe a qualitative difference in the behavior of the size of the largest biconnected component and the largest $2$-core in the region of very small components, which is unreachable using simple sampling methods. Also, we observe a convergence to a rate function even for small sizes, which is a hint that the large deviation principle holds for these distributions.

arXiv comment8 pages, 8 figures

References in corpus (29)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Error and attack tolerance of complex networks
• Random graphs with arbitrary degree distributions and their applications
• An efficient, multiple range random walk algorithm to calculate the density of states
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• The large deviation approach to statistical mechanics
• Determining the density of states for classical statistical models: A random walk algorithm to produce a flat histogram
• Fast Algorithm to Calculate Density of States
• Wang-Landau Algorithm: a Theoretical Analysis of the Saturation of the Error
• Avoiding Boundary Effects in Wang-Landau Sampling
• Sampling rare events: statistics of local sequence alignments
• Large-deviation properties of largest component for random graphs
• Bicomponents and the robustness of networks to failure
• Rare events and discontinuous percolation transitions
• On large deviation properties of Erdos-Renyi random graphs
• Fluctuations in percolation of sparse complex networks
• Distribution of diameters for Erdös-Rényi random graphs
• Convex Hulls of Random Walks: Large-Deviation Properties
• Large-deviation properties of resilience of power grids
• Bias in generation of random graphs
• Maximum flow and topological structure of complex networks
• Large-deviations/thermodynamic approach to percolation on the complete graph
• Complete high-precision entropic sampling
• Large Deviations of Convex Hulls of Self-Avoiding Random Walks
• Convex Hulls of Multiple Random Walks: A Large-Deviation Study
• Fragmentation properties of two-dimensional Proximity Graphs considering random failures and targeted attacks
• Score distributions of gapped multiple sequence alignments down to the low-probability tail

Cited by in corpus (10)

• Percolation on complex networks: Theory and application
• Long time position distribution of an active Brownian particle in two dimensions
• Position distribution in a generalised run and tumble process
• Rare-Event Properties of the Nagel-Schreckenberg Model
• First-passage area distribution and optimal fluctuations of fractional Brownian motion
• How many longest increasing subsequences are there?
• Large deviations of connected components in the stochastic block model
• Large deviations of a random walk model with emerging territories
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• Dimensionality-induced dynamical phase transition in the large deviation of local time density for Brownian motion