In his paper Kronecker Graphs: An approach to modeling Networks Jure et Al, mention that an important property of networks are that they are heavy tailed.
I'm trying to get an insight on what this really means. Do you have good examples of real heavy-tailed distributions, or what does it really means.
Thanks
"Heavy tailed" is a bit tricky in the sense that there is no unique definition of what it really means. Usually, it refers to the MGF being infinite on the side of zero that the heavy tail is (i.e. right tail, MGF infinite for arguments $> 0$ etc.). However, as is pointed out by Mikosch in one of his papers (I forget which one), the notion of heavy-tailedness depends on the model under consideration.
Commonly used versions of heavy-tailed random variables are those which are $(i)$ regularly varying and $(ii)$ subexponential ($(i)$ being a subclass of $(ii)$). Regularly varying refers to the tail of the distribution being regularly varying in the usual sense from analysis. The perhaps easiest example of such a distribution is the Pareto distribution. That a distribution is subexponential means that
$ \lim _{x \to \infty} \frac{P (S_n > x)}{n P (X_1 > x)} = 1,$
where $S_n$ is the sum of $n$ i.i.d. random variables and $n=2,3,...$ Example of such a distribution is the Weibull distribution.
Having heavy tails basically means, as the name hints, that the tail of the distribution decays slower "than normal". E.g., in the case of a regularly varying distribution the decay is according to a power law.
In looking at the paper briefly, it would seem that investigate various random variables associated to certain networks and random operators on them (such as transition probabilities for a given edge etc.) and discuss that these give probability distributions with heavy tails. There is a wikipedia article on heavy tailed distributions; very briefly, being heavy-tailed means that the distribution decays slowly at infinity (for example, too slowly to have finite moments). An example of a heavy tailed distribution is the Cauchy law (with density, up to constants, $(1+x^2)^{-1} dx$) as well as many infinitely divisible laws.
