The tail does not determine the size of the giant

• Published in 2017
• Added on 2017-10-04

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

• http://arxiv.org/abs/1710.01208v1
• http://arxiv.org/pdf/1710.01208v1

Other information

BibTeX entry

@article{Thetaildoesnotdeterminethesizeofthegiant,
	key = {Thetaildoesnotdeterminethesizeofthegiant},
	type = {article},
	title = {The tail does not determine the size of the giant},
	author = {Maria Deijfen and Sebastian Rosengren and Pieter Trapman},
	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.},
	comment = {},
	date_added = {2017-10-04},
	date_published = {2017-12-07},
	urls = {http://arxiv.org/abs/1710.01208v1,http://arxiv.org/pdf/1710.01208v1},
	collections = {Attention-grabbing titles},
	url = {http://arxiv.org/abs/1710.01208v1 http://arxiv.org/pdf/1710.01208v1},
	urldate = {2017-10-04},
	archivePrefix = {arXiv},
	eprint = {1710.01208},
	primaryClass = {math.PR},
	year = 2017
}