Pith. sign in

REVIEW 2 major objections 5 minor 18 references

Asymptotic degree distributions in random threshold graphs

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Under one scaling assumption, the fraction of nodes of a given degree in a random threshold graph converges to a non-degenerate random variable, not to the nodal degree distribution.

desk verdict A mostly rigorous, well-written paper showing that empirical degree fractions in random threshold graphs converge only in distribution to a non-degenerate limit; the one real gap is an unproved positivity claim under the full Assumption 1, which should be fixed before publication. read the letter →

arxiv 1908.07066 v1 pith:RM4OYHWN submitted 2019-08-19 math.PR cond-mat.stat-mechcs.DMcs.SI

Armand M. Makowski , Siddharth Pal This is my paper · ORCID
classification math.PRcond-mat.stat-mechcs.DMcs.SI MSC 05C8060F0560G70
keywords randomthresholdgraphsdegreedistributionempiricalnodalfitnessmodelscale-freenetworksweakconvergencecharacteristicfunction
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether the fraction of nodes of a given degree in a random threshold graph settles to the same limiting distribution as the degree of a single node. It shows the answer is no: under a broad scaling assumption on the fitness distribution, for each degree $d$ the empirical fraction $P_n(d;\theta^\star_n)$ converges only in distribution, to a non-degenerate random variable $\Pi(d)$, so the large-network histogram never settles down. In the exponential case this overturns the idea that these graphs provide a scale-free alternative to the Barabási–Albert model. The distribution of $\Pi(d)$ is identified through its characteristic function, built from joint degree probabilities of exchangeable limiting degrees.

What carries the argument

The argument rests on Assumption 1, which says the fitness distribution $F$ admits a threshold scaling $\theta^\star_n\to\infty$ for which $n(1-F(\theta^\star_n-x))$ converges to a non-identically-zero function $\lambda(x)$. This scaling makes the single-node degree converge to a conditionally Poisson variable $D$ with pmf $P[D=d]=E[\lambda(\xi)^d e^{-\lambda(\xi)}/d!]$. The main technical step, Proposition 3.3, extends this to the joint limit of $r$ node degrees via their multivariate probability generating function, expressed through order statistics and the random permutation arranging the fitness values. The method of moments then yields the characteristic function of $\Pi(d)$ from the joint probabilities $P[D_1=d,\ldots,D_r=d]$, and exchangeability of the limiting degrees supplies the factorial moments.

What would settle it

For exponentially distributed fitness with $\lambda=1$ and $\theta^\star_n=\log n$, compute the variance $\mathrm{Var}[\Pi(d)]=\mathrm{Cov}(\mathbf{1}[D_1=d],\mathbf{1}[D_2=d])$ from the joint generating function (49); if for some $d$ the variance vanishes, the claimed non-degeneracy fails. Equivalently, simulate many independent graphs at large $n$ and check whether the histogram of $P_n(d;\log n)$ collapses to a point at $p_{\rm Fuj}(d)$ rather than spreading.

Watch

Extended reading notes

Core claim

The paper's central result, Theorem 3.1, states that under Assumption 1 there exists, for each $d=0,1,\ldots$, a non-degenerate $[0,1]$-valued random variable $\Pi(d)$ such that $P_n(d;\theta^\star_n)$ converges in distribution to $\Pi(d)$, with $E[\Pi(d)]=P[D=d]$ and $\mathrm{Var}[\Pi(d)]>0$. Consequently the empirical degree fraction does not converge in probability to the nodal degree pmf, so the customary equation $P_n(d;\theta^\star_n)\to p_{\rm Fuj}(d)$ fails. The distribution of $\Pi(d)$ is given only through its characteristic function $$\Phi_d(t)=1+\sum_{r=1}^\infty \frac{(it)^r}{r!}\,P[D_1=d,\ldots,D_r=d],$$ where $(D_1,\ldots,D_r)$ are the exchangeable but dependent limiting degrees of $r$ distinct nodes. In the exponential case this directly contradicts the claim that random threshold graphs provide a scale-free alternative to the Barabási–Albert model; the two models cannot be compared through their empirical degree distributions.

Load-bearing premise

The whole result is conditional on Assumption 1: the fitness distribution must admit a threshold scaling $\theta^\star_n\to\infty$ for which $n(1-F(\theta^\star_n-x))$ converges to a non-identically-zero $\lambda(x)$; distributions without such regular variation are outside the scope, and even under the assumption the paper does not supply a proof of the asserted strict positivity of $\mathrm{Var}[\Pi(d)]$ for every $d$.

Editorial extensions

If this is right

  • For exponentially distributed fitness with $\theta^\star_n=\lambda^{-1}\log n$, the fraction of nodes of degree $d$ does not settle to a fixed value as $n$ grows; sample histograms fluctuate by an amount that does not vanish.
  • The empirical degree distribution of a single large random threshold graph cannot be used as an estimator or proxy for the limiting nodal degree pmf $p_{\rm Fuj}$.
  • Even in a homogeneous random graph model, the network-wide empirical degree distribution and the single-node degree distribution can carry fundamentally different information.
  • Random threshold graphs with exponential fitness do not provide a scale-free alternative to the Barabási–Albert model as claimed in earlier work; the two models cannot be meaningfully compared in terms of their degree distributions.
  • The same random-limit behavior holds for every fitness distribution satisfying Assumption 1, so the phenomenon is not an artifact of the exponential case.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A testable extension: for other homogeneous random graph models built from i.i.d. latent variables through a smooth edge kernel, the same random-limit phenomenon should appear whenever a Poisson-type scaling exists; plotting $\mathrm{Var}[P_n(d;\theta_n)]$ against $n$ would reveal whether the variance plateaus at a positive value.
  • If a closed-form expression for $\mathrm{Var}[\Pi(d)]$ can be derived for the exponential case, it would give practitioners a direct confidence interval for histogram fluctuations; the paper leaves this as an open computation.
  • The result implicitly challenges the common data-analysis practice of reading scale-freeness from a single observed degree histogram: even the correct homogeneous model would show run-to-run fluctuations that averaging over nodes within one network cannot remove.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies random threshold graphs with i.i.d. nonnegative fitness variables under Assumption 1, a tail-scaling condition on the fitness distribution. Under this assumption the authors prove that a single node's degree converges in distribution to a conditionally Poisson limit D, and they establish that the empirical degree fraction P_n(d; θ*_n) converges weakly to a [0,1]-valued limit Π(d) whose moments are given by P(D_1 = d, ..., D_r = d). The advertised conclusion is that Π(d) is non-degenerate, so the empirical degree fraction does not converge in probability to the nodal degree pmf; in the exponential case this is used to argue that random threshold graphs do not provide a scale-free alternative to the Barabási-Albert model. The proof proceeds through a multivariate pgf convergence result (Proposition 3.3), a method-of-moments step (Proposition 3.4), and identification of the limit via its characteristic function. Simulations for the exponential case illustrate the claimed non-degeneracy.

Significance. If the non-degeneracy claim is fully established, the paper makes a conceptually important point: in a homogeneous random graph model, the network-wide empirical degree distribution and the single-node degree distribution can have different asymptotic behavior. This has direct implications for empirical work that uses the empirical degree distribution as a proxy for the nodal distribution, and it corrects a claim in the threshold-graph literature about scale-free alternatives to preferential attachment. The proof strategy is generally rigorous and self-contained: the joint pgf convergence and the moment computations are carried out in detail, no fitted parameters appear, and the simulations support the qualitative conclusion. The main caveat is that the proof of Var[Π(d)] > 0, which is load-bearing for the headline conclusion, is deferred and not supplied under the full generality of Assumption 1.

major comments (2)
  1. [Section 5, Eq. (39); end of Section 7] The assertion Var[Π(d)] > 0 in Theorem 3.1 is not proved under the full Assumption 1. Section 5 refers to 'the discussion at the end of Section 7', but that discussion treats only the constant-λ case, where Π(d) is two-point with an explicit variance, and the exponential case, which is deferred to references [14,16]. Non-independence of D1,...,Dr, even if fully established, does not imply Cov(1[D1=d], 1[D2=d]) > 0 for every fixed d. Since Corollary 3.2 and the advertised failure of (7) depend precisely on this positivity, Theorem 3.1 as stated is conditional on a missing proof. Please supply a direct argument that Var[Π(d)] > 0 for every d under Assumption 1, or state and prove a weaker theorem.
  2. [Section 7, Eq. (50)] The inequality (50), asserting that the joint pgf of (D1,D2) differs from the product of the marginal pgfs, is stated after 'comparing (48) and (49)' but no proof is given. This is part of the claimed non-independence in Proposition 3.3 and is also the only qualitative support for the variance claim. For the constant-λ case the computation is explicit, but for a general nonconstant λ satisfying Assumption 1 a derivation is needed. The same comparison must also yield positive covariance of the indicators 1[D1=d] and 1[D2=d] for each d, which is a stronger statement than mere non-independence.
minor comments (5)
  1. [Section 4] The text contains a typo: 'high probbability' should be 'high probability'.
  2. [Section 4] The phrase 'The rv Π(d) is non-degenerate Fix d = 0, 1,...' appears to have a missing line break or punctuation; it should read as a subsection heading or a new sentence.
  3. [Section 7] In the constant-λ display, 'd,d ′ = 01, 2,...' should read 'd,d′ = 0,1,2,...'.
  4. [Introduction] The abstract and introduction state the failure of convergence in probability as a conclusion; given the missing variance proof, the wording should be softened or the proof supplied.
  5. [Assumption 1] It would be helpful to state explicitly that Assumption 1 is a regular-variation-type condition that many continuous distributions do not satisfy, so the theorem applies only to fitness distributions admitting such a scaling.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the main limit theorem is derived by a self-contained probabilistic argument under Assumption 1; self-citations appear only for the exponential special case and do not carry the general proof.

full rationale

The paper's central claim (Theorem 3.1) is not a restatement of its inputs. Assumption 1 fixes a scaling under which n(1-F(theta*_n - x)) converges to lambda(x); the paper then proves, rather than assumes, the limiting degree structure. Proposition 2.1 derives the nodal limit from a pgf computation; Proposition 7.1 (with Lemmas 9.1-9.2) computes the finite-dimensional joint pgf limit; Proposition 3.4 turns those joint probabilities into moment limits; Section 5 then uses a Levy-Cramer continuity argument to obtain weak convergence of the empirical degree fraction P_n(d;theta*_n) to a characteristic function defined by (37)-(38). No fitted parameter is renamed as a prediction, and no step identifies the limiting variable Pi(d) with the input scaling or with the quantity being predicted. The self-citations [14,15,16] concern the exponential-fitness special case: [15] announced Corollary 3.2 and [16] proved the non-convergence by order statistics; the current proof does not cite those results as the source of the general theorem. There is one non-circularity concern worth recording: the assertion Var[Pi(d)]>0 in Theorem 3.1 is justified in the text only by the sentence 'The fact that Var [Pi(d)]> 0 can be seen from the discussion at the end of Section 7. See also the references [14, 16]...', and Section 7's explicit variance computation covers the constant-lambda case while the exponential case is delegated to the authors' earlier work. For a nonconstant, non-exponential lambda satisfying Assumption 1, no fully explicit proof of positivity appears in the preprint. That is a missing-proof/correctness risk, not a circularity: the inequality is a substantive analytic claim and is not built into the definition of lambda or of Pi(d). Therefore the paper receives a low score for circularity, with the non-degeneracy gap flagged as an incompleteness rather than a self-referential reduction.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No new physical or probabilistic entities are postulated. The limit objects Pi(d) are derived random variables, not fitted parameters. The only structural input is the fitness distribution F and the scaling assumption on its tail.

assumptions (3)
  • domain assumption The fitness variables xi, xi_n are i.i.d. R+-valued with continuous distribution F supported on [0,infinity).
    Defines the random threshold graph model in Section 2.1 and is needed for the order-statistic treatment in Section 7; continuity avoids ties in fitness values almost surely.
  • domain assumption Assumption 1: There exists a scaling theta*_n with theta*_n tending to infinity and n(1-F(theta*_n - x)) converging to lambda(x) for every x at least 0, with lambda non-identically zero.
    This is the central structural hypothesis. It guarantees a non-trivial nodal limiting degree distribution (Proposition 2.1) and fixes the scaling under which Theorem 3.1 is proved. It excludes fitness distributions without such regular variation at infinity.
  • standard math Standard convergence theorems: bounded convergence, Cramer-Levy continuity theorem, Glivenko-Cantelli, and order-statistics factorization for i.i.d. continuous variables.
    Used in Sections 2, 5, 7, and 10 without proof; these are standard background results in probability theory.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Asymptotic degree distributions in random threshold graphs." pith.science (2026). https://pith.science/paper/RM4OYHWN

@misc{pith2026190807066,
  author       = {Pith},
  title        = {Pith review of: Asymptotic degree distributions in random threshold graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RM4OYHWN}},
  note         = {Machine review of arXiv:1908.07066}
}
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!

Figures

Figures reproduced from arXiv: 1908.07066 by the authors.

Figure 1
Figure 1. Histogram Hn,R(d; .) for degree d = 0 with varying number of nodes n and the number of runs R held fixed, and vice versa (a) Varying R and n = 30000 (b) Varying n and R = 100 [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Histogram Hn,R(d; .) for d = 5 with varying number of nodes n and the number of runs R held fixed, and vice versa The probability distribution x → Hn,R(d; x) has support on [0, 1] with Hn,R(d; x) = 0 for x < 0 and Hn,R(d; x) = 1 for 1 ≤ x, as does the probability distribution of Π(d). Under the enforced independence assumptions, the Glivenko-Cantelli Theorem [2, p. 103] asserts that lim R→∞  sup 0≤x≤1 |Hn,R(d; x) −… view at source ↗
Figure 3
Figure 3. Histogram Hn,R(d; .) for d = 10 with varying number of nodes n and the number of runs R held fixed, and vice versa Combining (29) and (30) with a simple triangle inequality argument naturally leads us to propose the approximation P [Π(d) ≤ x] =Approx Hn,R(d; x), x ∈ C(Π(d)) (31) with integers n and R selected sufficiently large. Put differently, we expect the probability distribution of Π(d) to be well approximated … view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The nodal degree distribution pFuj(.) was plotted against the empirical degree distribution N (r) n (.;θ ? n) n for various runs r = 1, 2, . . . , R. Next we explore the behavior of the empirical degree distribution (24) along the scaling (4) (with λ = 1) as generated …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Emergence of scaling in random networks,

    A.-L. Barab´ asi and R. Albert, “Emergence of scaling in random networks,” Science 286 (1999), pp. 509-512

    work page 1999

  2. [2]

    Billingsley, Convergence of Probability Measures , John Wiley & Sons, New York (NY), 1968

    P. Billingsley, Convergence of Probability Measures , John Wiley & Sons, New York (NY), 1968

    work page 1968

  3. [3]

    The degree sequence of a scale free random graph process,

    B. Bollob´ as, O. Riordan, J. Spencer and G. Tusn´ ady, “The degree sequence of a scale free random graph process,” Random Structures and Algorithms 18 (2001), pp. 279-290

    work page 2001

  4. [4]

    Scale-free networks from varying vertex intrinsic fitness,

    G. Caldarelli, A. Capocci, P. De Los Rios and M.A. Mu˜ noz, “Scale-free networks from varying vertex intrinsic fitness,” Physical Review Letters 89 (2002), 258702

    work page 2002

  5. [5]

    Power-law distributions in empirical data,

    A. Clauset, C. Rohilla Shalizi and M.E.J. Newman, “Power-law distributions in empirical data,” SIAM Review 51 (2009), pp. 661-703

    work page 2009

  6. [6]

    Chung, A Course in Probability Theory , Second Edition, Academic Press, New York (NY), 1974

    K.L. Chung, A Course in Probability Theory , Second Edition, Academic Press, New York (NY), 1974

    work page 1974

  7. [7]

    David and H.N

    H.A. David and H.N. Nagaraja, Order Statistics , Third Edition, Wiley Series in Proba- bility and Statistics, John Wiley & Sons, Hoboken (NJ), 2003

    work page 2003

  8. [8]

    Durrett, Random Graph Dynamics , Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge (UK), 2007

    R. Durrett, Random Graph Dynamics , Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge (UK), 2007

    work page 2007

Show all 18 references
  1. [9]

    Embrechts, C

    P. Embrechts, C. Kl¨ uppelberg and T. Mikosch,Modelling Extremal Events for Insurance and Finance, Springer-Verlag, Berlin (Germany), 1997

    1997

  2. [10]

    Limit theorems for the average distance and the degree distribution of the threshold network model,

    A. Fujihara, Y. Ide, N. Konno, N. Masuda, H. Miwa and M. Uchida, “Limit theorems for the average distance and the degree distribution of the threshold network model,” Interdisciplinary Information Sciences 15 (2003), pp. 361-366

    2003

  3. [11]

    Janson, T

    S. Janson, T. Luczak and A. Ruci´ nski, Random Graphs , Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York (NY), 2000

    2000

  4. [12]

    Scaling laws for connectivity in random threshold graph models with non-negative fitness variables,

    A. M. Makowski and O. Ya˘ gan, “Scaling laws for connectivity in random threshold graph models with non-negative fitness variables,” IEEE Journal on Selected Areas in Commu- nications JSAC–31 (2013), Special Issues on Emerging Technologies in Communications (Area 4: Social Networks)

    2013

  5. [13]

    The structure and function of complex networks,

    M.E.J. Newman, “The structure and function of complex networks,” SIAM Review 45 (2003), pp. 167-256

    2003

  6. [14]

    Pal, Adventures on Networks: Degrees and Games , Ph.D

    S. Pal, Adventures on Networks: Degrees and Games , Ph.D. Thesis, Department of Elec- trical and Computer Engineering, University of Maryland, College Park (MD), December 2015

    2015

  7. [15]

    On the asymptotics of degree distributions,

    S. Pal and A.M. Makowski, “On the asymptotics of degree distributions,” in the Proceed- ings of the 53rd IEEE Conference on Decision and Control (CDC 2015), Osaka (Japan), December 2015. 24

    2015

  8. [16]

    Asymptotic distributions in large (homogeneous) random networks: A little theory and a counterexample,

    S. Pal and A.M. Makowski, “Asymptotic distributions in large (homogeneous) random networks: A little theory and a counterexample,” IEEE Transactions on Network Science and Engineering. Accepted for publication, July 2019. Also available at arXiv:1710.11064

    2019 arXiv

  9. [17]

    Vertex intrinsic fitness: How to produce arbitrary scale-free networks,

    V.D.P. Servedio and G. Caldarelli, “Vertex intrinsic fitness: How to produce arbitrary scale-free networks,” Physical Review E 70 (2004), 056126

    2004

  10. [18]

    Shiryayev, Probability, Graduate Texts in Mathematics 95, Translated by R.P

    A.N. Shiryayev, Probability, Graduate Texts in Mathematics 95, Translated by R.P. Boas, Springer-Verlag, New York (NY), 1984. 25

    1984

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.