Pith. sign in

REVIEW 2 major objections 3 minor 39 references

The Generalized Friendship Paradox for Eigenvectors

T0 review · 2 major / 3 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read For graphon-generated random graphs, the empirical distribution of eigenvector-friendship bias converges to an explicit deterministic law.

desk verdict New, mostly solid limit theorem for eigenvector friendship bias in graphon random graphs; the sparse-case proof has a normalization typo that must be fixed before the paper can be trusted. read the letter →

arxiv 2607.19549 v1 pith:UA6MRPDG submitted 2026-07-21 math.PR

Bishakh Bhattacharya , Arijit Chakrabarty , Rajat Subhra Hazra This is my paper
classification math.PR MSC 05C8060B2060B1046L54
keywords generalizedfriendshipparadoxeigenvectorcentralitygraphoninhomogeneousErdős–RényigraphempiricaldistributionintegraloperatorPerron–Frobeniusweakconvergenceinprobability
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 asks: if each vertex is assigned its entry in the principal eigenvector of the adjacency matrix, how do the 'friend-averaged' eigenvector values compare to the vertex's own value across a large random graph? It proves that for graphs whose edge probabilities come from a continuous graphon, the empirical distribution of these bias values converges, as n grows, to a deterministic probability measure. The limit is explicit: it is the law of (ρ/K(U)−1)φ(U), where ρ and φ are the principal eigenvalue and eigenfunction of the integral operator with the graphon as kernel, K is the degree functional, and U is uniform on [0,1]. This gives a parameter-free description of how eigenvector centrality spreads through large inhomogeneous networks, and it yields a simple integral condition under which the paradox is 'significant' — more than half the vertices see nonnegative bias.

What carries the argument

The driving object is the graphon integral operator T_W on L²[0,1], whose kernel is the continuous symmetric graphon W. The limiting object Δ∞ is built from its principal pair (ρ,φ) together with the degree functional K(x)=∫W(x,y)dy. The proof transfers spectral data from the n×n adjacency matrix to T_W by identifying the nonzero spectra of P_n/n with those of the step-function operator T_{W_n} (via explicit identification operators S¹_n, S²_n), showing ∥T_{W_n}−T_W∥→0 and ∥(A_n−P_n)/n∥=o_p(1), then using Weyl's inequality for eigenvalues and a Davis–Kahan-type bound for eigenvector step functions. Concentration of degrees comes from Bernstein's inequality, and the sparsity regime in Model B

What would settle it

Simulate Model A for a continuous, symmetric W that satisfies Assumptions A1–A3 but has a narrow spectral gap (e.g., W(x,y)=a(x)a(y)+εb(x)b(y) with very small ε), compute the empirical bias histogram at large n, and test it against μ∞=(ρ/K(U)−1)φ(U); a systematic mismatch in the tails, or a histogram that does not stabilize as n grows, would refute the claimed limit. A second check: take a finite graph with two equal largest eigenvalues (ρ degenerate) and observe that the bias distribution no longer has the single-eigenfunction form predicted by the theorem.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 2.1: for a continuous symmetric graphon W satisfying a positivity and spectral-gap condition, the empirical distribution of eigen-friendship biases in the induced inhomogeneous Erdős–Rényi graph converges weakly in probability to the law of Δ∞=(ρ/K(U)−1)φ(U), with U uniform on [0,1]. Here ρ is the principal eigenvalue and φ the positive normalized principal eigenfunction of the integral operator T_W, and K(x)=∫₀¹W(x,y)dy is the limiting degree profile. The proof reduces the limit to two L² convergences: λ₁/d_i scaled by n (resp. nεₙ) converges to ρ/K, and the Perron-vector step function converges to φ; these are obtained from degree concentration, Weyl pertur

Load-bearing premise

The whole eigenvector-convergence step rests on the principal eigenvalue ρ of the integral operator T_W being simple and isolated — if the gap to the next eigenvalue closes, the Davis–Kahan bound fails and the explicit law in terms of a single φ is no longer justified.

Editorial extensions

If this is right

  • If Theorem 2.1 holds, the entire distribution of Perron-eigenvector bias in large graphon-generated graphs is determined by three graphon functionals — ρ, φ, and K — with no further network statistics needed at first order.
  • The limiting law has compact support whenever K>0, because h(x)=(ρ/K(x)−1)φ(x) is continuous on [0,1]; bias values cannot wander arbitrarily far.
  • The 'significance' of the eigen-friendship paradox — more than half the vertices having nonnegative bias — reduces to the integral test ∫∫W < ρ/2, a checkable condition for a given graphon.
  • For d-regular graphs the limit is δ₀, and for rank-1 graphons W(x,y)=r(x)r(y) the limiting mean bias is nonnegative by Cauchy–Schwarz, recovering the paradox in explicit form.
  • The same two-part convergence (eigenvalue ratio and eigenvector) supplies a template for limiting bias distributions of other spectral centralities in the graphon setting.

Reading between the lines

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

  • Because the theorem reduces the limit law to h(U) with h continuous when K>0, any two graphons sharing the same (ρ,φ,K) would be indistinguishable at first order in the bias distribution — an equivalence that finite-n empirical tests would need to break using higher-order fluctuations.
  • An analogous argument should yield limit laws for Katz or PageRank centrality biases, since the same resolvent-based Davis–Kahan control is the only non-commutative input needed.
  • The two-block graphon computation hints that the explicit limit may persist even for piecewise-continuous kernels outside the theorem's stated assumptions, provided the principal eigenvalue remains simple; a separate proof for discontinuous kernels would settle this.
  • The condition ∫∫W < ρ/2 suggests a practical design rule: it tells which edge-density profiles guarantee that the majority of vertices will appear 'less central than their neighbors' in spectral terms.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper studies the generalized friendship paradox for eigenvectors (EFP) in inhomogeneous Erdős–Rényi random graphs generated by continuous graphons. For each vertex, the eigen-friendship bias is Δ_i^E = (λ_1/d_i - 1) r_i, where λ_1 is the largest adjacency eigenvalue and r is the corresponding normalized eigenvector. The authors prove that, under spectral-gap and positivity assumptions on the integral operator T_W associated with the graphon W, the empirical distribution of these biases converges weakly in probability to the law of Δ_∞ = (ρ/K(U) - 1)ϕ(U), where U∼U(0,1), ρ and ϕ are the principal eigenvalue and eigenfunction of T_W, and K(x)=∫W(x,y)dy. The result covers both a dense model (Model A) and a sparse model (Model B) with edge probabilities ε_n W(·,·), under the condition nε_n ≫ (log n)^ξ. The proof proceeds by proving L^1 convergence of the bias step functions to the limiting function, splitting into degree-ratio convergence and eigenvector convergence via Davis–Kahan.

Significance. If the normalization issue in Model B is corrected, this is a substantial and useful result. The limiting distribution is explicit and parameter-free: it is determined entirely by the spectral data of the graphon, not by fitting to simulations. The paper covers both dense and moderately sparse regimes and uses a clean combination of standard tools: degree concentration, spectral norm estimates for inhomogeneous random matrices, integral-operator approximation of the mean matrix, and Davis–Kahan eigenvector perturbation. The result connects the friendship-paradox literature to graphon spectral theory and would be of interest to random graph theorists and network scientists. The main theorem is plausible and the proof architecture is sound; however, as printed, the Model B eigenvalue normalization in Lemma 3.3 is internally inconsistent and must be fixed before the result can be considered verified.

major comments (2)
  1. [Lemma 3.3 (Model B), pp. 13–14] The normalization in the Model B part of Lemma 3.3 is inconsistent as printed. Since P_n has entries ε_n W(X_(i), X_(j)), the operator identity (3.13) becomes S1_n P_n S2_n = n ε_n T_Wn, so the nonzero spectra of T_Wn and P_n/(nε_n) coincide, not those of T_Wn and P_n/n. Consequently the correct identity is λ1(P_n)/(nε_n) = λ1(T_Wn), not λ1(P_n)/(nε_n) = λ1(T_Wn)/ε_n. Taken literally, the printed statement would imply λ1/(nε_n) cannot converge to ρ. The subsequent Weyl step (3.16) compares λ1/(nε_n) with λ1(T_Wn), which is only justified under the corrected identity. Since Model B is one of the two regimes covered by Theorem 2.1, this is a load-bearing error. The rest of the proof is consistent with the corrected identity, so I regard this as repairable, but the normalization and the ensuing eigenvalue convergence argument must be corrected and re-verified.
  2. [Lemma 3.3, Model B display after (3.16)] The line '|λ1(T_Wn)-λ1(T_W)| = |λ1(T_Wn)/ε - ρ|' is also not correct as written. Since T_Wn has kernel W(X_(⌈nx⌉), X_(⌈ny⌉)) and T_W has kernel W(x,y), the intended statement is |λ1(T_Wn)-ρ| ≤ ∥T_Wn - T_W∥. This appears to be a typo, but it should be corrected for coherence with the preceding equations.
minor comments (3)
  1. [Lemma 3.3, Model A spectrum argument] In the proof that nonzero spectra of S1_n P_n S2_n and P_n coincide, the argument that S2 y ≠ 0 is misstated. If S2 y = 0, then the eigenvalue equation S1_n P_n S2_n y = α y gives 0 = α y, hence y = 0, contradicting y ≠ 0. The intended conclusion is correct, but the displayed reasoning around '0 = α S2 y' is not the right contradiction.
  2. [Section 4.3] The two-block graphon is discontinuous and is therefore outside the hypotheses of Theorem 2.1. The phrase 'can be justified by continuous approximations' is vague. If this example is kept, the authors should either state a precise approximation argument or explicitly label the computation as heuristic and outside the theorem.
  3. [Lemma 3.4, Model A constants] The constants in the bound on |n^2/d_{⌈nx⌉}^2 - 1/K(x)^2| and the threshold δK_min^4/4 appear off by a factor (the pointwise inequality gives 8/K_min^4, suggesting δK_min^4/8). Since the argument is asymptotic and δ is arbitrary, this is harmless, but it should be cleaned up.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the limiting distribution is derived from graphon spectral data, not fitted to the empirical measure, and the key self-citation is independently proven in the paper.

full rationale

The derivation chain for Theorem 2.1 is self-contained. The limiting measure is expressed through ρ, K, and φ, which are deterministic spectral objects of the underlying graphon, and no parameter is fitted to the empirical eigen-friendship biases. The proof proceeds through degree concentration (Lemma 3.1), spectral norm concentration (Lemma 3.2), eigenvalue convergence (Lemma 3.3), and Davis–Kahan based eigenvector convergence (Lemma 3.5), each established in the text or via cited external results on random matrix concentration and perturbation theory. The only potentially self-citational starting point—the assertion that the eigen-friendship paradox holds, attributed to Hazra and Verbitskiy (2026)—is immediately reproven in Lemma 2.1, so the citation is not load-bearing. Other self-citations (e.g., to Hazra et al. 2025a) provide context or terminology, not the theorem's content. No step reduces by construction to the claimed limit: the bound (2.10), Part 1 and Part 2 together yield the L1 convergence of the bias step functions, and the target weak convergence follows from bounded-Lipschitz testing. A possible typo in Lemma 3.3 for Model B (the normalization P_n/n versus P_n/(n ε_n)) is a correctness concern about the proof as printed, not a circularity, because the conclusion is not assumed in that lemma. Overall, the central claim has independent mathematical content and is not equivalent to its inputs.

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

The central claim rests on the graphon model, the three explicit technical assumptions A1–A3, and the Model B sparsity condition. No free parameters are fitted to data; ρ, K, and φ are spectral and functional objects determined by W. External results are used as standard tools rather than as inputs that force the conclusion.

assumptions (6)
  • domain assumption W: [0,1]^2 → [0,1] is symmetric, continuous, and W ≢ 0.
    This is the graphon model used in both Model A and Model B; continuity is used for uniform operator approximation (Lemmas 3.3 and 3.5).
  • domain assumption A1: K(x) = ∫_0^1 W(x,y)dy ≥ k_min > 0 for all x.
    Needed in Lemma 3.4 to control 1/K and to define events where degrees stay bounded away from zero after scaling.
  • domain assumption A2: ρ = λ1(T_W) is simple and isolated with gap γ > 0.
    Required for the Davis–Kahan eigenvector convergence argument in Lemma 3.5; if the gap closes, convergence of the empirical eigenvector to a single φ is not guaranteed.
  • domain assumption A3: the principal eigenfunction φ of T_W satisfies φ > 0 and ||φ||_2 = 1.
    Used to identify the sign of the limit and in Remark 3.4 to simplify P(∆∞ ≥ 0); not implied by continuity alone when W has zeros.
  • domain assumption Model B sparsity: (log n)^ξ / (n ε_n) → 0 for some fixed ξ > 4.
    Needed for the spectral concentration bound via Lemma 4.1 of Chakrabarty et al. (2020); this is a moderately sparse regime, not nε_n = O(1).
  • standard math Standard external results: Perron–Frobenius, Bernstein's inequality, Weyl's inequality, Davis–Kahan theorem, Glivenko–Cantelli, and the trace-moment bound of Chakrabarty et al. (2020).
    These are used as tools in Lemmas 3.1–3.5; none of them encodes the target limiting distribution.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Generalized Friendship Paradox for Eigenvectors." pith.science (2026). https://pith.science/paper/UA6MRPDG

@misc{pith2026260719549,
  author       = {Pith},
  title        = {Pith review of: The Generalized Friendship Paradox for Eigenvectors},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UA6MRPDG}},
  note         = {Machine review of arXiv:2607.19549}
}
read the original abstract

In this paper, we investigate the generalized friendship paradox for eigenvectors (alternatively called the eigen friendship paradox and abbreviated hereafter as EFP) in the setting of inhomogeneous Erd\H{o}s--R\'enyi random graphs whose edge probabilities are generated by a continuous graphon. We consider the adjacency matrix of the graph and take the entries of the eigenvector corresponding to its largest eigenvalue as the vertex attributes. It was shown in \cite{hazra2026generalized} that the generalized friendship paradox holds in this setting. We study the empirical distribution of the resulting bias values across the vertices and derive its limiting distribution explicitly in terms of the principal eigenvalue and the corresponding eigenfunction of the integral operator whose kernel is the underlying graphon.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

39 extracted references · 3 linked inside Pith

  1. [1]

    and Kirkley, A

    Cantwell, G.T. and Kirkley, A. and Newman, M.E.J. , title =. J. Complex Netw. , volume =. 2021 , number =

    2021

  2. [2]

    , title =

    Chatterjee, S. , title =. 2017 , volume =

    2017

  3. [3]

    and Varadhan, S.R.S

    Chatterjee, S. and Varadhan, S.R.S. , title =. European J. Combin. , volume =

  4. [4]

    and Sen, S

    Dhara, S. and Sen, S. , title =. Ann. Appl. Probab. , volume =

  5. [5]

    Why your friends have more friends than you do , author =. Am. J. Sociol. , volume =

  6. [6]

    and den Hollander, F

    Hazra, R.S. and den Hollander, F. and Parvaneh, A. , title =. Probab. Theory Relat. Fields , year =

  7. [7]

    Random Graphs and Complex Networks , author =

  8. [8]

    , title =

    den Hollander, F. , title =

Show all 39 references
  1. [9]

    , title =

    Lov\'asz, L. , title =

  2. [10]

    , title =

    Markering, M. , title =. J. Theoret. Probab. , volume =

  3. [11]

    , title =

    Meerpoel, V. , title =

  4. [12]

    A study on the friendship paradox--quantitative analysis and relationship with assortative mixing , author =. Appl. Netw. Sci. , volume =

  5. [13]

    , booktitle =

    Aldous, D.J. , booktitle =. Exchangeability and. 1985 , pages =

    1985

  6. [14]

    Athreya, S. and R\". Dense graph limits under respondent-driven sampling , JOURNAL =. 2016 , NUMBER =

    2016

  7. [15]

    PloS one , volume=

    Social network sensors for early detection of contagious outbreaks , author=. PloS one , volume=. 2010 , publisher=

    2010

  8. [16]

    and Jo, H.-H

    Eom, Y.-H. and Jo, H.-H. , title=. Scientific Reports , year=

  9. [17]

    Proceedings of the International AAAI Conference on Web and Social Media , volume=

    Friendship Paradox Redux: Your Friends Are More Interesting Than You , author=. Proceedings of the International AAAI Conference on Web and Social Media , volume=. 2021 , pages=

    2021

  10. [18]

    Journal of political economy , volume=

    The friendship paradox and systematic biases in perceptions and social norms , author=. Journal of political economy , volume=. 2019 , publisher=

    2019

  11. [19]

    and Ross, S.M

    Cao, Y. and Ross, S.M. , TITLE =. Math. Sci. , VOLUME =. 2016 , NUMBER =

    2016

  12. [20]

    What Do Your Friends Think?

    Nettasinghe, B. and Krishnamurthy, V. , journal=. “What Do Your Friends Think?”: Efficient Polling Methods for Networks Using Friendship Paradox , year=

  13. [21]

    Journal of Complex Networks , volume=

    The generalized friendship paradox for spectral centralities , author=. Journal of Complex Networks , volume=. 2026 , publisher=

    2026

  14. [22]

    Eigenvalues outside the bulk of inhomogeneous Erd

    Chakrabarty, Arijit and Chakraborty, Sukrit and Hazra, Rajat Subhra , journal=. Eigenvalues outside the bulk of inhomogeneous Erd. 2020 , publisher=

    2020

  15. [23]

    SIAM Journal on Matrix Analysis and Applications , volume=

    Norms of Toeplitz matrices with Fisher--Hartwig symbols , author=. SIAM Journal on Matrix Analysis and Applications , volume=. 2007 , publisher=

    2007

  16. [24]

    IEEE Transactions on Network Science and Engineering , volume=

    Centrality measures for graphons: Accounting for uncertainty in networks , author=. IEEE Transactions on Network Science and Engineering , volume=. 2018 , publisher=

    2018

  17. [25]

    arXiv preprint arXiv:2507.02627 , year=

    The Triangle Friendship Paradox , author=. arXiv preprint arXiv:2507.02627 , year=

    arXiv

  18. [26]

    2013 , publisher=

    Convergence of probability measures , author=. 2013 , publisher=

    2013

  19. [27]

    American journal of sociology , volume=

    Why your friends have more friends than you do , author=. American journal of sociology , volume=. 1991 , publisher=

    1991

  20. [28]

    arXiv preprint arXiv:0910.0948 , year=

    A note on the weighted harmonic-geometric-arithmetic means inequalities , author=. arXiv preprint arXiv:0910.0948 , year=

    arXiv

  21. [29]

    What do your friends think?

    “What do your friends think?”: Efficient polling methods for networks using friendship paradox , author=. IEEE transactions on knowledge and data engineering , volume=. 2019 , publisher=

    2019

  22. [30]

    New England journal of medicine , volume=

    The collective dynamics of smoking in a large social network , author=. New England journal of medicine , volume=. 2008 , publisher=

    2008

  23. [31]

    , author=

    The friendship paradox. , author=. Mathematical Scientist , volume=

  24. [32]

    Journal of Complex Networks , volume=

    The friendship paradox in real and model networks , author=. Journal of Complex Networks , volume=. 2021 , publisher=

    2021

  25. [33]

    Scientific reports , volume=

    Generalized friendship paradox in complex networks: The case of scientific collaboration , author=. Scientific reports , volume=. 2014 , publisher=

    2014

  26. [34]

    Proceedings of the International AAAI Conference on Web and Social Media , volume=

    Friendship paradox redux: Your friends are more interesting than you , author=. Proceedings of the International AAAI Conference on Web and Social Media , volume=

  27. [35]

    The pagerank citation ranking: Bring order to the web , author=. Proc. of the 7th International World Wide Web Conf.--1998 , year=

    1998

  28. [36]

    Games and Economic Behavior , volume=

    Distributions of centrality on networks , author=. Games and Economic Behavior , volume=. 2020 , publisher=

    2020

  29. [37]

    2017 , publisher=

    Probability and measure , author=. 2017 , publisher=

    2017

  30. [38]

    Stochastic Processes and their Applications , pages=

    The multi-level friendship paradox for sparse random graphs , author=. Stochastic Processes and their Applications , pages=. 2026 , publisher=

    2026

  31. [39]

    arXiv preprint arXiv:2505.21774 , year=

    The friendship paradox for trees , author=. arXiv preprint arXiv:2505.21774 , year=

    arXiv

Pith tools

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