Asymptotic Degree Distributions in Random Threshold Graphs
Entropy · 27.05.2026 · 28 (6) · 603
DOI: 10.3390/e28060603 ↗Kurz gefasst
Fachartikel in der Zeitschrift Entropy, online erschienen am 27.05.2026. Verfasst von Armand M Makowski und 1 weiteren Autor:innen. Beteiligte Einrichtung: Department of Electrical and Computer Engineering, University of Maryland, College Park, MD 20742, USA. Die Arbeit nennt 19 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation, NSF, Lady Davis Trust.
Abstract (Originalsprache)
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.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- Department of Electrical and Computer Engineering, University of Maryland, College Park, MD 20742, USA.
- RTX BBN Technologies, Columbia, MD 21046, USA.
Förderung
- National Science Foundation
- NSF
- Lady Davis Trust
Zitieren
APA
Makowski, A. M., & Pal, S. (2026). Asymptotic Degree Distributions in Random Threshold Graphs. Entropy, 28(6), 603. https://doi.org/10.3390/e28060603
Vancouver
Makowski AM, Pal S. Asymptotic Degree Distributions in Random Threshold Graphs. Entropy. 2026;28(6):603. doi:10.3390/e28060603
BibTeX
@article{Makowski2026,
author = {Makowski, Armand M and Pal, Siddharth},
title = {Asymptotic Degree Distributions in Random Threshold Graphs},
journal = {Entropy},
year = {2026},
volume = {28},
number = {6},
pages = {603},
doi = {10.3390/e28060603}
}
EUVIMED