Asymptotic degree distributions in random threshold graphs

arXiv1908.07066MaRDI QIDQ6323894FDOQ6323894

Authors: Armand M. Makowski, Siddharth Pal 

Publication date: 19 August 2019

Abstract: We discuss several limiting degree distributions for a class of random threshold graphs in the many node regime. This analysis is carried out under a weak assumption on the distribution of the underlying fitness variable. This assumption, which is satisfied by the exponential distribution, determines a natural scaling under which the following limiting results are shown: The nodal degree distribution, i.e., the distribution of any node, converges in distribution to a limiting pmf. However, for each $d=0,1,ldots$, the fraction of nodes with given degree $d$ converges only in distribution to a non-degenerate random variable $Pi(d)$ (whose distribution depends on $d$),and not in probability to the aforementioned limiting nodal pmf as is customarily expected. The distribution of $Pi(d)$ is identified only through its characteristic function. Implications of this result include: (i) The empirical node distribution may not be used as a proxy for or as an estimate to the limiting nodal pmf; (ii) Even in homogeneous graphs, the network-wide degree distribution and the nodal degree distribution may capture vastly different information; and (iii) Random threshold graphs with exponential distributed fitness do not provide an alternative scale-free model to the Barab'asi-Albert model as was argued by some authors; the two models cannot be meaningfully compared in terms of their degree distributions!

This page was built for publication: Asymptotic degree distributions in random threshold graphs

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