{"id":"3fe3e1c5-07b7-44bd-885d-3ddc2b590dc4","arxiv_id":"2505.09713","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"The paper attempts to derive finite-time message-spreading distributions for Norros-Reittu graphs, but the Poisson-binomial derivation is invalid because success probabilities depend on the random set of informed nodes.","lead":"This paper claims to derive exact formulas for how many nodes have received a message by a fixed time in a Norros-Reittu preferential attachment graph. The derivation is unsound: it treats dependent spreading events as independent and contains an error in the ratio distribution.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Poisson-binomial representation fails: p_{k+1} in (8) depends on the random set S_k, making transmission indicators correlated, so the claimed pmf (9) and Lemma 4 are not the true laws.","rationale":"The paper aims to derive exact finite-time pmfs for the number of informed nodes in the Norros–Reittu model and for the ratio #S_K*/N_K*. For the central claim to hold, the per-step transmission indicators must be independent Bernoulli trials with fixed (Λ-conditional) success probabilities, so that #S_k has the Poisson-binomial law ψ(i,j,k) of (6) and the Poisson mixing in (9) is legitimate. That is the load-bearing condition, and it is asserted rather than proved: Section 3.2 infers independence of transmissions from independence of edge creation across steps. But Lemma 2 shows the success probability at step k+1 depends on the random set S_k through (8); because S_k is determined by previous transmissions, the indicators are positively correlated given Λ, and the unconditional law of #S_k is a trajectory-mixture, not a product measure. The k=2, Λ≡1 computation in the concrete test demonstrates that eq. (9) is numerically false in the simplest instance of the model, so this is a correctness failure of the central formulas, not merely a missing argument. Lemma 4 inherits the error and has an additional K* = 0 edge-case mistake (the term e^{-λT*} should carry the factor 1{x ≥ 1}). I credit the parts that are sound: Lemma 2 is correct as a conditional statement; mixing over the Poisson step count K* is in principle fine since the jump chain and the clock are independent; Corollary 1 is correct exactly because along the all-failure trajectory S_k = {0} is deterministic, so the successive conditional probabilities multiply, which incidentally pinpoints the nature of the failure elsewhere. The simulation does not validate (9), since it plots only averages of #S_k/N_k over 20 runs, and Lemma 1 is borrowed from the authors' unpublished preprint, limiting independent verification. The reader's weakest_assumption identifies the same mechanism, and I agree with the REJECT verdict; my read does not move it.","tokens_in":7323,"tokens_out":23763,"duration_ms":199599,"concrete_test":"Analytic check at k = 2 with Λ_i ≡ 1, which needs no simulation. Compute p_1 = 1 - e^{-1/2}; given S_1, p_2 = 1 - e^{-|S_1|/3}; the true law is P(#S_2 = 1) = e^{-5/6} ≈ 0.4346 and P(#S_2 = 3) = (1-e^{-1/2})(1-e^{-2/3}) ≈ 0.1915, with Cov(I_1, I_2) ≈ 0.0485 > 0. The paper's eq. (6)+(9) instead claims a Poisson-binomial law with one fixed p_2: ψ(1) = e^{-1/2}(1-p_2) and ψ(3) = (1-e^{-1/2})p_2. Choosing p_2 = 1-e^{-1/3} matches ψ(1) but gives ψ(3) ≈ 0.1116 ≠ 0.1915; choosing p_2 = 1-e^{-2/3} matches ψ(3) but gives ψ(1) ≈ 0.3114 ≠ 0.4346; no single p_2 reconciles both, refuting the Poisson-binomial representation behind (9) and Lemma 4. A 10^6-run Monte Carlo of the exact process (λ = 1, T* = 5, Λ ≡ 1) comparing the empirical pmf of #S_K* with (9) would confirm the discrepancy across all i.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing premise is the Poisson-binomial representation asserted in Section 3.2: the transmission indicators I_k = 1{#S_k = #S_{k-1}+1} are independent Bernoulli trials with parameters p_1,...,p_k, so P(#S_k = i | Λ) = ψ(i,j,k) in (6), mixed over the Poisson step count in (9) and used in Lemma 4. This premise is false: p_{k+1} in (8), p_{k+1} = 1 - ∏_{w∈S_k} exp(-Λ_w Λ_{k+1}/L_{k+1}), is conditional on the random set S_k and hence a random variable; because a success enlarges S_k, every later success probability increases, so the indicators are positively correlated given Λ. The unconditional pmf of #S_k is a mixture of products over infection trajectories, not the product measure ψ(i,j,k), and no fixed choice of the p's repairs (9). An exact 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, with Cov(I_1,I_2) ≈ 0.0485 > 0, whereas (6) would require ψ(1) = (1-p_1)(1-p_2) and ψ(3) = p_1 p_2 for a single fixed p_2; no p_2 matches both values. Lemma 4 inherits this error and also sets the K* = 0 term to e^{-λT*} for all x, although #S_0/N_0 = 1 requires x ≥ 1; for x < 1 the formula assigns positive mass to an impossible event. The Figure 2 simulation plots only 20-run averages of #S_k/N_k and never tests (9); Lemma 1 rests on the authors' unpublished preprint [11]. Credit where due: Lemma 2 is correct as a conditional statement, the Poisson mixing over K* is sound in principle, and Corollary 1 holds because the all-failure path keeps S_k = {0} deterministic so the conditional probabilities genuinely multiply; the failure is specific to the general i ≥ 2 case that forms the paper's central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":7853,"tokens_out":5111,"duration_ms":50505,"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":[{"comment":"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.","section":"Section 3.2, Eqs. (8)–(9)"},{"comment":"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).","section":"Section 3.2, Eq. (9)"},{"comment":"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.","section":"Lemma 4"},{"comment":"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.","section":"Lemma 1 and Section 2"}],"minor_comments":[{"comment":"The title contains a typo: 'Evoving' should be 'Evolving'. In the abstract, 'nodes obtained the message' should read 'nodes having received the message'.","section":"Title and Abstract"},{"comment":"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.","section":"Equation (6)"},{"comment":"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].","section":"Sections 2 and 3"},{"comment":"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.","section":"Section 4, Figure 2"},{"comment":"The word 'propogated' in the Conclusions should be 'propagated'.","section":"Conclusions"}],"recommendation":"reject","confidential_remarks":"The paper appears to be an early draft: it relies on an unpublished preprint for its key lemma, and the main derivation contains a fundamental statistical error (treating state-dependent success indicators as independent Bernoulli trials). The counterexample at k=2 is simple and decisive; correcting it would require a substantially different analysis and not merely local revisions. The editors may also wish to note the incomplete citation practice regarding the unpublished source of Lemma 1."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nYou asked for a take on arXiv:2505.09713. The short version: the paper's central pmf claim is wrong, and the error is not a technical gap but a misused independence assumption. The transmission indicators are not independent Bernoulli trials: p_{k+1} in (8) depends on the random set S_k, so the unconditional law of #S_k is a mixture over infection trajectories, not the Poisson-binomial product in (6). The claimed pmf (9) and Lemma 4 inherit this error. Lemma 4 also adds e^{-λT*} for all x, but when K*=0 the ratio is 1, so that term belongs only for x≥1.\n\nA concrete two-step check makes it clear. With all capacities Λ_i = 1, p1 = 1 - e^{-1/2}. If step 1 succeeds, S_1 has size 2 and p2 = 1 - e^{-2/3}; if it fails, S_1 size 1 and p2 = 1 - e^{-1/3}. Thus P(#S_2 = 1) = e^{-5/6} and P(#S_2 = 3) = (1-e^{-1/2})(1-e^{-2/3}). No single fixed p2 plugged into (6) can match both, so the Poisson-binomial representation is not just approximate; it is structurally inconsistent with the process.\n\nWhat the paper does well: Lemma 2 derives the conditional success probability (8) correctly for the Norros-Reittu model, and Corollary 1 gives the correct all-failure probability because S_k stays deterministic. The Poisson mixing over K* is standard and sound in principle. The simulation study, however, plots only 20-run averages of the ratio and never tests any of the pmf formulas, so it provides no support for the main claims. The reliance on the authors' unpublished preprint [11] for Lemma 1 adds a verification burden that this paper does not meet.\n\nIs anything salvageable? The conditional success probability and the all-failure result could be part of a sound paper if the authors replaced the Poisson-binomial step with a correct recursive formulation (or an explicit sum over infection trajectories). That is a substantial rewrite, not a local fix. As it stands, the central result is demonstrably false, so I would not send it to peer review. If it crosses your desk, desk reject with a brief note pointing to the two-step counterexample and the K*=0 issue.\n\nBest,\n[Your name]","headline":"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.","tokens_in":8385,"tokens_out":4852,"would_cite":false,"duration_ms":45088,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","60E05","60G55"],"pacs":[],"model":"deepseek-v4-flash","headline":"Formula gives exact odds for informed nodes in growing random graphs","keywords":["Norros-Reittu model","preferential attachment","information spreading","Poisson binomial distribution","Poisson process","random graph evolution","message propagation","heavy-tailed capacities"],"falsifier":"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.","tokens_in":7147,"feed_emoji":"🕸️","tokens_out":8946,"duration_ms":70685,"temperature":0.7,"pith_summary":"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.","feed_headline":"Formula gives exact odds for informed nodes in growing random graphs","feed_subtitle":"Derives the probability that a given fraction of nodes carries a message by time T* in the Norros-Reittu network.","key_machinery":"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.","core_discovery":"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\n$$\\mathbb{P}\\{\\#S_{K^*} = i \\mid \\Lambda\\} = $e^{{-\\lambda T^*}}$ \\sum_{k=i}^{\\infty} \\frac{(\\$\\lambda$ T^*)^k}{k!}\\, \\psi(i,j,k),$$\nwhere $\\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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the Norros-Reittu conditionally Poissonian graph process that the paper evolves, supplying the edge-mean formula (5).","marker":"[1]"},{"why":"The linear preferential attachment model for which Lemma 1 was originally proved and which the paper adapts to Norros-Reittu success probabilities.","marker":"[2]"},{"why":"Companion Poisson preferential attachment model cited to justify treating the number of new edges as random.","marker":"[3]"},{"why":"Supplies Lemma 1, the Poisson-weighted identity that converts the pmf at the random time $K^*$ into a mixture of fixed-step pmfs.","marker":"[11]"},{"why":"Gives the definition and theory of the Poisson binomial distribution used to express $\\psi(i,j,k)$.","marker":"[12]"}],"fun_headline_variants":["Exact odds for message spread in Norros-Reittu graphs","Probability laws for informed nodes in evolving random graphs","Precise formulas for info propagation in growing networks","Norros-Reittu graph: exact spreading probabilities derived","Exact pmf for informed nodes in random evolving graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Exact odds for message spread in Norros-Reittu graphs","Probability laws for informed nodes in evolving random graphs","Precise formulas for info propagation in growing networks","Norros-Reittu graph: exact spreading probabilities derived","Exact pmf for informed nodes in random evolving graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000157,"raw_usage":{"total_tokens":1190,"prompt_tokens":885,"completion_tokens":305,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":501,"completion_tokens_details":{"reasoning_tokens":225}},"tokens_in":501,"tokens_out":305,"duration_ms":2939,"temperature":1.0,"reasoning_tokens":225,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:27:29.112108+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The linear preferential attachment model for which Lemma 1 was originally proved and which the paper adapts to Norros-Reittu success probabilities."},{"cited_title":"Methodol Comput Appl Probab 25, 8 (2023).https://doi.org/10.1007/s11009-023-09997-y","cited_arxiv_id":null,"evidence_quote":"Companion Poisson preferential attachment model cited to justify treating the number of new edges as random."},{"cited_title":"Submission to e-Journal Reliability: Theory and Applications (2024)","cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 1, the Poisson-weighted identity that converts the pmf at the random time $K^*$ into a mixture of fixed-step pmfs."}],"review_version":1}