The multi-level friendship paradox for sparse random graphs

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.