$\DeclareMathOperator\deg{deg}\DeclareMathOperator\ndeg{ndeg}\newcommand\abs[1]{\lvert#1\rvert}$The friendship paradox goes most people have fewer friends than their friends have on average. The original paper Feld - Why your friends have more friends than you do has a simple counter example: enter image description here (Figure 5, p. 1474).

My question is how exceptional is this example?

Even in some random graph models where some answer is tractable, the analysis of the distribution of a neighbour's degree deals with expectation. That is, in some models it is explicitly shown that the average difference between the mean number of friends of friends and the number of friends is positive, which is much less likely to get press attention I think.

Given any graph $G=(V,E)$ and $v\in V$, let $N(v) = \{w\in V:\{v,w\} \in E\}$ and $\deg(v) = \abs{N(v)}$. This is the number of friends of $v$. Now consider $\ndeg(v)= \sum_{w \in N(v)}\deg(w)$, the total friends of friends of $v$ and the distribution of $$ f(v) = \frac{\ndeg(v)}{\deg(v)} - \deg(v). $$ For a friendship paradox, $$ g = \abs{\{v:f(v)>0\}}-\abs{\{v:f(v)<0\}}>0. $$ For the graph pictured above, $$ \{f(v)\}_{v\in \{A,B,C,D,E,F\}}=\left\{ 1,1,-\frac13-\frac13,-\frac13,-\frac13 \right\}. $$ Clearly $g = -2$, and no paradox. But, the mean of $f$ is $1/9>0$.

The mean of $f$ is shown to be positive in the popular configuration model. And this is usually said to be evidence/proof of the friendship paradox. (Tangential question: is $g>0$ in this model?)

Now the question(s):

  1. Is the mean of $f$ positive for any graph?
  2. What are some equivalent conditions stated in terms of graph properties to $g >0$?

I can answer question 1, at least. The mean of $f$ is always positive (unless every connected component of the graph $G$ is regular, in which case the mean of $f$ is zero). To see this, we rewrite the sum of the values of $f$ as

$$\sum_{v \in V} f(v) = \sum_{v \in V} \sum_{w\text{ s.t. }\{v,w\} \in E} \left(\frac{\deg(w)}{\deg(v)} - 1\right) = \sum_{\{v,w\} \in E} \left(\frac{\deg(w)}{\deg(v)} + \frac{\deg(v)}{\deg(w)} - 2\right),$$

and each summand is positive by AM-GM. More explicitly, we have

$$\sum_{v \in V} f(v) = \sum_{\{v,w\} \in E} \frac{(\deg(v)-\deg(w))^2}{\deg(v)\deg(w)} \ge 0.$$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.