The multi-level friendship paradox for sparse random graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914243735977984 |
|---|---|
| author | Hazra, Rajat Subhra Hollander, Frank den Parvaneh, Azadeh |
| author_facet | Hazra, Rajat Subhra Hollander, Frank den Parvaneh, Azadeh |
| contents | In Hazra, den Hollander and Parvaneh (2025) 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\infty$ 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 \in \mathbb{N}$ obtained via a $k$-step exploration according to a backtracking or a non-backtracking random walk. We identify the limit of empirical distribution of the multi-level friendship biases as $n\to\infty$ and/or $k\to\infty$. 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=k_n$, provided $\lim_{n\to\infty} k_n = \infty$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_17724 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The multi-level friendship paradox for sparse random graphs Hazra, Rajat Subhra Hollander, Frank den Parvaneh, Azadeh Probability 05C80, 60C05, 60F15, 60J80, 60G50 In Hazra, den Hollander and Parvaneh (2025) 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\infty$ 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 \in \mathbb{N}$ obtained via a $k$-step exploration according to a backtracking or a non-backtracking random walk. We identify the limit of empirical distribution of the multi-level friendship biases as $n\to\infty$ and/or $k\to\infty$. 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=k_n$, provided $\lim_{n\to\infty} k_n = \infty$ 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. |
| title | The multi-level friendship paradox for sparse random graphs |
| topic | Probability 05C80, 60C05, 60F15, 60J80, 60G50 |
| url | https://arxiv.org/abs/2502.17724 |