A

The multi-level friendship paradox for sparse random graphs

Stochastic Processes and their Applications, vol. 195, pp. 104873

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 𝑘 ∈ ℕ 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., 𝑘 = 𝑘 𝑛 , provided l i m 𝑛 → ∞ ⁡ 𝑘 𝑛 = ∞ 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.

Authors 3

  1. Frank den Hollander corresponding
  2. Leiden University

    Affiliation as printed

    Mathematical Institute, Leiden University, Einsteinweg 55, Leiden, 2333 CC, The Netherlands

Cited by 2 stored of 2

2 results

References 15

15 results