Pith. sign in

REVIEW 2 major objections 4 minor 14 references

Degrees in Preferential Attachment Networks with an Anomaly

T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Pith's one-line read An anomaly that enters a preferential-attachment network early changes the degree distribution's power-law exponent; the same anomaly arriving late leaves almost no trace.

desk verdict Useful exact mean-degree results for a PA model with an arbitrary-time anomaly, but the early-anomaly exponent is heuristic and untested by the simulations, and Section 5 has a formula error. read the letter →

arxiv 2505.03340 v1 pith:MA5FGGNW submitted 2025-05-06 physics.soc-ph math.PR

classification physics.soc-phmath.PR MSC 05C8060C05 PACS 89.75.Hc
keywords preferentialattachmentanomalousvertexdegreedistributionpower-lawexponentsuperstarmodelexpecteddynamicnetworkchangepoint
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

This paper studies a preferential attachment network into which a single 'anomaly' vertex arrives at time τ and thereafter captures a fixed share of every new edge. It proves an exact formula for the anomaly's expected degree, which grows almost linearly with network size, and derives the power-law exponent of the ordinary vertices' degree distribution as a function of τ. The main finding is a timing dichotomy: an early anomaly significantly steepens the degree distribution, while a late anomaly leaves the network nearly indistinguishable from the standard preferential attachment model. The paper also shows that the oldest vertex grows faster under an early anomaly, which explains the visible outliers in the simulated tail.

What carries the argument

The load-bearing object is the recursion for expected degrees under the modified attachment rule, in which the anomaly's edge-receiving probability is $((t-1)\beta + D_\tau + \delta)$ divided by the universal denominator. Solving this recursion yields the exact closed form in Proposition 1 for the anomaly's mean degree. The heuristic degree-distribution argument then uses the asymptotic formula for $\mathbb{E}[D_i(t)+\delta]$ as a function of the vertex index $i$ to count how many indices have expected degree near $k$; inverting this index-to-degree map produces the power-law exponents in (14), (17), and (18).

What would settle it

Simulate the model with $m=1$, $\delta=0$, $\beta=2$, anomaly at $\tau=1000$, and run to $t=10^5$ and $t=2\times 10^5$. Proposition 1 predicts $\mathbb{E}[D_\tau(t)+\delta]/t \to \frac{m\beta}{m+\beta+\delta} = \frac{2}{3}$. If the empirical ratio converges to a different constant, or the finite-time gamma-ratio correction is not observed, the closed form is wrong. For the heuristic distribution, simulate $\tau=\alpha t$ with $\alpha=1/2$ over many runs and compare the tail of pre-anomaly vertices to the predicted slope $-(2+\frac{\delta}{m})$ with pre-factor $\alpha^{\frac{\beta}{2m+\beta+\delta}}$.

Watch

Extended reading notes

Core claim

The central claim is that the presence of an anomalous vertex that attracts a fixed probability of each new edge—on top of its normal preferential-attachment share—changes the network's degree structure in a way that depends sharply on when the anomaly appears. For the anomaly itself, the expected degree obeys the exact identity $\mathbb{E}[D_\tau(t)+\delta] = \frac{m\beta t}{m+\beta+\delta} + c_0 \frac{\Gamma(t + \frac{m}{2m+\beta+\delta})\Gamma(\tau)}{\Gamma(t)\Gamma(\tau + \frac{m}{2m+\beta+\delta})}$, so it grows linearly with slope $\frac{m\beta}{m+\beta+\delta}$, larger than the per-edge attraction probability $\frac{\beta}{2m+\beta+\delta}$. For ordinary vertices, the paper argues heuristically that the degree distribution is still a power law, with exponent $3+\frac{\delta}{m}$ when the anomaly arrives late ($\tau=t-t^\gamma$) or mid-way ($\tau=\alpha t$), and exponent $3+\frac{\beta+\delta}{m}$ when it arrives early ($\tau=t^\gamma$); the mid-way case also picks up a multiplicative factor $\alpha^{\frac{\beta}{2m+\beta+\delta}}$.

Load-bearing premise

The heuristic derivation assumes that a vertex's degree is tightly concentrated around its expected value, so that the fraction of vertices with expected degree near $k$ can be equated with the true fraction of degree-$k$ vertices; the paper does not prove concentration, and the rigorous derivation is left open.

Editorial extensions

If this is right

  • If the anomaly arrives early, the ordinary vertices' power-law exponent jumps from $3+\frac{\delta}{m}$ to $3+\frac{\beta+\delta}{m}$, so the network tail becomes considerably thinner.
  • If the anomaly arrives mid-way, the exponent stays $3+\frac{\delta}{m}$ but the degree distribution is multiplied by $\alpha^{\frac{\beta}{2m+\beta+\delta}}$, meaning the high-degree pre-anomaly vertices grow slower than in the standard model.
  • If the anomaly arrives late, the degree distribution converges to the standard preferential attachment power law, so detecting the anomaly from the degree sequence alone becomes hard.
  • The anomaly's own degree grows linearly at a rate larger than its fixed edge-capture probability, because it also receives edges through the regular preferential attachment channel.
  • The oldest vertex's expected degree grows as $t^{\frac{\gamma}{2+\delta/m} + \frac{1-\gamma}{2+(\beta+\delta)/m}}$ for an early anomaly, outstripping the rate implied by the early-anomaly power law and producing the observed right tail.

Reading between the lines

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

  • The exact gamma-ratio correction in the anomaly's expected degree quantifies how long it takes the anomaly to reach its linear asymptote; this transient could serve as a finite-time signature of the anomaly's age.
  • The same index-to-degree heuristic, applied separately to pre- and post-anomaly vertices, would yield the full two-population degree distribution; the paper only states the aggregate.
  • Comparing the early-anomaly exponent $3+\frac{\beta+\delta}{m}$ with the superstar model's $3+\frac{p}{1-p}$ could in principle distinguish a constant edge-attraction mechanism from a degree-proportional one in empirical networks.
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 / 4 minor

Summary. The paper studies a preferential attachment model in which an anomalous vertex v_tau arrives at time tau and, after arrival, attracts each new edge with an additional fixed probability beta/(2m+beta+delta). The model interpolates between ordinary PA and the superstar model. The authors derive exact recursions for the expected degree of the anomaly and of ordinary vertices (Proposition 1 and Eqs. (9)-(11)), prove almost-sure convergence of suitably rescaled degrees via martingale arguments (Section 3.3), and then give a heuristic derivation of the ordinary-vertex degree-distribution exponent in three regimes: late (tau = t - t^gamma), mid-way (tau = alpha t), and early (tau = t^gamma) arrival. The claimed exponents are 3+delta/m for late and mid-way anomalies and 3+(beta+delta)/m for an early anomaly. The heuristic formulas are compared with simulations in Figures 3-5.

Significance. The exact expectation formulas and the martingale convergence statements are clean and useful, and the model is a natural extension of the superstar model to a general arrival time. The almost-sure convergence results in Section 3.3 are a genuine contribution, as is the closed-form formula for the anomaly's mean degree. If the early-anomaly exponent claim were properly supported, the paper would be an interesting contribution to the study of change-point and anomaly effects in PA networks. However, the numerical support for the early-anomaly case does not test the claimed exponent, because the simulated tail is dominated by vertices born before the anomaly. Thus the central new phenomenon advertised in the abstract remains only a heuristic without valid finite-sample evidence.

major comments (2)
  1. [Section 4.3, Eq. (18), Figure 5] The derivation of Eq. (18) applies only to vertices born after tau = t^gamma, since the pre-tau fraction is vanishing. In the simulation of Figure 5 (t=50000, m=1, delta=0, beta=5, gamma approx 0.3615), the largest expected degree of a post-tau vertex is t^{m(1-gamma)/(2m+beta+delta)} approx 2.7. Consequently, every ordinary vertex of degree larger than about 3 was born before tau and follows the expected degree formula in Eq. (10), which produces the standard-PA tail k^{-(3+delta/m)} rather than Eq. (18). The tail shown in Figure 5 is therefore dominated by the pre-tau cohort, and the figure does not test the claimed early-anomaly exponent. The fixed-k limit may well be Eq. (18), but the paper needs either a simulation that isolates post-tau vertices, a parameter regime in which the post-tau expected degrees span a sufficiently large range, or a more explicit discussion of why the finite-t tail cannot be used to read off the fixed-k exponent.
  2. [Section 5] The explanation of Figure 5 attributes the right-deviation of the empirical tail to the oldest vertex's faster degree growth. This is not accurate. From Eq. (10), for every pre-tau vertex i with i < tau = t^gamma, the expected degree satisfies E[D_i(t)+delta] approx (m+delta)(t/tau)^{m/(2m+beta+delta)}(tau/i)^{m/(2m+delta)}, so the entire pre-tau cohort has expected degree larger than the maximum post-tau expected degree, which is only about t^{m(1-gamma)/(2m+beta+delta)}. Thus the outliers to the right in Figure 5 are not exclusively, or even mainly, the oldest vertex; they are the whole pre-tau population. The text in Section 5 should be corrected to state that the finite-t tail is generated by pre-tau vertices and therefore is not a valid comparison for Eq. (18).
minor comments (4)
  1. [Section 3.3] The phrase 'converges almost surely as t to infinity and tau to infinity' is imprecise, since tau is fixed as a model parameter. It should read 'for each fixed tau, as t to infinity', or the authors should specify that they consider a sequence with tau tending to infinity.
  2. [Section 4.4, Figure 5] For t=50000, the value tau=50 is only approximately t^gamma with gamma=0.3615; the exact value of 50000^{0.3615} is about 50.1. The caption should state whether tau is taken as floor(t^gamma) or as exactly 50.
  3. [Eq. (8)] The Stirling approximation in Eq. (8) is stated for fixed a, but it is later applied to exponents that depend on model parameters such as m/(2m+beta+delta). This is standard and harmless, but a brief note would improve rigor.
  4. [References] References [5] and [8] are given as arXiv preprints; if published versions exist, they should be cited instead of or in addition to the arXiv identifiers.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: expectations follow from model recursions, and the heuristic degree-distribution formulas introduce no fitted parameters; remaining issues are rigor/correctness, not circularity.

full rationale

The paper's central derivations are self-contained from the model definition. Proposition 1 (Eq. 4) solves the recursion (3) for E[D_tau(t)+delta], and the ordinary-vertex expectation formulas (9)-(11) are obtained by the same recursive approach applied to the stated attachment rule. No fitted parameter is later renamed as a prediction: the heuristic degree-distribution exponents in Eqs. (14), (17), and (18) are computed directly from the interval of vertex indices whose expected degree falls near k, using the already-derived expectation formulas. The comparison figures are simulations of the same model, so they are not independent validation, but neither are they fitted inputs; this is a methodological weakness, not circularity. There are self-citations ([5], [9], [11] involve the authors), but they are used for standard martingale convergence facts and as a source of a heuristic method, not as the sole justification of the paper's central claims. The manuscript itself flags the lack of a rigorous derivation (Section 6(2)) and admits the early-anomaly slope is steeper than simulations (Section 4.4, Figure 5); those are correctness and rigor concerns, not circular reductions. In particular, the early-anomaly tail in Eq. (18) may describe only post-tau vertices while the observed far tail is dominated by pre-tau vertices, as the skeptic notes, but this is an internal mathematical mismatch, not an assumption of the answer. Overall, the derivation chain does not reduce to its inputs by construction, so the circularity score is low.

Assumptions & free parameters 4 free parameters · 4 assumptions · 1 invented entities

The paper introduces one model parameter beta (anomaly attractiveness) and one structural parameter tau (arrival time); neither is fitted to data. The anomaly attachment rule (3) is a modeling postulate, not derived from first principles or calibrated. The degree-distribution results additionally depend on an unproved heuristic identification between mean degree and degree frequency, which the authors disclose. No external empirical benchmarks are used; simulations generate data from the same model, so the comparisons test internal consistency rather than real-world validity.

free parameters (4)
  • beta
    Anomaly attractiveness parameter in Eq. (3); an input chosen by the analyst, not fitted. The linear slope m beta/(m+beta+delta) and the early-anomaly exponent depend on it.
  • tau
    Anomaly arrival time, an input studied in three asymptotic regimes (late, mid-way, early); not fitted.
  • m
    Number of edges added per new vertex in the baseline PA model; input, not fitted.
  • delta
    Fitness shift in the PA rule; input, not fitted.
assumptions (4)
  • domain assumption Standard preferential attachment baseline: P(v_t,j -> v_i) = (D_i + delta)/(2m(t-1)+(t-1)delta+(j-1)) for t<tau.
    Adopted from [3,4,9]; the anomaly model modifies this rule after time tau.
  • domain assumption Anomaly attachment rule (Eq. 3): after tau, each new edge has extra weight (t-1)beta for the anomaly and standard PA weight for all other vertices.
    This is the paper's definition of an anomaly; the analysis proves properties of this model, not of an empirically validated anomaly process.
  • domain assumption Heuristic identification in Section 4: the fraction of vertices with degree near k equals the fraction of indices i whose expected degree E[D_i(t)+delta] lies in (k+delta-0.5, k+delta+0.5).
    Implicit concentration assumption, cited to [11]; the paper states in Section 6(2) that a rigorous derivation is open.
  • standard math Background probability tools: martingale convergence theorem, Stirling's formula, gamma identities.
    Used in Sections 3 and 5 without proof; standard in the PA literature.
invented entities (1)
  • Anomalous vertex v_tau with attractiveness beta
    purpose: Models a node that, after arrival, receives new edges with fixed extra probability plus standard PA; used to study structural effects of an anomaly.
    The anomaly is a model construct; no real-world dataset validates its behavior. The paper proposes anomaly detection as future work, so there is no external falsifiable handle yet.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Degrees in Preferential Attachment Networks with an Anomaly." pith.science (2026). https://pith.science/paper/MA5FGGNW

@misc{pith2026250503340,
  author       = {Pith},
  title        = {Pith review of: Degrees in Preferential Attachment Networks with an Anomaly},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MA5FGGNW}},
  note         = {Machine review of arXiv:2505.03340}
}
read the original abstract

We consider a preferential attachment model that incorporates an anomaly. Our goal is to understand the evolution of the network before and after the occurrence of the anomaly by studying the influence of the anomaly on the structural properties of the network. The anomaly is such that after its arrival it attracts newly added edges with fixed probability. We investigate the growth of degrees in the network, finding that the anomaly's degree increases almost linearly. We also provide a heuristic derivation for the exponent of the limiting degree distributions of ordinary vertices, and study the degree growth of the oldest vertex. We show that when the anomaly enters early, the degree distribution is altered significantly, while a late anomaly has minimal impact. Our analysis provides deeper insights into the evolution of preferential attachment networks with an anomalous vertex.

Figures

Figures reproduced from arXiv: 2505.03340 by the authors.

Figure 1
Figure 1. Examples of PA networks with an anomaly. Here t = 500, τ = 200, δ = 0, m = 1. which leads to pβ,t,j ≈ p in (3). Since the precise form of (3) is a little simpler, we choose to work with this parameterization instead to simplify the formulas [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. The degree of the anomaly as a function of time t. The parameters used are τ = 200, δ = 0, β = 2.0, m = 1. to the anomaly also through the PA mechanism, has increased the rate of growth (rather than, say, giving rise to an extra polynomial term as we conjectured at the beginning). To further explore the relation between Dτ (t) and the network size, we assume that t = aτ , a ≥ 1. By Stirling’s formula, Γ(t + a) Γ(t) … view at source ↗
Figure 3
Figure 3. 5 show the empirical and the theoretically predicted degree distribu￾tions for the PA network with the late anomaly, the mid-way anomaly, and the early anomaly, respectively. (a) m = 1, β = 5.0, δ = 0. (b) m = 4, β = 10.0, δ = 0 [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: The complementary cumulative degree distribution for PA network with mid￾way anomaly, parameters are t = 50000, τ = 25000, α = 0.5. The green line uses the formula (8.4.11) in [9, Chapter 8], multiplied by factor α β 2m+β+δ as in (17). The dashed blue line follows (17)…
Figure 5
Figure 5. Figure 5: The complementary cumulative degree distribution for PA network with early anomaly, parameters are t = 50000, τ = 50, γ = 0.3615. (8.4.11) in [9, Chapter 8] multiplied by the factor α β 2m+β+δ . Thus, our heuristic derivation correctly predicts the effect of a mid-way …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 11 canonical work pages

  1. [1]

    Banerjee, S., Bhamidi, S., Carmichael, I.: Fluctuation bounds for continuous time branchingprocessesandevolutionofgrowingtreeswithachangepoint.TheAnnals of Applied Probability33(4), 2919–2980 (2023)

  2. [2]

    Science 286(5439), 509–512 (1999)

    Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)

  3. [3]

    Berger, N., Borgs, C., Chayes, J., Saberi, A.: Asymptotic behavior and distribu- tional limits of preferential attachment graphs. Ann. Probab.42(1), 1–40 (2014)

  4. [4]

    In: SODA ’05: Proceedings of the sixteenth annual ACM-SIAM symposium on 16 Q

    Berger, N., Borgs, C., Chayes, J., Saberi, A.: On the spread of viruses on the inter- net. In: SODA ’05: Proceedings of the sixteenth annual ACM-SIAM symposium on 16 Q. Liang et al. Discrete algorithms. pp. 301–310. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2005)

  5. [5]

    Bet, G., Bogerd, K., Castro, R.M., van der Hofstad, R.: Detect- ing a late changepoint in the preferential attachment model (2023), https://arxiv.org/abs/2310.02603

  6. [6]

    The Annals of Applied Probability 28(1), 35–78 (2018)

    Bhamidi, S., Jin, J., Nobel, A.: Change point detection in network models: Prefer- ential attachment and long range dependence. The Annals of Applied Probability 28(1), 35–78 (2018)

  7. [7]

    The Annals of Applied Probability25(5), 2462–2502 (2015)

    Bhamidi, S., Steele, J.M., Zaman, T.: Twitter event networks and the Superstar model. The Annals of Applied Probability25(5), 2462–2502 (2015)

  8. [8]

    Cirkovic, D., Wang, T., Zhang, X.: Likelihood-based inference for random networks with changepoints (2024), https://arxiv.org/abs/2206.01076

Show all 14 references
  1. [9]

    Volume 1, Cambridge Series in Statistical and Probabilistic Mathematics, vol

    Hofstad, R.v.d.: Random Graphs and Complex Networks. Volume 1, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 34. Cambridge University Press, Cambridge (2017)

  2. [10]

    In: International Conference on Learning Representations (ICLR) (2017)

    Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. In: International Conference on Learning Representations (ICLR) (2017)

  3. [11]

    Nieuw archief voor wiskunde5(24), 103–113 (2023)

    Litvak, N.: Randomness and structure in complex networks. Nieuw archief voor wiskunde5(24), 103–113 (2023)

  4. [12]

    IEEE Transactions on Knowledge & Data Engineering35(12), 12081–12094 (Dec 2023)

    Liu, Y., Pan, S., Wang, Y.G., Xiong, F., Wang, L., Chen, Q., Lee, V.C.: Anomaly detection in dynamic graphs via transformer. IEEE Transactions on Knowledge & Data Engineering35(12), 12081–12094 (Dec 2023)

  5. [13]

    Ruiz, D., Finke, J.: Lyapunov–based anomaly detection in preferential attachment networks. Int. J. Appl. Math. Comput. Sci.29(2), 363–373 (Jun 2019)

  6. [14]

    In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19

    Zheng, L., Li, Z., Li, J., Li, Z., Gao, J.: Addgraph: Anomaly detection in dynamic graph using attention-based temporal gcn. In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19. pp. 4419–4425. International Joint Conferences...

Pith tools

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