Asymptotic degree distributions in random threshold graphs
share
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, ..., the fraction of nodes with given 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: (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ási-Albert model as was argued by some authors; the two models cannot be meaningfully compared in terms of their degree distributions!
READ FULL TEXT