Disparity-persistence and the multistep friendship paradox

Abstract

In this paper, we consider the friendship paradox in the context of random walks and paths. Among our results, we give an equality connecting long-range degree correlation, degree variability, and the degree-wise effect of additional steps for a random walk on a graph. Random paths are also considered, as well as applications to acquaintance sampling in the context of core-periphery structure.

1. Introduction

The friendship paradox, introduced by Feld in [15], states roughly that your friends have more friends than you do on average (for an explicit statement, see Theorem 1.1). Following the work of [24], extending the friendship paradox to multiple steps (i.e., iterated friendships), here we quantify an explicit connection between long-range degree correlation, degree variability, and the degree-wise effect of additional steps for random walks on a graph. Results for random paths are also considered.

Throughout, we suppose $G=(\mathcal{V},\mathcal{E})$ is a connected graph with node set $\mathcal{V}=\{v_1,v_2,\ldots,v_n\}$ and undirected edge set $\mathcal{E}$ and define the degree function $\mathrm{d}$, so that for $v\in \mathcal{V}$, $\mathrm{d}(v)$ is the degree of v (i.e., the number of neighbors of v) in G. Moreover, we denote by $\bf{A}=[A_{i,j}]$ the associated n × n adjacency matrix; the degree of a node v_i can then be computed via

\begin{align*} \mathrm{d}(v_i)=\sum_{j=1}^{n}A_{i,j}. \end{align*}

As we will be interested in the expected degree over random sequences of nodes in the graph, it will be convenient to consider a time-homogeneous random walk $\bf{X}=(X_0,X_1,\ldots)$ dictated by a transition matrix, $\bf{P}=[P_{i,j}]$, with

\begin{align*} P_{i,j}\stackrel{\rm def}{=} \mathbb{P}(X_{k+1}=v_j\mid X_k=v_i)=\frac{A_{i,j}}{\mathrm{d}(v_i)}, \end{align*}

for $1\leq i$, $j\leq n$, and $k\geq 0$. Importantly, we will assume throughout that X ₀ is uniformly selected from V.

We first restate the friendship paradox formalized in [15].

Theorem 1.1. ([15]) Suppose X ₀ is a node selected uniformly at random from $\mathcal{V}$, and $E=\{V,W\}$ is an edge pair selected uniformly at random from $\mathcal{E}$. Then, selecting Y ₁ from the nodes in E, each with half chance,

(1)\begin{align} \mathbb{E}(\mathrm{d}(Y_1))\geq \mathbb{E}(\mathrm{d}(X_0)). \end{align}

Similarly, several authors have employed the following counterpart for random walks with a uniformly selected initial node X ₀ (see for instance [3, 6, 21]).

Theorem 1.2. Suppose $\bf{X}=(X_0,X_1,X_2,\ldots)$ is a simple random walk on the graph G, where X ₀ is selected uniformly at random from $\mathcal{V}$. Then

(2)\begin{align} \mathbb{E}(\mathrm{d}(X_1))\geq \mathbb{E}(\mathrm{d}(X_0)). \end{align}

The following two results regarding multiple step walks and paths can be found in [24].

Theorem 1.3. ([24]) Suppose $\bf{X}=(X_0,X_1,X_2,\ldots)$ is a simple random walk on the graph G, where X ₀ is selected uniformly at random from $\mathcal{V}$. Then, for $k\geq 0$,

(3)\begin{align} \mathbb{E}(\mathrm{d}(X_k))\geq \mathbb{E}(\mathrm{d}(X_0)). \end{align}

Theorem 1.4. ([24]) Suppose $k\geq 1$ is odd, X ₀ is selected uniformly at random from $\mathcal{V}$, and $W=\{Y_0,Y_1,\ldots,Y_k\}$ is a path selected uniformly at random from the set of all length-k paths on G. Then, we have

(4)\begin{align} \mathbb{E}(\mathrm{d}(Y_k))\geq \mathbb{E}(\mathrm{d}(X_0)). \end{align}

For further recent theoretical results regarding the friendship paradox, see for instance [4, 5, 12, 31].

In place of comparisons with $\mathbb{E}(\mathrm{d}(X_0))$, as in the results above, the primary concern of this paper is the study of the degree-wise benefit of additional steps on the graph (for both random walks and random paths). Motivation for such considerations is provided by the recent success of applications of the one-step friendship paradox (see [8, 9, 14, 18, 20, 23, 34]).

Several authors have alluded to weakness in expression of the friendship paradox in networks exhibiting positive degree correlation over edges (see for instance [5, 25, 28, 31]). Before formally stating our results, it will be convenient to consider longer-range degree correlation. It is common for networks to exhibit sharing of similar characteristics across edges (i.e., “homophily,” “birds of a feather flock together,” “assortativity”; see [29]). In social networks, in particular, individuals may prefer to be associated with others sharing, for instance, similar age, education, or occupations. In the case where the characteristic of interest is nodal degree, Pearson correlation $\rho=\rho(G)$ refers to the tendency of nodes in a network to be associated with others sharing similar (or different) degrees. Specifically, for the graph G, suppose $E=\{V,W\}$ is an edge selected uniformly at random, then

(5)\begin{align} \rho\stackrel{\rm def}{=}\mathrm{cor}(\mathrm{d}(V),\mathrm{d}(W))=\frac{\mathrm{cov}(\mathrm{d}(V),\mathrm{d}(W))}{\mathrm{sd}(\mathrm{d}(V))\ \mathrm{sd}(\mathrm{d}(W))}. \end{align}

A positive degree correlation, ρ > 0, indicates a tendency for high-degree nodes in the graph to connect to other high-degree nodes and similarly for low-degree nodes.

Values of ρ have been studied in various classes of networks (see [7, 16, 26, 33]). For connections between assortativity and other topological network properties, see [11, 13, 36, 37]. For work considering assortativity in the context of the friendship paradox, see for instance [22, 25, 28, 31]. See [30] and the references therein for some further work on assortativity.

Although much previous research has focused on degree correlation among nearest neighbors, some recent considerations of the concept of assortative mixing beyond first neighbors can be found in [1, 2, 17, 27] and can in a general sense be referred to as long-range degree correlation (see [2]).

Assortativity, as defined in [29], can be interpreted as a measure of the correlation between nodal degrees based on the first-order adjacency matrix. Here, we define the kth-order path-based degree correlation as the Pearson coefficient, measuring the correlation between degrees for the two end points of a randomly chosen path with length k.

Definition 1.5. For $k \geq 0$, let $Y_k^-$ and $Y_k^+$ be the beginning and terminal nodes for a path selected uniformly at random from the set of all length-k paths on G. The kth-order (path-based) degree correlation $\rho_{0,k}$ is given by

\begin{align*} \rho_{0,k}\stackrel{\rm def}{=} \mathrm{cor}(\mathrm{d}(Y_k^-),\mathrm{d}(Y_{k}^+))=\frac{\mathrm{cov}(\mathrm{d}(Y_k^-),\mathrm{d}(Y_k^+))}{\mathrm{sd}(\mathrm{d}(Y_k^-))\ \mathrm{sd}(\mathrm{d}(Y_{k}^+))}. \end{align*}

In parallel with the definition above, we also consider the walk-based degree correlation as that for the starting node, X ₀, of a random walk $\bf{X}=(X_0,X_1,X_2,\ldots)$ (with uniform initial distribution) and the node reached at the walk’s kth step, X_k. Note that the use of the uniform distribution here is motivated by the desired applications. This is in contrast to recent work regarding long-range correlation, wherein the initial distribution is stationary for the corresponding Markov chain (see [2, 19, 32]).

Definition 1.6. Consider a random walk, $\bf{X}=\{X_0, X_1, X_2, \ldots\}$, on the graph G (with uniform initial distribution). The kth-order (walk-based) degree correlation, $\phi_{0,k}=\phi_{0,k}(\bf{X})$, is given by

\begin{align*} \phi_{0,k}\stackrel{\rm def}{=} \mathrm{cor}(\mathrm{d}(X_0),\mathrm{d}(X_k))=\frac{\mathrm{cov}(\mathrm{d}(X_{0}),\mathrm{d}(X_{k}))}{\mathrm{sd}(\mathrm{d}(X_{0}))\ \mathrm{sd}(\mathrm{d}(X_{k}))}. \end{align*}

Note. As an aside, it may be of some value to consider applications for which $\phi_{0,1}$ as in Definition 1.6 may be of interest. The correlation computed involves the same node pairs as in (5) but with weighting in a manner that places equal emphases on each node regardless of degree. Ties in a sense are weaker (or diluted) for nodes of large degree.

Now, for the random walk $\bf{X}=(X_0,X_1,\dots)$, let $X_\infty$ be a node selected according to the stationary distribution $\pi=(\pi_1, \dots, \pi_n)$ of the random walk X, that is, $\pi_i=\mathrm{d}(v_i)/\sum_j \mathrm{d}(v_j)$. A main quantity of interest will be what we term the proportional residual benefit at time k for the walk, which measures the degree-wise (remaining) benefit of additional steps of a random walk.

Definition 1.7. The proportional residual benefit for the walk X at time k, $\tau_k=\tau_k(\bf{X})$ is given by

\begin{align*} \tau_k\stackrel{\rm def}{=}\frac{\mathbb{E}(\mathrm{d}(X_\infty))-\mathbb{E}(\mathrm{d}(X_k))}{\mathbb{E}(\mathrm{d}(X_k))}. \end{align*}

We now have the following quantitative relationship between the walk-based long-range degree correlation and the proportional residual benefit. The proof is provided in Section 2. Throughout, for a random variable U with finite second moment, we denote by $\mathrm{c_v}(U)$, the coefficient of variation of U, that is,

(6)\begin{align} \mathrm{c_v}(U)\stackrel{\rm def}{=}\frac{\mathrm{sd}(U)}{\mathbb{E}(U)}. \end{align}

Theorem 1.8. Suppose $\bf{X}=(X_0,X_1,\ldots)$ is a random walk on the graph G. The proportional residual benefit τ_k can be written as the product of the kth-order degree correlation $\phi_{0,k}$ and the two coefficients of variation, $c_v(\mathrm{d}(X_0))$ and $c_v(\mathrm{d}(X_k))$, that is

(7)\begin{align} \tau_k&=\mathrm{cor}(\mathrm{d}(X_{0}),d(X_{k}))\cdot\frac{\mathrm{sd}(\mathrm{d}(X_{0}))}{\mathbb{E}(\mathrm{d}(X_{0}))}\cdot\frac{\mathrm{sd}(\mathrm{d}(X_{k}))}{\mathbb{E}(\mathrm{d}(X_{k}))}\nonumber \\ &=\phi_{0,k}\ c_v(\mathrm{d}(X_0)) c_v(\mathrm{d}(X_k)). \end{align}

Now, as in Definition 1.5, for $k \geq 0$, let $Y_k^-$ and $Y_k^+$ be the beginning and terminal nodes for a path selected uniformly at random from the set of all length-k paths. We have the following definition and result.

Definition 1.9. Suppose $k\geq 0$. The proportional one-step benefit at length k, γ_k, is given by

\begin{align*} \gamma_k\stackrel{\rm def}{=}\frac{\mathbb{E}(\mathrm{d}(Y_{k+1}^+))-\mathbb{E}(\mathrm{d}(Y_k^+))}{\mathbb{E}(\mathrm{d}(Y_k^+)))}. \end{align*}

Theorem 1.10. The proportional one-step benefit, γ_k, at length k can be written as the product of the kth-order degree correlation $\rho_{0,k}$ and the two coefficients of variation, ${c_v}(\mathrm{d}(Y_{k}^-))$ and ${c_v}(\mathrm{d}(Y_{k}^+))$, that is,

(8)\begin{align} \gamma_k&= \mathrm{cor}(\mathrm{d}(Y_{k}^-),\mathrm{d}(Y_{k}^+))\cdot \frac{\mathrm{sd}(\mathrm{d}(Y_{k}^-))}{\mathbb{E} (\mathrm{d}(Y_{k}^-))}\cdot\frac{\mathrm{sd}(\mathrm{d}(Y_{k}^+))}{\mathbb{E}(\mathrm{d}(Y_{k}^+))} \nonumber \\ &=\rho_{0,k}\ {c_v}(\mathrm{d}(Y_{k}^-))\ {c_v}(\mathrm{d}(Y_{k}^+)). \end{align}

In terms of residual benefit, in the case of random paths, we will also prove the following.

Theorem 1.11. Suppose G is a non-bipartite (and connected) graph. If $\bf{(a)}$ $k\geq 0$ is even or $\bf{(b)}$ $k\geq 1$ is odd and the corresponding kth-order path-based degree correlation $\rho_{0,k}$ is nonnegative, then the limiting expected degree of $Y_i^+$ is no less than that of $Y_k^+$, that is,

(9)\begin{align} \lim_{i\rightarrow \infty} \mathbb{E}(\mathrm{d}(Y_i^+)) \geq \mathbb{E}(\mathrm{d}(Y_k^+)). \end{align}

Note. (Disparity persistence and core-periphery structure) Theorems 1.8, 1.10, and 1.11 provide insight into when it may be beneficial in acquaintance sampling and elsewhere to continue on to neighbors of neighbors in an iterated fashion. In fact, the benefit can be high in networks wherein the degree correlation is positive out to a longer range, but, globally, the degree variability is high. We refer to such a phenomenon as disparity-persistence, since disparity in degree persists over extended neighborhoods. A prime example wherein such behavior can occur is social networks exhibiting strong core-periphery structure, with a large core of high-degree nodes and a periphery of loosely connected nodes, with low degree.

The remainder of the paper proceeds as follows. In Section 2, we prove Theorem 1.8, while in Section 3, we prove Theorems 1.10 and 1.11.

2. Proof of Theorem 1.8 (The random walk case)

In this section, we will prove Theorem 1.8.

Proof of Theorem 1.8

Set $d_i=\mathrm{d}(v_i)$, $\bf{d}=(d_1,d_2,\ldots,d_n)^{\prime}$, and $\bf{1}=(1,1,\ldots,1)^{\prime}$. Let P be the transition matrix for the random walk, X, and note that $\bf{d}=\bf{A} \bf{1}$. Now, note that

\begin{align*} \mathbb{E}\left(\mathrm{d}(X_0)\ \mathrm{d}(X_k)\right)=\frac{1}{n}\sum_i\sum_j d_id_j (\bf{P}^k)_{i,j} =\frac{\bf{d}^{\prime}\bf{P}^k\bf{d}}{\bf{1}^{\prime}\bf{1}}. \end{align*}

Hence, letting D be the diagonal matrix with diagonal d and noting that $\bf{P}=\bf{D}^{-1}\bf{A}$ gives

\begin{align*} \bf{d}^{\prime}\bf{P}^{k}\bf{d}&=\bf{d}^{\prime}\bf{D}^{-1}\bf{A}\bf{P}^{k-1}\bf{d} = \bf{1}^{\prime}\bf{A}\bf{P}^{k-1}\bf{d} = \bf{d}^{\prime}\bf{P}^{k-1}\bf{d} \\ &=\cdots = \bf{d}^{\prime}\bf{d}. \end{align*}

Thus,

\begin{align*} \mathbb{E}(\mathrm{d}(X_0)\ \mathrm{d}(X_k))=(\bf{d}^{\prime}\bf{d})/(\bf{1}^{\prime}\bf{1}). \end{align*}

Now,

\begin{align*} \mathbb{E}(\mathrm{d}(X_\infty))&=\sum_i \left(\frac{d_i}{\sum_j d_j}\right)d_i=\frac{\bf{d}^{\prime}\bf{d}}{\bf{1}^{\prime}\bf{A}\bf{1}},\\ \mathbb{E}(\mathrm{d}(X_0))&=\frac{1}{n}\sum_i d_i=\frac{\bf{1}^{\prime} \bf{A} \bf{1}}{\bf{1}^{\prime}\bf{1}}, \end{align*}

and hence

\begin{align*} \mathbb{E}(\mathrm{d}(X_\infty))\cdot\mathbb{E}(\mathrm{d}(X_0))=\frac{\bf{d}^{\prime}\bf{d}}{\bf{1}^{\prime}\bf{A}\bf{1}}\frac{\bf{1}^{\prime} \bf{A} \bf{1}}{\bf{1}^{\prime}\bf{1}}=\frac{\bf{d}^{\prime}\bf{d}}{\bf{1}^{\prime}\bf{1}}= \mathbb{E}\left(\mathrm{d}(X_0)\ \mathrm{d}(X_k)\right). \end{align*}

Thus,

\begin{align*} \tau_k&=\frac{\mathbb{E}(\mathrm{d}(X_\infty))-\mathbb{E}(\mathrm{d}(X_k))}{\mathbb{E}(d(X_k))},\\ &= \frac{1}{\mathbb{E}(\mathrm{d}(X_k))}\left(\frac{\mathbb{E}(\mathrm{d}(X_0)\ \mathrm{d}(X_k))}{\mathbb{E}(\mathrm{d}(X_0))}-\mathbb{E}(\mathrm{d}(X_k))\right), \\ &= \frac{\mathrm{cov}(d(X_0),d(X_k))}{\mathbb{E}(\mathrm{d}(X_k))\cdot\mathbb{E}(\mathrm{d}(X_0))}, \\ &= \phi_{0,k}\left(\frac{\mathrm{sd}(\mathrm{d}(X_0))}{\mathbb{E}(\mathrm{d}(X_0))}\right)\cdot\left(\frac{\mathrm{sd}(\mathrm{d}(X_k))}{\mathbb{E}(\mathrm{d}(X_k))}\right)=\phi_{0,k}\ {c_v}(\mathrm{d}(X_0)) {c_v}(\mathrm{d}(X_k)).\\[-42pt] \end{align*}

We easily derive the following corollary.

Corollary 2.1. Suppose $\bf{X}=(X_0,X_1,\ldots)$ is a random walk on the graph $G=(\mathcal{V},\mathcal{E})$. For $k\geq 1$, the expected degree of $X_\infty$ is no less than that of X_k if and only if the kth-order degree correlation $\phi_{0,k}$ is nonnegative, that is,

(10)\begin{align} \mathbb{E}(\mathrm{d}(X_\infty))\geq \mathbb{E}(\mathrm{d}(X_k)) \quad \text{if and only if} \quad \phi_{0,k}=\mathrm{cor}(\mathrm{d}(X_{0}), \mathrm{d}(X_{k}))\geq 0. \end{align}

3. Proof of Theorems 1.10 and 1.11 (The random path case)

In this section, we will prove Theorem 1.10 and further discuss the relationship between the proportional one-step benefit γ_k and the path-based degree correlation $\rho_{0,k}$ in parallel with the random-walk case, $(X_k)_{k\geq 0}$. As per convention, throughout, we will take the zeroth power of the adjacency matrix, A, of a graph G (i.e., A⁰) to be the n × n identity matrix, and hence for $k\geq 0$, the entry $(A^k)_{i,j}$ counts the number of distinct paths of length k connecting nodes v_i and v_j.

As before, suppose for $i \geq 0$, $Y_{i}^-$ and $Y_{i}^+$ are the beginning and terminal nodes of a path selected uniformly at random from the set of all length-i paths on G. We have the following lemma (see also Lemma 4 in [24]).

Lemma 3.1. Suppose $k\geq 0$. The expected degree of $Y_k^{+}$ can be written in terms of successive entries in the sequence $(N_0, N_1, \ldots)$, where N_j is the number of length j paths on G, that is,

(11)\begin{align} \mathbb{E}(\mathrm{d}(Y_k^{+}))=\frac{N_{k+1}}{N_k}. \end{align}

Proof. We have

\begin{align*} \mathbb{E}(\mathrm{d}(Y_k^{+}))=\sum_{j=1}^{n}d_j \frac{\sum_{i=1}^{n}A_{i,j}^{k}}{N_k}=\frac{\bf{d}^{\prime}(\bf{A}^{k})^{\prime}\bf{1}}{N_k}=\frac{\bf{1}^{\prime} \bf{A}\bf{A}^{k}\bf{1}}{N_k}=\frac{N_{k+1}}{N_k}, \end{align*}

where the third equality follows from the symmetry of the adjacency matrix, A.

Now we turn to a proof of Theorem 1.10.

Proof of Theorem 1.10

Suppose $k\geq 0$ and $Y_k^{-}$ and $Y_k^{+}$ are two nodes connected by a randomly chosen path with length k. We have

(12)\begin{align} \mathbb{E}(\mathrm{d}(Y_k^{-})\ \mathrm{d}(Y_k^{+}))=\sum_{i=1}^{n}\sum_{j=1}^{n}d_i d_j \frac{A_{i,j}^{k}}{N_k}=\frac{\bf{d}^{\prime}\bf{A}^{k}\bf{d}}{N_k}=\frac{N_{k+2}}{N_k}. \end{align}

Note that by Lemma 3.1 and symmetry,

(13)\begin{align} \mathbb{E}(\mathrm{d}(Y_k^{-}))=\frac{N_{k+1}}{N_k}=\mathbb{E}(\mathrm{d}(Y_k^{+})). \end{align}

Hence, using Eqs. (12) and (13),

(14)\begin{align} \mathrm{cov}(d(Y_k^{-}),d(Y_k^{+}))&=\frac{N_{k+2}}{N_k}-\left(\frac{N_{k+1}}{N_k}\right)^2=\frac{N_{k+1}}{N_k}\left(\frac{N_{k+2}}{N_{k+1}}-\frac{N_{k+1}}{N_k}\right),\nonumber \\ &=\mathbb{E}(d(Y_k^{+}))\cdot(\mathbb{E}(d(Y_{k+1}^+))-\mathbb{E}(d(Y_k^+))), \end{align}

and hence by the definition of γ_k, and Eqs. (13) and (14),

(15)\begin{align} \gamma_k&=\frac{\mathbb{E}(\mathrm{d}(Y_{k+1}^+))-\mathbb{E}(\mathrm{d}(Y_k^+))}{\mathbb{E}(\mathrm{d}(Y_k^+))}\cdot \frac{\mathbb{E}(\mathrm{d}(Y_{k}^+))}{\mathbb{E}(\mathrm{d}(Y_k^-))}\cdot\frac{\mathrm{sd}(\mathrm{d}(Y_{k}^-))}{\mathrm{sd}(\mathrm{d}(Y_k^-))}\cdot\frac{\mathrm{sd}(\mathrm{d}(Y_{k}^+))}{\mathrm{sd}(\mathrm{d}(Y_k^+))}, \nonumber\\ &=\frac{\mathrm{cov}(d(Y_k^-),d(Y_K^+))}{\mathrm{sd}(\mathrm{d}(Y_k^-))\ \mathrm{sd}(\mathrm{d}(Y_{k}^+))}\cdot \frac{\mathrm{sd}(\mathrm{d}(Y_k^-)}{\mathbb{E}(\mathrm{d}(Y_k^-))}\cdot \frac{\mathrm{sd}(\mathrm{d}(Y_{k}^+)}{\mathbb{E}(\mathrm{d}(Y_k^+))},\nonumber \\ &=\rho_{0,k}\ \mathrm{c_v}(\mathrm{d}(Y_k^-))\ \mathrm{c_v}(\mathrm{d}(Y_k^+)).\nonumber \\[-40pt] \end{align}

Therefore, the proportional increase in relative expected degree for an increase of one in the length of our random path can be determined by the corresponding path-based degree correlation, along with the two coefficients of variation. We have the following corollary.

Corollary 3.2. Suppose $k\geq 0$. The expected degree of $Y_{k+1}^{+}$ is no less than that of $Y_k^{+}$ if and only if the kth-order degree correlation $\rho_{0,k}$ is nonnegative, that is,

(16)\begin{align} \mathbb{E}(\mathrm{d}(Y_{k+1}^{+}))\geq \mathbb{E}(\mathrm{d}(Y_k^{+})) \quad\text{if and only if } \quad \rho_{0,k}=\mathrm{cor}(\mathrm{d}(Y_k^{-}), \mathrm{d}(Y_{k}^{+}))\geq 0. \end{align}

Note that employing an inequality on the number of paths, developed by [35] (with c = 1 and b = 0), we have

(17)\begin{align} \frac{N_{2a+1}}{N_{2a}}\leq \frac{N_{2a+2}}{N_{2a+1}} \end{align}

for $a\geq 0$, and hence by Lemma 3.1, when k is even, $\mathbb{E}(\mathrm{d}(Y_{k+1}^{+}))\geq \mathbb{E}(\mathrm{d}(Y_k^{+}))$. In the case k = 0, this is simply the result of Feld in Theorem 1.1. In addition, by Corollary 3.2, for any network G, G is assortative (i.e., $\rho_{0,1} \gt 0$) if and only if $\mathbb{E}(\mathrm{d}(Y_{2}^+)) \gt \mathbb{E}(\mathrm{d}(Y_1^+))$. For consideration of degree comparison for X ₁ and X ₂ under a random graph model, see [4].

The following lemma follows directly from eigen decomposition of the matrix A and Lemma 3.1 (see for instance [10]).

Lemma 3.3. ([10]) Suppose $k\geq 0$ and the graph G is non-bipartite. The expected degree of $Y_k^{+}$ tends to λ ₁, the largest eigenvalue of the adjacency matrix, A, as k tends to infinity, that is,

(18)\begin{align} \lim_{k\to\infty} E(\mathrm{d}(Y_k^+)) = \lambda_1. \end{align}

We now turn to a proof of Theorem 1.11

Proof of Theorem 1.11

Suppose $m\geq 0$. From Rayleigh’s inequality, we have

(19)\begin{align} \mathbb{E}(\mathrm{d}(Y_{2m}^+))=\frac{N_{2m+1}}{N_{2m}}=\frac{\left(\bf{A}^{m}\bf{1}\right)^{\prime}\bf{A}\left(\bf{A}^{m}\bf{1}\right)}{\left(\bf{A}^{m}\bf{1}\right)^{\prime}\cdot\left(\bf{A}^{m}\bf{1}\right)}\leq \lambda_1. \end{align}

The result for k even follows by Lemma 3.3. Now, suppose k is odd and $\rho_{0,k}\geq 0$. Employing Corollary 3.2 and Eq. (19) then gives

\begin{align*} \mathbb{E}(\mathrm{d}(Y_{k}^+))\leq \mathbb{E}(\mathrm{d}(Y_{k+1}^+))\leq \lambda_1, \end{align*}

and the result follows.