Asymptotic Degree Distributions in Random Threshold Graphs

We discuss several limiting degree distributions for a class of homogeneous random graphs, known as 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,…, the fraction of nodes with degree d converges only in distribution to a non-degenerate random variable Π(d) (whose distribution depends on d), and not in probability to the aforementioned limiting nodal pmf as is customarily expected. The distribution of Π(d) is identified only through its characteristic function. Implications of this result include the following: (i) the empirical node distribution may not be used either as a proxy for or estimate of 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ási–Albert model as was argued by some authors; the two models cannot be meaningfully compared in terms of their degree distributions.