IDEAS home Printed from https://ideas.repec.org/a/eee/spapps/v195y2026ics0304414926000050.html

The multi-level friendship paradox for sparse random graphs

Author

Listed:
  • Subhra Hazra, Rajat
  • den Hollander, Frank
  • Parvaneh, Azadeh

Abstract

In [1] we analysed the friendship paradox for sparse random graphs. For four classes of random graphs we characterised the empirical distribution of the friendship biases between vertices and their neighbours at distance 1, proving convergence as n → ∞ to a limiting distribution, with n the number of vertices, and identifying moments and tail exponents of the limiting distribution. In the present paper we look at the multi-level friendship bias between vertices and their neighbours at distance k∈N obtained via a k-step exploration according to a backtracking or a non-backtracking random walk. We identify the limit of the empirical distribution of the multi-level friendship biases as n → ∞ and/or k → ∞. We show that for non-backtracking exploration the two limits commute for a large class of sparse random graphs, including those that locally converge to a rooted Galton-Watson tree. In particular, we show that the same limit arises when k depends on n, i.e., k=kn, provided limn→∞kn=∞ under some mild conditions. We exhibit cases where the two limits do not commute and show the relevance of the mixing time of the exploration.

Suggested Citation

  • Subhra Hazra, Rajat & den Hollander, Frank & Parvaneh, Azadeh, 2026. "The multi-level friendship paradox for sparse random graphs," Stochastic Processes and their Applications, Elsevier, vol. 195(C).
  • Handle: RePEc:eee:spapps:v:195:y:2026:i:c:s0304414926000050
    DOI: 10.1016/j.spa.2026.104873
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0304414926000050
    Download Restriction: Full text may be restricted for ScienceDirect subscribers

    File URL: https://libkey.io/10.1016/j.spa.2026.104873?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Matthew O. Jackson, 2019. "The Friendship Paradox and Systematic Biases in Perceptions and Social Norms," Journal of Political Economy, University of Chicago Press, vol. 127(2), pages 777-818.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ronak Jain & Vatsal Khandelwal, 2024. "Silent networks: the role of inaccurate beliefs in reducing useful social interactions," ECON - Working Papers 455, Department of Economics - University of Zurich.
    2. Gary Charness & Francesco Feri & Matthew Jackson & Miguel Melendez-Jimenez & Matthias Sutter, 2026. "The Friendship Paradox: Causal Evidence of Its Behavioral Consequences," CESifo Working Paper Series 12905, CESifo.
    3. Mira Frick & Ryota Iijima & Yuhta Ishii, 2018. "Dispersed Behavior and Perceptions in Assortative Societies," Cowles Foundation Discussion Papers 2128R3, Cowles Foundation for Research in Economics, Yale University, revised Jun 2022.
    4. Olivier Bochet & Mathieu Faure & Yan Long & Yves Zenou, 2025. "Perceived Competition," AMSE Working Papers 2515, Aix-Marseille School of Economics, France.
    5. Belhaj, Mohamed & Deroïan, Frédéric, 2021. "The value of network information: Assortative mixing makes the difference," Games and Economic Behavior, Elsevier, vol. 126(C), pages 428-442.
    6. Bochet, Olivier & Faure, Mathieu & Long, Yan & Zenou, Yves, 2020. "Perceived Competition in Networks," CEPR Discussion Papers 15582, Centre for Economic Policy Research.
    7. Garance Genicot, 2022. "Tolerance and Compromise in Social Networks," Journal of Political Economy, University of Chicago Press, vol. 130(1), pages 94-120.
    8. Francesco Renzini, 2025. "Network formation dynamics in asymmetric coordination games," Rationality and Society, , vol. 37(3), pages 356-394, August.
    9. Bing Han & David Hirshleifer & Johan Walden, 2023. "Visibility Bias in the Transmission of Consumption Beliefs and Undersaving," Journal of Finance, American Finance Association, vol. 78(3), pages 1647-1704, June.
    10. Wichers, Hendrika Geesje, 2023. "Targeted intervention using network characteristics: An experiment," Journal of Behavioral and Experimental Economics (formerly The Journal of Socio-Economics), Elsevier, vol. 103(C).
    11. Francis Bloch & Matthew O. Jackson & Pietro Tebaldi, 2023. "Centrality measures in networks," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 61(2), pages 413-453, August.
    12. Jim Leitzel, 2021. "Double defaults: Behavioral regulation of cocaine," Journal of Behavioral Economics for Policy, Society for the Advancement of Behavioral Economics (SABE), vol. 5(1), pages 7-12, Septembre.
    13. Arthur Campbell & C. Matthew Leister & Yves Zenou, 2020. "Word‐of‐mouth communication and search," RAND Journal of Economics, RAND Corporation, vol. 51(3), pages 676-712, September.
    14. Promit K. Chaudhuri & Matthew O. Jackson & Sudipta Sarangi & Hector Tzavellas, 2023. "Network Beliefs and Behavior with Peer Effects," Papers 2305.03124, arXiv.org, revised Jun 2026.
    15. Mira Frick & Ryota Iijima & Yuhta Ishii, 2018. "Dispersed Behavior and Perceptions in Assortative Societies," Cowles Foundation Discussion Papers 2128, Cowles Foundation for Research in Economics, Yale University.
    16. Evan Sadler & Benjamin Golub, 2021. "Games on Endogenous Networks," Papers 2102.01587, arXiv.org, revised Feb 2024.
    17. Andreas Bjerre-Nielsen & Martin Benedikt Busch, 2022. "Statistical inference in social networks: how sampling bias and uncertainty shape decisions," Papers 2205.13046, arXiv.org.
    18. Yan Leng & Xiaowen Dong & Esteban Moro & Alex Pentland, 2024. "Long-Range Social Influence in Phone Communication Networks on Offline Adoption Decisions," Information Systems Research, INFORMS, vol. 35(1), pages 318-338, March.
    19. González, Felipe, 2020. "Collective action in networks: Evidence from the Chilean student movement," Journal of Public Economics, Elsevier, vol. 188(C).
    20. Florian Mudekereza, 2025. "Aggregate Efficiency in Games," Papers 2501.13019, arXiv.org, revised Feb 2026.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;

    JEL classification:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:spapps:v:195:y:2026:i:c:s0304414926000050. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/505572/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.