The friendship paradox for trees
Rajat Subhra Hazra · 2025
Read The friendship paradox for trees by Rajat Subhra Hazra (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-21774.txt.
Introduction
Hazra and co-authors (2025) analyze the friendship paradox on trees. The paradox is the network effect by which your friends tend, on average, to have more friends than you do. For each vertex the authors track whether this friendship bias is positive, neutral, or negative.
For any finite tree, they prove the positive vertices always number at least as many as the negative ones. They call this property significance. They also bound the gap using the tree's branching points. For an endless random Galton-Watson tree, they compute how common each type is. There, either side can dominate, depending on how the offspring are distributed. They also work out how often each pair of vertex types sits at the ends of an edge, and when those types attract or repel. The results give the paradox a precise shape on the simplest branching networks.
Catalog record
| CREATOR | Rajat Subhra Hazra |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-21774
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The friendship paradox for trees Rajat Subhra Hazra Abstract We analyse the friendship paradox on finite and infinite trees. In particular, we monitor the vertices for which the friendship-bias is positive, neutral and negative, respectively. For an arbitrary finite tree, we show that the number of positive vertices is at least as large as the number of negative vertices, a property we refer to as significance, and derive a lower bound in terms of the branching points in the tree. For an infinite Galton-Watson tree, we compute the densities of the positive and the negative vertices and show that either may dominate the other, depending on the offspring distribution. We also compute the densities of the edges having two given types of vertices at their ends, and give conditions in terms of the offspring distribution under which these types are positively or negatively correlated. AMS 2020 subject classifications. 05C80, 60C05. Key words and phrases. Trees, Friendship Paradox, Friendship-bias, Positive, neutral and negative vertices, Significance. Acknowledgment. The work in this paper was supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003. FdH and NL were supported by the National Science Foundation (NSF) under Grant No. DMS-1928930 while in residence at the Simons Laufer Mathematical Sciences Institute in Berkeley, California, USA during the Spring 2025 semester. AP received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement Grant Agreement No 101034253. 1 Introduction and main results Section 1.1 provides a brief background. Section 1.2 introduces notation. Section 1.3 states our main theorems for finite trees, Section 1.4 for infinite trees. Section 1.5 places these theorems in their proper context and lists a few open problems. Section 1.6 gives the outline of the remainder of the paper. 1.1 Background The friendship paradox says that for any finite graph the average friendship-bias is non-negative [ 7 , 8 ] . More precisely, let G_{n} be a finite undirected graph with n vertices, labelled by u\in[n]=\{1,\ldots,n\} . Define the friendship-bias of vertex u as \Delta_{u,n}=\left(\frac{1}{d_{u}}\sum_{v\in[n]}A_{uv}d_{v}-d_{u}\right)\,\mathbbm{1}_{\{d_{u}\neq 0\}}, where A=(A_{uv})_{u,v\in[n]} is the adjacency matrix of G_{n} , i.e., A_{uv} is the number of edges between u\neq v while A_{uu} is twice the number of self-loops at u , and d_{u}=\sum_{v\in[n]}A_{uv} is the degree of u . Then the friendship paradox says that \frac{1}{n}\sum_{u\in[n]}\Delta_{u,n}\geq 0, with equality if and only if all connected components of G_{n} are regular. Typically, there are u for which \Delta_{u,n} is >0 , =0 , <0 . Even though the average is non-negative, there are graphs for which the number of vertices u with \Delta_{u,n}<0 is larger than the number of vertices u with \Delta_{u,n}>0 . One of the goals of the present paper is to analyse the number and the arrangement of such vertices in finite trees and infinite trees . The friendship paradox was introduced in 1991 by the American sociologist Scott Feld [ 7 ] . Since then, numerous studies have explored and applied this paradox across various domains, including social sciences, information theory and epidemiology. For instance, researchers have used the friendship paradox to design efficient sampling methods for early detection of contagious outbreaks [ 4 ] , and to improve strategies for delivering information and monitoring its propagation [ 15 ] , as well as for reducing the spread of contagion [ 18 ] . The friendship paradox has applications in exploring the network, for example, quickly finding vertices of high degrees [ 1 ] and developing immunisation strategies [ 5 , 2 ] . Apart from being interesting in itself, the friendship paradox has useful generalisations and implications. For instance, the friendship-bias can be viewed as a centrality measure, akin to PageRank centrality [ 17 ] and degree centrality. Co-authorship networks of Physical Review journals and Google Scholar profiles reveal that on average the co-authors of a person have more collaborations, publications and citations than that person has themselves [ 6 ] . On Twitter, most users, on average, follow others who are more popular and more active, i.e., tend to have more followers and share more viral content than they do themselves [ 10 ] . The friendship paradox has implications for individual biases in perception and thought contagion as well, because our social norms are influenced by our perceptions of others, and are strongly shaped by the people around us [ 13 , 16 ] . Despite many practical examples, mathematically the friendship paradox has received only modest attention, and a proper quantification of friendship-biases in large-size networks is still lacking. In [ 3 ] , it is shown that a randomly chosen friend of a randomly chosen individual has stochastically more friends than that individual. In [ 8 ] , a quantification of the friendship paradox for sparse locally tree-like random graphs is carried out, and the notion of significance of the friendship paradox is introduced. Specifically, the friendship paradox is said to be asymptotically significant for a sequence of finite random graphs (G_{n})_{n\in\mathbb{N}} labelled by the number of vertices n if the proportion of vertices with non-negative friendship-bias converges in probability as n\to\infty to a number \geq\tfrac{1}{2} . Interestingly, it is shown that the friendship paradox is significant for the homogeneous Erdős-Rényi random graph, the inhomogeneous Erdős-Rényi random graph, as well as for a well-known case of the configuration model and the preferential attachment model. In [ 9 ] , the multi-level friendship paradox is analysed, which addresses the friendship paradox at higher levels of friendship. More specifically, by extending the notion of friendship-bias to a multi-level setting, using random walks on graphs and imposing additional constraints on the graph, it is shown that the k -level average friendship-bias is non-negative for each fixed k , regardless of whether k -level friends are explored via backtracking or non-backtracking random walks. In the present paper we develop a probabilistic framework for understanding and analysing the friendship paradox for trees. We isolate and quantify the local structure underlying the friendship paradox on trees, which has both deterministic and random features. By formulating the paradox in terms of vertex-level bias and type, we derive sharp results on the distribution and correlation of these types in tree environments. Our results yield a systematic framework for studying when and how the friendship paradox manifests itself in tree-like structures that arise naturally in real-world networks. 1.2 Notations Let (\mathcal{T}_{n},\phi) be a rooted tree with n\in\mathbb{N}\cup\{\infty\} vertices, vertex set V(\mathcal{T}_{n}) , and root vertex \phi . To label the vertices, use the Ulam-Harris method of labelling a tree: each vertex u\in V(\mathcal{T}_{n})\setminus\{\phi\} is labelled by a finite word \phi\,u^{1}\ldots u^{k} , where k\in\mathbb{N} and, for u\in V(\mathcal{T}_{n}) , the j th offspring of u is u_{j}=uj=\left\{\begin{array}[]{ll}\phi\,j,&\text{if $u=\phi$},\\[5.69046pt] \phi\,u^{1}\ldots u^{k}j,&\text{if $u=\phi\,u^{1}\ldots u^{k}$}.\end{array}\right. For u,v\in V(\mathcal{T}_{n}) , write u\sim v to indicate that vertex u is adjacent to vertex v . The edge set of \mathcal{T}_{n} is E(\mathcal{T}_{n})=\{\{u,v\}\colon\,u,v\in V(\mathcal{T}_{n}),u\sim v\} . Let d_{u} be the degree of a vertex u . Define the friendship-bias of u as \Delta_{u,n}=\frac{1}{d_{u}}\sum_{{v\in V(\mathcal{T}_{n})}\atop{v\sim u}}d_{v}-d_{u}, which represents the difference between the average degree of the neighbours of u and the degree of u itself. Throughout the paper we follow the natural convention of defining the empty