Can 90% Of People Do Worse Than Average?

In the first case, Dan is looking at the number of followers that the user has, $f^i$ .

That number should of course have the average value

$\langle f \rangle = \frac1N\sum\limits_i f^i$

In the second case, Dan is looking at the average number of followers that user $i$ 's followers have, $f_f^i$ .

This number is given by

$f_f^i = \frac{1}{f_i} \sum\limits_{j \in F_i} f_j$

where $F_i$ is the set of users who follow user $i$ . In other words, we are taking the average number of followers for users who follow user $i$ .

Though it may seem that the number in the second case should be the same (on average) as the number in the first case, it can in fact be quite different.

Consider the case of a friendship network that has the symmetric relation of "friendship", i.e., if $x$ is a friend of $y$ , then $y$ is a friend of $x$ . Suppose there are people in the network who have no friends.

When the average number of friends per user is calculated, the people with no friends will be included in the average.

When the average number of friends that a user's friends have is included (friend's friends), such people are explicitly left out of the calculation.

In other words, the average number friend's friends is fundamentally biased in favor of people who have friends.

The general principle is that this calculation overemphasizes the contributions from people who have more friends. This is known as the "friendship paradox".

One could ask how, if in any way, does the relation (friend or follower) contribute to this property? This can in general be a tough nut to crack, but we can explore the consequences of two simple network types:

• 1 the Twitter (and Brilliant) network where "following" is asymmetric ( $x$ can follow $y$ even when $y$ does not follow $x$ )
• 2 the Facebook network, where friendship is symmetric.

$\large\mbox{Twitter relation}$

On Twitter (and Brilliant), users are connected by directed edges: if an edge is directed from $x$ to $y$ , then $x$ follows $y$ or $x\rightarrow y$ . For $y\rightarrow x$ , we need a separate edge going in the opposite direction. Therefore, for everyone to follow everyone else, we require $n\left(n-1\right)$ edges, compared to the $\frac{n\left(n-1\right)}{2}$ for Facebook.

Consider a random network, generated according to the following prescription:

• Select a number of users and a number of following events.
• For each following event you wish to generate, randomly select two users (uniformly and without replacement) from the set of users.
• Create a directed edge from the second user to the first user, i.e. the second user follows the first.
• Repeat until you have the desired number of following events.

This kind of network can be easily implemented in the programming language of your choice. Before we look at the results of simulating such a network, let's think about the "follower" relationship between users in a random network (RN). In a RN, the act of gaining a follower is divorced from the act of following someone. A user is equally like to follow 10 people and be followed by nobody as they are to be followed by 10 people and follow nobody. We do not expect much bias in the calculation of follower's followers compared to a given user's followers (no friendship paradox).

Below are the results of 10,000 rounds of simulation of a random Brilliant style network. The network contains 30 users with 435 following events (1/2 of all possible following events).

• Mean number of followers $= \frac{435}{30} = 14.5$ (this must be the case)
• Mean number of follower's followers = $14.497 \pm 0.0364$
• Percent of users with fewer followers than their follower's followers = $49.6 \pm 0.06$

Indeed, in a random follower network, there does not seem to be a sampling bias in calculating the average number of follower's followers. Half the users are less popular than their friends.

$\large\mbox{Facebook relation}$

On Facebook, users are connected by undirected edges: if $x$ is friends with $y$ , then $y$ is friends with $x$ .

As with Brilliant, we can simulate such a network with a simple prescription:

• Select a number of users and a number of friendship events.
• For each friendship you wish to generate, randomly select two users (uniformly and without replacement) from the set of users.
• Create an edge from between the two users.
• Repeat until you have the desired number of friendship.

In this case, even in a random network, we expect to see a difference between a user's friends, and friend's friends. As we said before, friend's friends is a weighted average that disproportionately favors the contributions from popular users.

Below are the results of 10,000 rounds of simulation of a random Facebook style network. The network contains 30 users and 218 friendships ($\approx$ of all possible friendships).

• Mean number of friends = $2\times218/30$ = 14.5333 (this must be the case)
• Mean number of follower's followers = $15.0297 \pm 0.001$
• Percent of users with fewer followers than their follower's followers = $56.87 \pm 0.05$

We can see clearly that even in a completely random network, the structure of the friendship relation is enough to produce a measurable boost and manifest the friendship paradox. Nearly 57% of users are less popular than their friends, solely due to the structure of the friendship relation.

We can see a negative correlation between the number of friends that a user has, and the number of friends their friends have:

Here we show a smoothed histogram showing the likelihood for a user in either style network to experience the friendship paradox.

$\large\mbox{Analysis}$

The friendship paradox is a counterintuitive result. Let's see if we can shed any light on it.

As we said earlier, the typical user has $\langle f \rangle = \frac1N\sum\limits_i f^i = \langle k \rangle$ friends/followers.

To calculate friend's friends, we have to take into account the number of connections a user has, as well as the kinds of user they are more or less likely to connect to.

By type of user, we mean, "how many friends do they have?". Are they they kind of user with two friendships?, three?, four?, etc. Let the number of users with $k$ friends be $N(k)$ .

If we pick a random friendship in a random Facebook style network, the probability that one of the friends is a user with $k$ friends is equal to to

$\begin{aligned} \frac{kN(k)}{\sum\limits_k kN(k)} &= \frac{kp(k)}{\sum\limits_k kp(k)} \\ &= \frac{kp(k)}{\langle k \rangle} \end{aligned}$ .

Here we have used $p(k) = N(k)/N_{tot}$ , the probability for a user to have $k$ friends. Note, this doesn't hold in the Brilliant style random network.

So, we have the probability that any given friend of a user will have $k$ friends, given by $\frac{kp(k)}{\langle k \rangle}$ . We can now calculate the average number of friends that a user's friends have by averaging over all kinds of friends:

$\begin{aligned} \langle f_f^i \rangle &= \sum\limits_k k\frac{kp(k)}{\langle k \rangle} \\ &= \sum\limits_k \frac{k^2p(k)}{\langle k \rangle} \\ &= \frac{\langle k^2 \rangle}{\langle k \rangle} \end{aligned}$

Therefore, $\langle f_f^i \rangle = \frac{\langle k^2 \rangle}{\langle k \rangle}$ . We can make things more clear by rewriting this in terms of the variance and the mean. The variance of a list of numbers $s_i$ is given by $\sigma^2(s) = \langle s^2 \rangle - \langle s \rangle ^2$ .

Therefore, the average number of friend's friends in a random network is given by

$\langle f_f^i \rangle = \langle k \rangle + \frac{\sigma^2(k)}{\langle k \rangle}$

As the variance of a dataset is strictly positive, this shows that the average number of friend's friend's will always be higher than the average number of friends, as long as the variance is not zero, i.e. as long as every user doesn't have the same number of friends.

We can try this out on the Facebook network above. The average variance in the number of friends per user was 6.99 while the mean number of friends per user was 14.53. Based on this, we'd predict the average number of friend's friends to be $14.53 + 6.99/14.53 \approx 15.01$ which is very close to the measured value of 15.02.

$\large\mbox{Discussion}$

All of this seems to contradict the observation that Dan had about the Brilliant network, and it would if the Brilliant network were simply random, but it isn't.

The real Brilliant network likely reflects elements of the Twitter and Facebook style random networks. I.e. if user $x$ followers user $y$ there is a chance between zero (random Twitter network style) and one (Facebook style) for the reverse to happen.

The random networks we considered have a binomial distribution in the number of followers per user, which has relatively low variance. The real Brilliant network has a heavy tailed distribution with much more variance, i.e. a relatively few users have a large number of followers and and most have a few followers.

Moreover, users don't select who to follow at random. In addition to following their friends, Brilliant users tend to follow popular users. Simple reasons for this might be that the popular user often shares interesting problems, sets, and notes, or that they post useful solutions to problems. Because there is a non-uniform distribution of popular content generation across the user base, we expect content generation to have a non-uniform effect on following patterns, which boosts the magnitude of the friendship paradox as we showed above. If an extremely popular users refollows a small number of their followers, we further expect that to bias the count of follower's followers.

In summary, the cause for Dan's observation is that users follow (sample) the base of other users non-uniformly.