Pith. sign in

REVIEW 4 major objections 5 minor 12 references

Information Spreading in Random Graphs Evoving by Norros-Reittu Model

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

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

Pith's one-line read Formula gives exact odds for informed nodes in growing random graphs

desk verdict The central pmf is wrong: transmission indicators are correlated because p_{k+1} depends on S_k; the paper's one correct lemma (conditional success probability) does not rescue it. read the letter →

arxiv 2505.09713 v1 pith:C7R7OAHQ submitted 2025-05-14 math.ST math.PRstat.TH

N.M.Markovich , D.V.Osipov This is my paper · ORCID
classification math.STmath.PRstat.TH MSC 05C8060E0560G55
keywords Norros-ReittumodelpreferentialattachmentinformationspreadingPoissonbinomialdistributionprocessrandomgraphevolutionmessagepropagationheavy-tailedcapacities
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 aims to give exact finite-time probability laws for the spread of a single message in a random graph that grows by the Norros-Reittu preferential attachment rule, where each new node forms a Poisson-distributed number of edges to existing nodes. It derives the probability mass function of the number of informed nodes at a fixed time $T^*$, the total number of nodes, and the distribution function of their ratio. The formulas are expressed through a Poisson-binomial law whose per-step success probabilities are explicit products over the informed set. If the formulas hold, the spread of a message in this graph model becomes a closed-form calculation rather than a simulation-only quantity.

What carries the argument

The load-bearing object is the Poisson-binomial model for the informed-set size: success at step $k+1$ is declared when the new node connects to at least one informed node, which happens with probability $p_{k+1}=1-\prod_{w\in S_k} e^{-\Lambda_w\Lambda_{k+1}/L_{k+1}}$. The paper treats the sequence of successes as independent Bernoulli trials, so $\#S_k$ has the Poisson-binomial pmf $\psi(i,j,k)$ of equation (6). A second ingredient is the Poisson clock identity of Lemma 1: conditioning on the final time $T^*$ replaces the pmf at the random step $K^*$ by a Poisson-weighted average of pmfs at fixed steps $k\ge i$. Together they convert the random-time problem into a summation over deterministic steps.

What would settle it

Simulate the Norros-Reittu process with a fixed capacity sequence $\Lambda$, record $\#S_k$ at every step for many independent runs conditioned on the same $\Lambda$, and compare the empirical pmf of $\#S_k$ with $\psi(i,j,k)$ computed from (6) using the success probabilities (8). A systematic deviation beyond sampling error, growing with $k$, would show that the dependence between successive informed sets breaks the Poisson-binomial assumption; the same comparison can be made for the ratio in Lemma 4.

Watch

Extended reading notes

Core claim

The central claim is that, conditionally on the node-capacity sequence $\Lambda$, the number of nodes that have received the message by the random evolution step $K^* = \nu(T^*)$ has probability mass function $$\mathbb{P}\{\#S_{K^*} = i \mid \Lambda\} = $e^{{-\lambda T^*}}$ \sum_{k=i}^{\infty} \frac{(\$\lambda$ T^*)^k}{k!}\, \psi(i,j,k),$$ where $\psi$ is the Poisson-binomial pmf of equation (6), assembled from per-step success probabilities $p_{k+1} = 1 - \prod_{w \in S_k} e^{-\Lambda_w \Lambda_{k+1}/L_{k+1}}$ (equation (8)). The paper also claims the distribution function of the ratio $\#S_{K^*}/N_{K^*}$ is the expression in Lemma 4, and that $\#S_k$ itself follows a Poisson-binomial law with those success probabilities. The number of nodes $N_{K^*}$ is a shifted Poisson variable with parameter $\lambda T^*$, because exactly one node is added at each tick of the Poisson clock.

Load-bearing premise

The argument stands on the assumption that whether the message reaches the new node at each step is an independent coin flip with a fixed probability for that step, even though the probability is computed from the random set of already-informed nodes; if the steps are not independent in this way, the Poisson-binomial formula no longer gives the true distribution.

Editorial extensions

If this is right

  • For every fixed observation horizon $T^*$, the probability of any informed-node count $i$ is a computable sum once the capacity sequence $\Lambda$ is given, with no asymptotic approximation.
  • The probability that the message has not spread at all by step $K$ is the explicit formula $e^{-\Lambda_0\sum_{k=1}^K \Lambda_k/L_k}$ from Corollary 1, giving a direct analytical handle on early-stage failure.
  • Since $N_{K^*}$ is a shifted Poisson variable with parameter $\lambda T^*$, interval estimates for the total graph size at time $T^*$ follow from standard Poisson quantiles.
  • The distribution function of the informed fraction $\#S_{K^*}/N_{K^*}$ in Lemma 4 permits direct comparison of spreading speed for different tail indices $\tau$, as the simulation section illustrates.

Reading between the lines

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

  • If the independence assumption held, the same Poisson-binomial machinery would extend to other transmission rules, such as requiring at least two contacts or a threshold number of edges, by changing only the success probability (8).
  • The stabilization of the informed fraction seen in the simulations suggests a possible deterministic limit as the graph grows; the paper's formulas could be used to test whether that limit solves a simple mean-field balance equation.
  • A natural generalization is a time-varying clock intensity $\lambda(t)$; then the Poisson weighting in Lemma 1 would become an inhomogeneous Poisson weighting, with the present formulas as the homogeneous special case.
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

4 major / 5 minor

Summary. The paper studies a message-spreading process on the Norros–Reittu preferential attachment graph, where new nodes arrive according to a Poisson process of intensity λ and connect to existing nodes with Poisson numbers of edges. For a fixed time T*, the authors claim to derive the conditional probability mass function of the number of informed nodes #S_K*, the pmf of the total number of nodes N_K*, and the distribution function of the ratio #S_K*/N_K*. The derivation rests on a success probability p_{k+1} (Lemma 2), a Poisson-binomial representation of the success indicators (Section 3.2), and a mixing over the Poisson number of steps K* (Lemma 1, cited from the authors' unpublished preprint [11]). A simulation study illustrates the average ratio #S_k/N_k.

Significance. If the main results were correct, they would provide exact finite-time distributional formulae for information spreading in a well-known evolving random graph model, which would be a useful contribution to the applied probability literature. The paper does contain a correct conditional success probability (Lemma 2), a correct pmf for the total number of nodes (Lemma 3), and a sound Poisson-mixing idea. However, the central claim is not established: the Poisson-binomial representation is invalid because the success probabilities depend on the random set of informed nodes, and the manuscript does not supply a proof of the key Lemma 1 on which the main pmf rests. As a result, equations (9) and Lemma 4, which are the paper's principal outputs, are not derived correctly.

major comments (4)
  1. [Section 3.2, Eqs. (8)–(9)] The assertion that the sequence of successes forms a Poisson binomial distribution model is false. The probability p_{k+1} in (8) is explicitly conditional on the random set S_k, so p_{k+1} is a random variable rather than a fixed parameter, and the indicators I_k = 1{#S_k = #S_{k-1}+1} are not independent given Λ. A concrete check at k=2 with Λ_i ≡ 1 gives P{#S_2=1} = e^{-5/6} ≈ 0.4346 and P{#S_2=3} = (1-e^{-1/2})(1-e^{-2/3}) ≈ 0.1915, while a Poisson-binomial law with fixed p_1,p_2 would require (1-p_1)(1-p_2) = 0.4346 and p_1 p_2 = 0.1915; no single p_2 satisfies both. Consequently, the substitution of ψ(i,j,k) for P{#S_k=i|Λ} in (9) is not valid, and Lemma 4 inherits this error.
  2. [Section 3.2, Eq. (9)] Even if the success indicators were independent, replacing the conditioning on G_{k-1} in Lemma 1 by conditioning on Λ is unjustified. Lemma 1 states a pmf conditional on the full graph history G_{k-1}; the quantity P{#S_k=i|Λ} requires averaging over all graphs compatible with Λ, not simply inserting ψ(i,j,k) into the Poisson mixture. This is an additional, independent gap in the derivation of (9).
  3. [Lemma 4] The distribution function in Lemma 4 includes the term e^{-λT*} for all x, but when K*=0 one has #S_0/N_0 = 1/1 = 1, so this contribution should appear only for x ≥ 1. For x < 1, the displayed formula assigns positive probability to the impossible event #S_K*/N_K* ≤ x, and for x ≥ 1 the event is certain, so the formula cannot be correct as written.
  4. [Lemma 1 and Section 2] The central pmf structure (6) is taken from the authors' unpublished preprint [11] and appears to have been proved for the linear PAM of [2], not for the Norros–Reittu model. The manuscript neither proves Lemma 1 nor demonstrates that its form carries over to the Norros–Reittu model with success probabilities (8). Since equations (9) and Lemma 4 depend entirely on this external, unverified result, the main claim of the paper is not self-contained and cannot be checked from the manuscript alone.
minor comments (5)
  1. [Title and Abstract] The title contains a typo: 'Evoving' should be 'Evolving'. In the abstract, 'nodes obtained the message' should read 'nodes having received the message'.
  2. [Equation (6)] The notation ∑_{c,k,i-1} in (6) is undefined, and the role of j in ψ(i,j,k) is not explained. The summation convention for the Poisson-binomial terms should be stated explicitly.
  3. [Sections 2 and 3] The manuscript refers to both [2] and [11] as sources of Lemma 1 without clarifying which model the lemma was originally proved for. This is confusing because Section 2 says the lemma was proved for the linear PAM in [2], while the citation is to unpublished [11].
  4. [Section 4, Figure 2] The simulation study reports only 20-run averages of #S_k/N_k and never compares the empirical distribution of #S_K*/N_K* with the formula in Lemma 4, so it does not validate the paper's main theoretical claim. Error bars or a distributional comparison would be needed.
  5. [Conclusions] The word 'propogated' in the Conclusions should be 'propagated'.

Circularity Check

3 steps flagged · score 6.0 of 10

Central pmf (9) and Lemma 4 reduce to the Poisson-binomial ansatz imported from the authors' unpublished preprint [11]; Section 3.2 asserts the PB model rather than deriving it from the Norros-Reittu dynamics.

  1. self citation load bearing [Section 2, Lemma 1 and Section 3.2, eq. (9)]
    "Our achievements will be based on the following lemma proved for the linear PAM proposed in [2]. Lemma 1. [11] The conditional pmf of #S_k ... = ψ(i,j,k), (6) ... and success probabilities p_1,...,p_k correspond to the PAM proposed in [2]."

    The manuscript's central formula (9) is introduced by 'From Lemma 1 we have' and directly uses ψ(i,j,k) from (6). Lemma 1 is attributed to [11], an unpublished submission by one of the present authors, and is not proved in this paper. Thus the claimed pmf of #S_K* is not derived here from the Norros-Reittu edge-generation mechanism; it is taken as input from the self-cited preprint. The simulation section never compares the empirical distribution with (9), so the citation is load-bearing rather than independently verified support.

  2. ansatz smuggled in via citation [Section 3.2, "Probability mass function of S_k"]
    "The success probability p_{k+1} at step k+1 is given by (8). Since edge creation is independent across steps, the sequence of successes {p_k} forms a Poisson binomial distribution model. Further analysis is based on the arguments of [11]."

    The Poisson-binomial structure is asserted in the same paragraph that defers to [11]. Equation (8) defines p_{k+1} conditionally on the random set S_k, so the unconditional success indicators are not shown to be independent Bernoulli trials; the paper simply states that they form a Poisson binomial model. Lemma 1's ψ is exactly that product-measure ansatz, so the eventual pmf (9) inherits the ansatz from the authors' prior work rather than from a proof in this paper.

1 more flagged steps
  1. other [Section 3.2, eq. (9)]
    "From Lemma 1 we have that the pmf of S_k, k≥1, for the maximum number of evolution steps K* within a fixed time T* is defined as follows: P{#S_K*=i|Λ}=e^{-λT*} Σ_{k=i}^∞ (λT*)^k/k! P{#S_k=i|Λ} (9) where P(#S_k=i|Λ) substitutes P{#S_k=i|G_{k-1}} in (6),(7)."

    Equation (9) is not an independent derivation; it is Lemma 1 restated after substituting the Norros-Reittu success probabilities (8) into the imported ψ. The words 'substitutes ... in (6),(7)' show that the final pmf is, by construction, the same Poisson-binomial object supplied by [11], with only the p_k values changed. Lemma 4 then uses this same ψ, so the claimed distribution of #S_K*/N_K* reduces to the cited ansatz.

full rationale

The paper is only partially circular. Lemma 2 genuinely derives the conditional success probability p_{k+1} in (8), Lemma 3 is a standard Poisson-process calculation, and the Poisson mixing over K* in (9) is a sound conditioning step. However, the central object of the paper—the pmf of #S_K* and the distribution of #S_K*/N_K* in Lemma 4—is not derived from the Norros-Reittu dynamics in this manuscript. Equation (9) is introduced by 'From Lemma 1 we have', and Lemma 1 is cited from [11], an unpublished submission by one of the authors. The formula ψ(i,j,k) is a Poisson-binomial product measure, and Section 3.2 asserts 'the sequence of successes {p_k} forms a Poisson binomial distribution model' immediately before saying 'Further analysis is based on the arguments of [11]'. Thus the claimed prediction reduces to the same PB ansatz that [11] supplies. The simulation section only plots 20-run averages of #S_k/N_k and never compares the empirical distribution with (9), so the self-citation is not independently tested here. Because Lemma 2 provides new content and the mixing over the Poisson clock is independently justified, the circularity is partial: the central pmf is the input structure, while the success probabilities and time mixing are separately obtained.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The derivation rests on the Norros-Reittu edge-generation rule, the regularly varying capacity distribution, the Poisson clock for node arrivals, and Lemma 1 borrowed from the authors' own preprint [11]. No constants are fitted to data; the external parameters are λT* and τ. The most fragile item is the independence assumption for the success indicators, listed as an axiom, which is actually violated by the model.

free parameters (2)
  • λT* (Poisson clock rate times horizon)
    All pmfs depend only on this product; the paper does not specify or estimate it, so it acts as an external model scale.
  • τ (tail index of capacity distribution) = 1.5, 2.5, 3.5 in simulations
    Chosen by hand for simulations; not fitted to data. The theoretical pmfs are conditional on Λ and do not fix a single τ.
assumptions (6)
  • domain assumption The graph follows the Norros-Reittu conditionally Poissonian edge rule: at step k+1, the number of edges between new node k+1 and old node w is Poisson with mean Λ_w Λ_{k+1}/L_{k+1}, independently for different w, and old edges are deleted with probability 1 - L_k/L_{k+1}.
    Stated in Section 2 from [1]; the success probability (8) is derived from this rule.
  • domain assumption Node arrivals form a Poisson process with rate λ, so K* = ν(T*) is Poisson with mean λT*.
    Used in (3), Lemma 3, and in the Poisson mixture (9).
  • domain assumption Capacities Λ_i are independent, strictly positive, regularly varying with tail P{Λ_1>x}=x^{-τ+1}ℓ(x).
    Equation (4) in Section 2; the theoretical formulas are conditional on Λ, so τ enters only through the simulation.
  • domain assumption Lemma 1 from the authors' own preprint [11] gives the conditional pmf ψ(i,j,k) for #S_k.
    Quoted in Section 2 and reused in Section 3; it is not proved here and [11] is not published or machine-checked.
  • ad hoc to paper The success indicators I_k are independent Bernoulli trials with probabilities p_k from (8).
    This is asserted in Section 3.2 and is false because p_{k+1} depends on the random set S_k. It is the main logical gap in the paper.
  • domain assumption Removal of old edges and self-loops does not affect message propagation (Remark 1).
    True under the paper's transmission rule, which only counts edges from a new node to already informed nodes.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Information Spreading in Random Graphs Evoving by Norros-Reittu Model." pith.science (2026). https://pith.science/paper/C7R7OAHQ

@misc{pith2026250509713,
  author       = {Pith},
  title        = {Pith review of: Information Spreading in Random Graphs Evoving by Norros-Reittu Model},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/C7R7OAHQ}},
  note         = {Machine review of arXiv:2505.09713}
}
abstract

The paper is devoted to the spreading of a message within the random graph evolving by the Norros-Reittu preferential attachment model. The latter model forms random Poissonian numbers of edges between newly added nodes and existing ones. For a pre-fixed time $T^*$, the probability mass functions of the number of nodes obtained the message and the total number of nodes in the graph, as well as the distribution function of their ratio are derived. To this end, the success probability to disseminate the message from the node with the message to the node without message is proved. The exposition is illustrated by the simulation study.

Figures

Figures reproduced from arXiv: 2505.09713 by the authors.

Figure 1
Figure 1. The evolution of a network generated using the Norros-Reittu model [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. The average value of #𝑆𝑘/𝑁𝑘 against 𝑁𝑘 for 20 repetitions of graph evolution by the Norros-Reittu PAM: on the left side − 𝑁0 = 10 and #𝑆0 ∈ {1, 5, 10}; in the middle − 𝑁0 = 50 and #𝑆0 ∈ {1, 5, 10}; on the right − 𝑁0 = 100 and #𝑆0 ∈ {1, 5, 10}, where the first line is responsible for 𝜏 = 1.5, the second line for 𝜏 = 2.5, and the third line for 𝜏 = 3.5. ∘ Impact of initial graph size (𝑁0): Larger 𝑁0 values amplify the… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 7 canonical work pages

  1. [11]

    Submission to e-Journal Reliability: Theory and Applications (2024)

    Markovich, N.M.: Spreading of a limited lifetime information in networks evolved by preferential attachment. Submission to e-Journal Reliability: Theory and Applications (2024)

    work page 2024

  2. [2]

    Wan, P., Wang, T., Davis, R.A., Resnick, S.I.: Are extreme value estimation methods useful for network data? Extremes, vol. 23, pp. 171–195. (2020)

    work page 2020

  3. [1]

    Advances in Applied Probability, 38(1), 59–75

    Norros, I., Reittu, H.: On a conditionally poissonian graph process. Advances in Applied Probability, 38(1), 59–75. DOI: 10.1239/aap/1143936140. (2006)

    arXiv 2006

  4. [3]

    Methodol Comput Appl Probab 25, 8 (2023).https://doi.org/10.1007/s11009-023-09997-y

    Wang, T., Resnick, S.: Poisson Edge Growth and Preferential Attachment Networks. Methodol Comput Appl Probab 25, 8 (2023).https://doi.org/10.1007/s11009-023-09997-y

    work page doi:10.1007/s11009-023-09997-y 2023

  5. [4]

    In Proceedings of the 25th ACM symposium on Principles of dis- tributed computing (PODC ’06), ACM, New York, USA 113–122

    Mosk-Aoyama, D., Shah, D.: Computing separable functions via gos- sip. In Proceedings of the 25th ACM symposium on Principles of dis- tributed computing (PODC ’06), ACM, New York, USA 113–122. DOI: 10.1145/1146381.1146401. (2006)

    arXiv 2006

  6. [5]

    In Proceedings of the 29th ACM symposium on Principles of distributed computing (PODC’10), ACM, New York, USA

    Censor-Hillel, K., Shachnai, H.: Partial Information Spreading with Appli- cation to Distributed Maximum Coverage. In Proceedings of the 29th ACM symposium on Principles of distributed computing (PODC’10), ACM, New York, USA. 161–170. DOI: 10.1145/1835698.1835739 (2010)

    arXiv 2010

  7. [6]

    Physical Review X, 13(4), 041054

    Patwardhan, S., Rao, V.K., Fortunato, S., Radicchi, F.: Epidemic Spreading in Group-Structured Populations. Physical Review X, 13(4), 041054. DOI: 10.1103/PhysRevX.13.041054 (2023) 12 N. M. Markovich, D. V. Osipov

    work page doi:10.1103/physrevx.13.041054 2023

  8. [7]

    Contagion dynamics in time-varying metapopulation networks with node's activity and attractiveness

    Zeng, L., Tang M., Liu, Y., Yeop Yang, S., Do, Y.: Contagion dynamics in time-varying metapopulation networks with node’s activity and attractive- ness. arXiv:2311.13856v1 [physics.soc-ph] (2023)

    work page Pith review arXiv 2023

Show all 12 references
  1. [8]

    arXiv:2502.04225v1 (2025)

    Pang, G., Pardoux, E., Velleret, A.: Stochastic SIR model with indi- vidual heterogeneity and infection-age dependent infectivity on large non- homogeneous random graphs. arXiv:2502.04225v1 (2025)

    2025 arXiv

  2. [9]

    Foundations and Trends in Networking 3(1), 1–125 (2008)

    Shah, D.: Gossip algorithms. Foundations and Trends in Networking 3(1), 1–125 (2008)

    2008

  3. [10]

    Jessen, A.H., Mikosch, T.: Regularly varying functions. Publ. Inst. Math. (Beograd) (N.S.), 80, 171–192. (2006)

    2006

  4. [12]

    Tang, W., Tang, F.: The Poisson Binomial Distribution— Old & New. Statist. Sci. 38(1) 108–119. DOI: 10.1214/22-STS852. (2023)

    2023 doi

Pith tools

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