Large-deviation properties of the largest biconnected component for random graphs
H Schawe, AK Hartmann - The European Physical Journal B, 2019 - Springer
The European Physical Journal B, 2019•Springer
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 …
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 …
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.
Graphical abstract
Springer