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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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}}$.
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
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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.
- [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)
- [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.
- [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.
- [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.
- [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
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
free parameters (4)
- beta
- tau
- m
- delta
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.
- 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.
- 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).
- standard math Background probability tools: martingale convergence theorem, Stirling's formula, gamma identities.
invented entities (1)
-
Anomalous vertex v_tau with attractiveness beta
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 from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Banerjee, S., Bhamidi, S., Carmichael, I.: Fluctuation bounds for continuous time branchingprocessesandevolutionofgrowingtreeswithachangepoint.TheAnnals of Applied Probability33(4), 2919–2980 (2023)
work page 2023
-
[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)
work page 1999
-
[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)
work page 2014
-
[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)
work page 2005
-
[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
arXiv 2023
-
[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)
work page 2018
-
[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)
work page 2015
-
[8]
Cirkovic, D., Wang, T., Zhang, X.: Likelihood-based inference for random networks with changepoints (2024), https://arxiv.org/abs/2206.01076
arXiv 2024
Show all 14 references
-
[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)
2017
-
[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)
2017
-
[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)
2023
-
[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)
2023
-
[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)
2019
-
[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...
2019
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.