The tail does not determine the size of the giant

DOI10.1007/S10955-018-2071-4MaRDI QIDQ1633970zbMATH OpenOpenAlexWikidataFDO

Authors Maria Deijfen, Sebastian Rosengren, Pieter Trapman

Publication date 21 December 2018

Published in Journal of Statistical Physics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1710.01208

zbMATH Keywords

component sizeconfiguration modeldegree distribution

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: The size of the giant component in the configuration model, measured by the asymptotic fraction of vertices in the component, is given by a well-known expression involving the generating function of the degree distribution. In this note, we argue that the distribution over small degrees is more important for the size of the giant component than the precise distribution over very large degrees. In particular, the tail behavior of the degree distribution does not play the same crucial role for the size of the giant as it does for many other properties of the graph. Upper and lower bounds for the component size are derived for an arbitrary given distribution over small degrees $dleqL$ and given expected degree, and numerical implementations show that these bounds are close already for small values of $L$. On the other hand, examples illustrate that, for a fixed degree tail, the component size can vary substantially depending on the distribution over small degrees.

Recommendations

• Sometimes size does not matter
• Maximizing the size of the giant
• Size matters!
• Heavy or semi-heavy tail, that is the question
• Tail area revisited
• Scale matters

Cites work

• A critical point for random graphs with a given degree sequence
• A new approach to the giant component problem
• A Phase Transition for the Diameter of the Configuration Model
• Distances in random graphs with finite mean and infinite variance degrees
• Distances in random graphs with finite variance degrees
• Generating simple random graphs with prescribed degree distribution
• Maximizing the size of the giant
• Random graphs and complex networks. Volume 1
• The impact of degree variability on connectivity properties of large networks
• The probability that a random multigraph is simple
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence

Cited in

(2)

• Connectivity of random hypergraphs with a given hyperedge size distribution
• Connectivity of random graphs after centrality-based vertex removal

This page was built for publication: The tail does not determine the size of the giant

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1633970)