Growth of Common Friends in a Preferential Attachment Model

Bikramjit Das; Souvik Ghosh

REVIEW 2 major objections 4 minor 13 references

Growth of Common Friends in a Preferential Attachment Model

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

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 1908.04510 v1 pith:MSJVZJOR submitted 2019-08-13 math.PR stat.AP

Bikramjit Das , Souvik Ghosh This is my paper · ORCID

classification math.PRstat.AP MSC 60F1560G4290B1591D30

keywords commonfriendspreferentialattachmentlinkpredictionphasetransitionpower-lawgrowthalmostsureconvergenceheavy-tailsocialnetworks

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 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.

What carries the argument

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)$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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.

Desk Editor's Note

read the letter

Dear Colleague,

The 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.

What 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.

The 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.

Who 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.

Best,

Referee Report

2 major / 4 minor

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.

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 (2)

[§4, Eq. (4.11)] 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.
[§4, proof of Theorem 2.2, part (3)] 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.

minor comments (4)

[§4, Eq. (4.13)] 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.
[§4, proof of Theorem 2.2, part (2)] 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]'.
[Lemma 4.1] 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+γ}.
[Acknowledgements] The acknowledgement refers to 'Theorem 2.1' but the paper's main result is Theorem 2.2.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the common-friend growth rate is derived from external degree-limit results and standard martingale arguments, not from the conclusion.

full rationale

The paper's central claim, Theorem 2.2, is an almost-sure limit theorem for the number of common friends Nij(n) in a linear preferential attachment model. Its proof depends on Proposition 2.1 for degree growth, which is cited to external literature (Bollobas et al., van der Hofstad), and on martingale and Borel-Cantelli arguments applied to the product Yij(n) = (Di(n)+delta)(Dj(n)+delta). No parameter is fitted to the target quantity, no normalization is chosen to force the limit constant, and no self-citation chain is used to forbid alternatives. The limit constants C(C-1)/(2C+delta)^2 Di(infty)Dj(infty) arise from the model's attachment probabilities and from the independently established degree limits, not from the definition of Nij(n). The unproved inequality (4.11), introduced with 'We can check that', is a missing verification in a load-bearing proof step, but it is not circular: it is a two-sided binomial inclusion-exclusion bound on the conditional one-step probability Qn, and proving it would not make the theorem an input-output tautology. The acknowledgement that the referee provided 'precise ideas to fill gaps' similarly indicates gaps in exposition or proof, not that the result is equivalent to its assumptions. Thus the derivation is self-contained with respect to the model and external degree-limit results, and no self-definitional, fitted-input, or self-citation circularity is present.

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

No free parameters are fitted; δ and C are model inputs. The proof builds on two external results (degree growth, standard martingale theory) and one unproved technical inequality (4.11).

assumptions (4)

domain assumption The linear preferential attachment model as defined in Section 2, where each new node attaches C edges to existing nodes with probabilities proportional to degree plus δ.
This is the model under study; all results depend on this definition.
standard math Known degree growth result (Proposition 2.1) from van der Hofstad (2017) and Bollobas et al. (2001) that Di(n)/n^γ → Di(∞) a.s. with E[Di(∞)] = (C+δ)Γ(i)/Γ(i+γ).
Used as input to derive the rate of the product Yij(n) and the final limits.
standard math Standard probability tools: martingale convergence, conditional Borel-Cantelli lemma, Borel-Cantelli lemma, and Stirling's formula.
Invoked in Section 4 without proof.
ad hoc to paper Inequality (4.11): Q_n ≥ C(C-1) p_i p_j (1 - (C-2)/2(p_i+p_j)), asserted but not proved.
This inequality is load-bearing for the lower bound in the Cesàro limits for the δ=0 and δ<0 regimes. It is stated with 'We can check that' and no proof is provided.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Growth of Common Friends in a Preferential Attachment Model." pith.science (2026). https://pith.science/paper/MSJVZJOR

@misc{pith2026190804510,
  author       = {Pith},
  title        = {Pith review of: Growth of Common Friends in a Preferential Attachment Model},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MSJVZJOR}},
  note         = {Machine review of arXiv:1908.04510}
}

read the original abstract

The number of common friends (or connections) in a graph is a commonly used measure of proximity between two nodes. Such measures are used in link prediction algorithms and recommendation systems in large online social networks. We obtain the rate of growth of the number of common friends in a linear preferential attachment model. We apply our result to develop an estimate for the number of common friends. We also observe a phase transition in the limiting behavior of the number of common friends; depending on the range of the parameters of the model, the growth is either power-law, or, logarithmic, or static with the size of the graph.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

bbook [author] Abramowitz , M. M. Stegun , I. A. I. A. ( 2012 ). Handbook of Mathematical Functions: with Formulas, Graphs, and Mathematical Tables . Courier Corporation . bbook

work page 2012
[2]

barticle [author] Barab\'asi , A. A. Albert , R. R. ( 1999 ). Emergence of scaling in random network . Science 286 509-512 . barticle

work page 1999
[3]

barticle [author] Bollob\'as , B. B. , Riordan , O. O. , Spencer , J. J. Tusn\'ady , G. G. ( 2001 ). The degree sequence of a scale-free random graph process . Random Structures Algorithms 18 279--290 . barticle

work page 2001
[4]

binproceedings [author] Bollob\'as , B. B. , Borgs , C. C. , Chayes , J. J. Riordan , O. O. ( 2003 ). Directed scale-free graphs . In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, 2003) 132-139 . binproceedings

work page 2003
[5]

barticle [author] Cooper , C. C. Frieze , A. A. ( 2003 ). A general model of web graphs . Random Structures & Algorithms 22 311--335 . barticle

work page 2003
[6]

barticle [author] Dereich , S. S. M\"orters , P. P. ( 2009 ). Random networks with sublinear preferential attachment: Degree evolutions . Electronic Journal of Probability 43 1222-1267 . barticle

work page 2009
[7]

bbook [author] Durrett , R. T. R. T. ( 2019 ). Probability: Theory and Examples , fifth ed. Cambridge Series in Statistical and Probabilistic Mathematics 49 . Cambridge University Press, Cambridge . bbook

work page 2019
[8]

barticle [author] Elwes , R. R. ( 2016 ). A Linear Preferential Attachment Process Approaching the Rado Graph . http://arxiv.org/abs/1603.08806v2 . barticle

work page Pith review arXiv 2016

Show all 13 references

[9]

binproceedings [author] Gupta , P. P. , Goel , A. A. , Lin , J. J. , Sharma , A. A. , Wang , D. D. Zadeh , R. R. ( 2013 ). W T F : The Who to Follow Service at Twitter . In Proceedings of the 22Nd International Conference on World Wide Web . WWW '13 505--514 . ACM , New York, ...

2013
[10]

barticle [author] Liben-Nowell , D. D. Kleinberg , J. J. ( 2007 ). The link-prediction problem for social networks . Journal of the American Society for Information Science and Technology 58 1019--1031 . barticle

2007
[11]

barticle [author] Resnick , S. I. S. I. Samorodnitsky , G. G. ( 2015 ). Tauberian Theory for Multivariate Regularly Varying Distributions with Application to Preferential Attachment Networks . Extremes 18 349--367 . barticle

2015
[12]

barticle [author] Samorodnitsky , G. G. , Resnick , S. S. , Towsley , D. D. , Davis , R. R. , Willis , A. A. Wan , P. P. ( 2016 ). Nonstandard regular variation of in-degree and out-degree in the preferential attachment model . Journal of Applied Probability 53 146-161 . barticle

2016
[13]

bbook [author] van der Hofstad , R. R. ( 2017 ). Random graphs and complex networks. V ol. 1 . Cambridge Series in Statistical and Probabilistic Mathematics, [43] . Cambridge University Press, Cambridge . bbook

2017

Pith tools

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

[1] [1]

bbook [author] Abramowitz , M. M. Stegun , I. A. I. A. ( 2012 ). Handbook of Mathematical Functions: with Formulas, Graphs, and Mathematical Tables . Courier Corporation . bbook

work page 2012

[2] [2]

barticle [author] Barab\'asi , A. A. Albert , R. R. ( 1999 ). Emergence of scaling in random network . Science 286 509-512 . barticle

work page 1999

[3] [3]

barticle [author] Bollob\'as , B. B. , Riordan , O. O. , Spencer , J. J. Tusn\'ady , G. G. ( 2001 ). The degree sequence of a scale-free random graph process . Random Structures Algorithms 18 279--290 . barticle

work page 2001

[4] [4]

binproceedings [author] Bollob\'as , B. B. , Borgs , C. C. , Chayes , J. J. Riordan , O. O. ( 2003 ). Directed scale-free graphs . In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, 2003) 132-139 . binproceedings

work page 2003

[5] [5]

barticle [author] Cooper , C. C. Frieze , A. A. ( 2003 ). A general model of web graphs . Random Structures & Algorithms 22 311--335 . barticle

work page 2003

[6] [6]

barticle [author] Dereich , S. S. M\"orters , P. P. ( 2009 ). Random networks with sublinear preferential attachment: Degree evolutions . Electronic Journal of Probability 43 1222-1267 . barticle

work page 2009

[7] [7]

bbook [author] Durrett , R. T. R. T. ( 2019 ). Probability: Theory and Examples , fifth ed. Cambridge Series in Statistical and Probabilistic Mathematics 49 . Cambridge University Press, Cambridge . bbook

work page 2019

[8] [8]

barticle [author] Elwes , R. R. ( 2016 ). A Linear Preferential Attachment Process Approaching the Rado Graph . http://arxiv.org/abs/1603.08806v2 . barticle

work page Pith review arXiv 2016