{"id":"307bd632-a1a0-40d4-a45a-87593c195936","arxiv_id":"1908.04510","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"In a linear preferential attachment graph, the number of common neighbors of two fixed nodes converges to a finite limit for mild preferential attachment, grows logarithmically at a critical parameter, and grows as a power law for strong preferential attachment.","lead":"This paper derives how the number of common friends between two nodes grows in a preferential attachment network model. The result shows a phase transition: the count stays bounded, grows logarithmically, or grows as a power law depending on a model parameter.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Inequality (4.11), the unproved lower bound on Q_n, is load-bearing for the δ=0 and δ<0 regimes; supply a proof or the phase-transition rates are unsupported.","rationale":"The reader identifies exactly the right soft spot. The lower bound (4.11) is not a peripheral technicality: it is the only mechanism in the proof that prevents the conditional Borel–Cantelli argument from giving only an upper bound for the number of common-friend additions in the δ=0 and δ<0 phases. If (4.11) failed, ∑ Q_k could grow more slowly than ∑ R_k and the Cesàro limit of the indicator ratio would not be forced to the claimed constant. The manuscript also reveals awareness of incomplete proof details: the acknowledgement thanks the referee for 'precise ideas to fill gaps in parts of the proof of Theorem 2.1' (presumably Theorem 2.2), and (4.11) is exactly such a gap. My own algebraic spot checks (C=2,3,4 and the multinomial expansion) indicate the inequality is true and provable, so I do not believe the theorem is wrong. Rather, as written, a load-bearing assertion is left unverified. The rest of the argument—martingale convergence, uniform integrability, Cesàro averaging, conditional Borel–Cantelli—is standard and, modulo the index typo in the definition of Q_n, coherent. Therefore I agree with the reader's CONDITIONAL verdict; the condition is a written proof of (4.11).","tokens_in":11177,"tokens_out":25388,"duration_ms":249401,"concrete_test":"Verify (4.11) directly: write Q_n via the multinomial expansion Q_n = ∑_{r,s≥1, r+s≤C} C!/(r!s!(C−r−s)!) p^r q^s(1−p−q)^{C−r−s}, and prove the difference from the claimed lower bound is nonnegative for all C≥2 and p,q≥0 with p+q≤1. A tractable route is to keep the (r,s)=(1,1),(1,2),(2,1) terms and show the remaining positive terms dominate; if a counterexample is found, the lower-bound Cesàro argument in parts (2)–(3) collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 2.2 splits the one-step conditional probability Q_n using (4.10) and (4.11). The upper bound (4.10) is elementary, but the lower bound (4.11), Q_n ≥ C(C−1)Y_ij(n)/((2C+δ)^2 n^2) [1 − (C−2)(X_i(n)+X_j(n))/(2(2C+δ)n)], is introduced with 'We can check that' and no verification. This inequality is what forces the Cesàro sums of the lower and upper sandwich L_n and R_n to converge to the same limit in the δ=0 case and, by transfer, in the δ<0 case; without it the conditional Borel–Cantelli step only gives an upper rate, and the claimed logarithmic and power-law limits in Theorem 2.2(2)–(3) could fail. My own spot checks for C=2,3,4 and the multinomial expansion suggest the inequality is true, so this is a missing proof in a load-bearing position rather than an observed falsehood; but because the authors do not supply the proof, the central claim is conditional on an unverified bound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes the number Nij(n) of common neighbors of two fixed vertices in the linear preferential attachment model PA^{δ,C}. Theorem 2.2 identifies a phase transition in the growth rate: a finite almost-sure limit when δ>0, logarithmic growth when δ=0, and power-law growth at rate n^{2γ−1} when δ<0, with the same constant C(C−1)/(2C+δ)^2 Di(∞)Dj(∞) in the last two cases. The proof uses known degree asymptotics, a martingale product limit for Di(n)Dj(n), and a Cesàro sandwich around the conditional connection probability, followed by conditional Borel–Cantelli. The paper also proposes an early-graph estimator for common friends and presents simulations.","tokens_in":11425,"tokens_out":15555,"duration_ms":157165,"significance":"The topic is well chosen and the phase-transition result is new and plausible. If the proof gaps are filled, the paper would be a solid contribution to the probabilistic analysis of preferential attachment and relevant to link-prediction applications. The martingale construction leading to Proposition 4.4 is elegant, and the estimator in Corollary 2.4 is a useful by-product. The main limitation is that a central inequality is asserted without proof, and the δ<0 regime is only sketched, so the main theorem is not yet fully supported.","major_comments":[{"comment":"The lower bound for the conditional expectation of Nij(n+1)−Nij(n) is introduced with the phrase 'We can check that' and no verification is supplied. This inequality is load-bearing: it is used immediately after (4.13) to sandwich the sums ∑Q_k between ∑L_k and ∑R_k, and Lemmas 4.5 and 4.6 then force the same Cesàro limit for the lower and upper sums. Without (4.11), the proof gives only the upper rate, and the almost-sure normalization in Theorem 2.2(2)–(3) is unsupported. Please add the missing derivation from the expansion of 1−(1−p_i)^C−(1−p_j)^C+(1−p_i−p_j)^C, or provide an exact reference.","section":"§4, Eq. (4.11)"},{"comment":"The δ<0 case is dispatched in one sentence saying it can be shown by the same technique as δ=0. This regime has a different normalization, n^{2γ−1}/(2γ−1), and requires the analogue of (4.14) to hold using Lemmas 4.5(2) and 4.6(2), including the verification that the sum of Q_k diverges at the claimed polynomial rate. Because part (3) is one of the three phase-transition regimes, the argument should be written out or at least the key Cesàro limits should be displayed.","section":"§4, proof of Theorem 2.2, part (3)"}],"minor_comments":[{"comment":"Please verify that Durrett's Theorem 4.4.5 indeed contains the ratio statement in (4.13); in many editions that theorem is the conditional Borel–Cantelli lemma giving only P(A_n i.o.)=1. If the cited theorem does not contain the ratio form, replace the citation or add a short martingale–Kronecker proof.","section":"§4, Eq. (4.13)"},{"comment":"The definition of Q_n contains a typo: 'E[Nij(n)−Nij(n)|F_n]' should be 'E[1_{Bij(n)}|F_n]' or equivalently 'E[Nij(n+1)−Nij(n)|F_n]'.","section":"§4, proof of Theorem 2.2, part (2)"},{"comment":"In the recursive estimate, the displayed term 'C^* ℓ^{(k−1)γ+1}' in the sum should be 'C^* ℓ^{(k−1)γ−1}' to match the earlier definition of b_n and the subsequent summation of 1/ℓ^{1+γ}.","section":"Lemma 4.1"},{"comment":"The acknowledgement refers to 'Theorem 2.1' but the paper's main result is Theorem 2.2.","section":"Acknowledgements"}],"recommendation":"major_revision","confidential_remarks":"This is a competent paper with a plausible and interesting theorem. The main obstacle is the unproved lower bound (4.11) and the sketched δ<0 case; once those are completed, the result should be publishable. No concerns about novelty or scope, but the simulation study is illustrative only and should not be treated as evidence of the asymptotics."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nThe short version: this paper is, as far as I can tell, the first theoretical study of the growth of common friends in the linear preferential attachment model. The result is new, the phase transition (finite for δ>0, logarithmic for δ=0, power-law for δ<0) is a clean insight, and the proof strategy—martingale convergence plus conditional Borel–Cantelli—is appropriate. The central claim looks sound, but there is one load-bearing inequality, (4.11), that is asserted with 'We can check that' and not proved. That is the main thing a referee should demand.\n\nWhat the paper does well: Proposition 4.4 on the joint degree product is done properly, with uniform integrability and L1 convergence. The normalizations in Lemmas 4.5 and 4.6 are the right ones, and the Cesàro averaging argument is clear. The δ>0 case is solid via Borel–Cantelli. The estimator in Corollary 2.4 is a natural consequence, and the simulations are fine as illustrations. The citation pattern is appropriate—Bollobás et al. and van der Hofstad for degree asymptotics, Liben-Nowell and Kleinberg for link prediction.\n\nThe soft spots: (4.11) is exactly the lower bound that makes the sandwich around Q_n close in the δ=0 and δ<0 cases. Without it, the conditional Borel–Cantelli step gives only an upper rate, so the logarithmic and power-law limits in Theorem 2.2 would be unsupported. My own spot checks for C=2,3,4 suggest the inequality is true, so this is a missing proof rather than an observed falsehood, but it is in a load-bearing position. The δ<0 case is summarized as 'same technique' rather than written out; that is a minor-to-moderate omission since the transfer should be routine, but an explicit sketch would help. There are also typos ('Martinagale', 'Sterling', a missing subscript in the Q_n definition) that point to a hasty final pass.\n\nWho this is for: people working on preferential attachment, random graph asymptotics, or theoretical aspects of link prediction. It is a worthy journal paper after the fix. I would send it to peer review, and I would ask the authors to supply a proof of (4.11) and a few lines on δ<0.\n\nBest,","headline":"First theoretical rates for common friends in the PA model, with a clean phase transition, but the lower-bound inequality (4.11) is load-bearing and left unproved.","tokens_in":11907,"tokens_out":4121,"would_cite":true,"duration_ms":38479,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60F15","60G42","90B15","91D30"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that in a linear preferential attachment network, the number of common friends of two fixed nodes has three almost-sure growth regimes: a finite limit for δ>0, logarithmic for δ=0, and power-law for δ<0.","keywords":["common friends","preferential attachment","link prediction","phase transition","power-law growth","almost sure convergence","heavy-tail","social networks"],"falsifier":"For $C=3$, $\\delta=-1$, with degrees, say, $D_i(n)=100$ and $D_j(n)=1$ at $n=1000$, compute the exact conditional probability that the next node attaches to both nodes and compare it with the right-hand side of (4.11); a single pair for which the inequality is reversed would refute the proof's key bound, while exhaustive verification over degree pairs would confirm it.","tokens_in":10967,"feed_emoji":"📈","tokens_out":11795,"duration_ms":105846,"temperature":0.7,"pith_summary":"This paper asks how the number of common friends between two fixed users grows as a preferential-attachment network expands, a quantity at the heart of link-prediction systems. Under the standard linear preferential attachment model, the authors prove that the answer has three sharply different regimes controlled by the single parameter $\\delta$ that tunes how strongly new nodes favor high-degree nodes. When $\\delta > 0$, the common-friend count converges almost surely to a finite random limit; when $\\delta = 0$, it grows like a constant times $\\log n$; when $\\delta < 0$, it grows like a constant times $n^{2\\gamma - 1}$, where $\\gamma = C/(2C+\\delta)$. The paper also shows these rates yield a consistent estimator that reads the common-friend count off a much smaller earlier snapshot of the graph.","feed_headline":"Mutual friends stabilize, log-grow, or surge in popularity networks","feed_subtitle":"One bias parameter decides whether shared-friend counts stay flat, climb like log n, or rise as a power law.","key_machinery":"The engine is the conditional attachment probability $p_{i,n+1} = (D_i(n)+\\delta)/((2C+\\delta)n)$. The probability that the new node links to both $i$ and $j$ is approximately $C(C-1)p_i p_j = C(C-1)Y_{ij}(n)/((2C+\\delta)^2 n^2)$, where $Y_{ij}(n) = (D_i(n)+\\delta)(D_j(n)+\\delta)$; the factor $C(C-1)$ counts ordered pairs of distinct stubs. The proof sandwiches the conditional increment probability $Q_n$ between a lower bound (4.11) and an upper bound (4.10), then shows the Cesàro sums of both bounds converge to the same limit after dividing by $\\log n$ or by $n^{2\\gamma-1}/(2\\gamma-1)$. The convergence of the product $Y_{ij}(n)$ itself comes from an exact martingale: $E[Y_{ij}(n+1)\\mid \\mathcal{F}_n] = Y_{ij}(n)(n+\\gamma_1)(n+\\gamma_2)/n^2$ with $\\gamma_1 = (1-1/\\sqrt{C})\\gamma$ and $\\gamma_2 = (1+1/\\sqrt{C})\\gamma$, giving a non-negative martingale $W_{ij}(n)$ whose almost-sure limit carries the degree product; the conditional Borel-Cantelli lemma transfers that limit to $N_{ij}(n)$.","core_discovery":"Fix any two nodes $v_i, v_j$ in the linear preferential attachment model with $C \\ge 2$. Theorem 2.2 asserts, almost surely, that $N_{ij}(n) \\to N_{ij}(\\infty)$ with finite expectation when $\\delta > 0$; that $N_{ij}(n)/\\log n \\to C(C-1)(2C+\\delta)^{-2}D_i(\\infty)D_j(\\infty)$ when $\\delta = 0$; and that $N_{ij}(n)/(n^{2\\gamma-1}/(2\\gamma-1))$ converges to the same constant when $\\delta < 0$, where $\\gamma = C/(2C+\\delta)$ and $D_i(\\infty), D_j(\\infty)$ are the almost-sure limits of the scaled degrees $D_i(n)/n^\\gamma, D_j(n)/n^\\gamma$. The proof identifies the limit constant as $C(C-1)/(2C+\\delta)^2$ times the product of those degree limits, so the randomness in the limit comes entirely from the two nodes' eventual scaled degrees. Corollary 2.4 turns the rates into a consistent estimator: for any $k > 1$, the ratio $N_{ij}(n)/N_{ij}(\\lfloor n/k \\rfloor)$ tends to $1$ when $\\delta \\ge 0$ (with the limiting quantity positive), and $N_{ij}(n)/(N_{ij}(\\lfloor n/k \\rfloor)k^{2\\gamma-1}) \\to 1$ when $\\delta < 0$, meaning a smaller and cheaper snapshot can estimate the later count.","pith_inferences":["Because the limit constant factors as $D_i(\\infty)D_j(\\infty)$, the limit distribution of common friends inherits heavy tails from the degree distribution; one can test whether empirical common-friend counts for old node pairs show tail indices matching the degrees.","The same two-stub counting should extend to counts of longer paths or small motifs: conditional probabilities factor into products of degree terms, so growth rates built from $\\gamma_1$ and $\\gamma_2$ are a natural conjecture the paper does not pursue.","A practical diagnostic follows implicitly: for a fixed old pair, regressing $\\log N_{ij}(n)$ on $\\log n$ distinguishes the three regimes (slope $2\\gamma-1$ for $\\delta<0$, flat with $\\log n$ drift for $\\delta=0$, saturation for $\\delta>0$) and so estimates the sign of $\\delta$ without observing the attachment mechanism."],"forward_implications":["The model exhibits a phase transition in pairwise proximity: $\\delta>0$ gives static common-friend counts, $\\delta=0$ gives logarithmic growth, and $\\delta<0$ gives power-law growth with exponent $2\\gamma-1$.","For $\\delta<0$, the growth exponent $2\\gamma-1$ ranges from just above 0 at $\\delta=0$ to 1 as $\\delta \\to -C$, so the common-friend count of a fixed pair can rise nearly linearly with the network.","Corollary 2.4 provides a consistent estimator that uses only a graph of size $\\lfloor n/k \\rfloor$; in the power-law regime the estimator rescales by $k^{2\\gamma-1}$, which can be much cheaper to compute at scale.","When $\\delta>0$, the finite almost-sure limit means the shared-neighbor count of a fixed pair stops changing even as the network grows."],"supporting_citations":[{"why":"Supplies the linear preferential attachment model definition and the degree-convergence result (Proposition 2.1) on which the proof builds.","marker":"van der Hofstad (2017)"},{"why":"Establishes the scale-free degree-sequence behavior that motivates and grounds the degree limits used in the main theorem.","marker":"Bollobás et al. (2001)"},{"why":"Provides the martingale convergence theorems, conditional Borel-Cantelli lemma, and uniform integrability criteria used throughout Section 4.","marker":"Durrett (2019)"},{"why":"Supplies the Stirling formula used to bound moments and identify constants in the exact recurrences.","marker":"Abramowitz and Stegun (2012)"}],"fun_headline_variants":["Common friends: freeze, log-climb, or power-surge","Mutual friends: static, logarithmic, or power-law growth","Phase transition in common friends: flat, log, or power","One parameter toggles mutual friend growth: flat, log, or power","Preferential attachment drives three regimes for shared friends"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is inequality (4.11), a claimed lower bound on the probability that the next node attaches to both fixed nodes; the authors assert it with 'We can check that' and do not prove it, and if it fails for some $C > 2$, the logarithmic and power-law rates in Theorem 2.2 are not supported.","fun_headline_variants_meta":{"raw":{"variants":["Common friends: freeze, log-climb, or power-surge","Mutual friends: static, logarithmic, or power-law growth","Phase transition in common friends: flat, log, or power","One parameter toggles mutual friend growth: flat, log, or power","Preferential attachment drives three regimes for shared friends"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001063,"raw_usage":{"total_tokens":4474,"prompt_tokens":981,"completion_tokens":3493,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":597,"completion_tokens_details":{"reasoning_tokens":3406}},"tokens_in":597,"tokens_out":3493,"duration_ms":24198,"temperature":1.0,"reasoning_tokens":3406,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:41:28.610648+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $C=3$, $\\delta=-1$, with degrees, say, $D_i(n)=100$ and $D_j(n)=1$ at $n=1000$, compute the exact conditional probability that the next node attaches to both nodes and compare it with the right-hand side of (4.11); a single pair for which the inequality is reversed would refute the proof's key bound, while exhaustive verification over degree pairs would confirm it.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the linear preferential attachment model definition and the degree-convergence result (Proposition 2.1) on which the proof builds."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the martingale convergence theorems, conditional Borel-Cantelli lemma, and uniform integrability criteria used throughout Section 4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Stirling formula used to bound moments and identify constants in the exact recurrences."}],"review_version":1}