Interesting Esoterica

The tail does not determine the size of the giant

Article by Maria Deijfen and Sebastian Rosengren and Pieter Trapman
  • Published in 2017
  • Added on
In the collection
The size of the giant component in the configuration model is given by a well-known expression involving the generating function of the degree distribution. In this note, we argue that the size of the giant is not determined by the tail behavior of the degree distribution but rather by the distribution over small degrees. Upper and lower bounds for the component size are derived for an arbitrary given distribution over small degrees $d\leq L$ and given expected degree, and numerical implementations show that these bounds are very 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. Hence the degree tail does not play the same crucial role for the size of the giant as it does for many other properties of the graph.

Links


BibTeX entry

@article{Thetaildoesnotdeterminethesizeofthegiant,
	title = {The tail does not determine the size of the giant},
	abstract = {The size of the giant component in the configuration model is given by a
well-known expression involving the generating function of the degree
distribution. In this note, we argue that the size of the giant is not
determined by the tail behavior of the degree distribution but rather by the
distribution over small degrees. Upper and lower bounds for the component size
are derived for an arbitrary given distribution over small degrees {\$}d\leq L{\$}
and given expected degree, and numerical implementations show that these bounds
are very 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. Hence the
degree tail does not play the same crucial role for the size of the giant as it
does for many other properties of the graph.},
	url = {http://arxiv.org/abs/1710.01208v1 http://arxiv.org/pdf/1710.01208v1},
	author = {Maria Deijfen and Sebastian Rosengren and Pieter Trapman},
	comment = {},
	urldate = {2017-10-04},
	archivePrefix = {arXiv},
	eprint = {1710.01208},
	primaryClass = {math.PR},
	year = 2017,
	collections = {Attention-grabbing titles}
}