Friendship paradox

The same observation was also applied more generally to social networks defined by other relations than friendship: for instance, most people's sexual partners have had (on the average) a greater number of sexual partners than they have.

The friendship paradox is an example of how network structure can significantly distort an individual's local observations.

Mathematical explanation

In spite of its apparently paradoxical nature, the phenomenon is real, and can be explained as a consequence of the general mathematical properties of social networks. The mathematics behind this are directly related to the arithmetic-geometric mean inequality and the Cauchy–Schwarz inequality.

Formally, Feld assumes that a social network is represented by an undirected graph G = (V, E), where the set V of vertices corresponds to the people in the social network, and the set E of edges corresponds to the friendship relation between pairs of people. That is, he assumes that friendship is a symmetric relation: if x is a friend of y, then y is a friend of x. The friendship between x and y is therefore modeled by the edge {x, y}, and the number of friends an individual has corresponds to a vertex's degree. The average number of friends of a person in the social network is therefore given by the average of the degrees of the vertices in the graph. That is, if vertex v has d(v) edges touching it (representing a person who has d(v) friends), then the average number μ of friends of a random person in the graph is

${\displaystyle \mu =\frac{\sum _{v\in V}d(v)}{|V|}=\frac{2|E|}{|V|}.}$

The average number of friends that a typical friend has can be modeled by choosing a random person (who has at least one friend), and then calculating how many friends their friends have on average. This amounts to choosing, uniformly at random, an edge of the graph (representing a pair of friends) and an endpoint of that edge (one of the friends), and again calculating the degree of the selected endpoint. The probability of a certain vertex ${\displaystyle v}$ to be chosen is

${\displaystyle \frac{d(v)}{|E|}\frac{1}{2}.}$

The first factor corresponds to how likely it is that the chosen edge contains the vertex, which increases when the vertex has more friends. The halving factor simply comes from the fact that each edge has two vertices. So the expected value of the number of friends of a (randomly chosen) friend is

${\displaystyle \sum _v\left(\frac{d(v)}{|E|}\frac{1}{2}\right)d(v)=\frac{\sum _{v}d(v{)}^2}{2|E|}.}$

We know from the definition of variance that

${\displaystyle \frac{\sum _{v}d(v{)}^2}{|V|}={\mu }^2+{\sigma }^2,}$

where ${\displaystyle {\sigma }^2}$ is the variance of the degrees in the graph. This allows us to compute the desired expected value as

${\displaystyle \frac{\sum _{v}d(v{)}^2}{2|E|}=\frac{|V|}{2|E|}({\mu }^2+{\sigma }^2)=\frac{{\mu }^2+{\sigma }^2}{\mu }=\mu +\frac{{\sigma }^2}{\mu }.}$

For a graph that has vertices of varying degrees (as is typical for social networks), ${\displaystyle {\sigma }^2}$ is strictly positive, which implies that the average degree of a friend is strictly greater than the average degree of a random node.

Another way of understanding how the first term came is as follows. For each friendship (u, v), a node u mentions that v is a friend and v has d(v) friends. There are d(v) such friends who mention this. Hence the square of d(v) term. We add this for all such friendships in the network from both the u's and v's perspective, which gives the numerator. The denominator is the number of total such friendships, which is twice the total edges in the network (one from the u's perspective and the other from the v's).

After this analysis, Feld goes on to make some more qualitative assumptions about the statistical correlation between the number of friends that two friends have, based on theories of social networks such as assortative mixing, and he analyzes what these assumptions imply about the number of people whose friends have more friends than they do. Based on this analysis, he concludes that in real social networks, most people are likely to have fewer friends than the average of their friends' numbers of friends. However, this conclusion is not a mathematical certainty; there exist undirected graphs (such as the graph formed by removing a single edge from a large complete graph) that are unlikely to arise as social networks but in which most vertices have higher degree than the average of their neighbors' degrees.

The Friendship Paradox may be restated in graph theory terms as "the average degree of a randomly selected node in a network is less than the average degree of neighbors of a randomly selected node", but this leaves unspecified the exact mechanism of averaging (i.e., macro vs micro averaging). Let ${\displaystyle G=(V,E)}$ be an undirected graph with ${\displaystyle |V|=N}$ and ${\displaystyle |E|=M}$, having no isolated nodes. Let the set of neighbors of node ${\displaystyle u}$ be denoted ${\displaystyle \mathrm{nbr}(u)}$. The average degree is then ${\displaystyle \mu =\frac{1}{N}\sum _{u\in V}|\mathrm{nbr}(u)|=\frac{2M}{N}\ge 1}$. Let the number of "friends of friends" of node ${\displaystyle u}$ be denoted ${\displaystyle \mathrm{FF}(u)=\sum _{v\in \mathrm{nbr}(u)}|\mathrm{nbr}(v)|}$. Note that this can count 2-hop neighbors multiple times, but so does Feld's analysis. We have ${\displaystyle \mathrm{FF}(u)\ge |\mathrm{nbr}(u)|\ge 1}$. Feld considered the following "micro average" quantity.

${\displaystyle \text{MicroAvg}=\frac{\sum _{u\in V}\mathrm{FF}(u)}{\sum _{u\in V}|\mathrm{nbr}(u)|}}$

However, there is also the (equally legitimate) "macro average" quantity, given by

${\displaystyle \text{MacroAvg}=\frac{1}{N}\sum _{u\in V}\frac{\mathrm{FF}(u)}{|\mathrm{nbr}(u)|}}$

The computation of MacroAvg can be expressed as the following pseudocode.

<b>Algorithm</b> MacroAvg

1. for each node ${\displaystyle u\in V}$
   1. initialize ${\displaystyle Q(u)\leftarrow 0}$
2. for each edge ${\displaystyle \{u,v\}\in E}$
   1. ${\displaystyle Q(u)\leftarrow Q(u)+\frac{|\mathrm{nbr}(v)|}{|\mathrm{nbr}(u)|}}$
   2. ${\displaystyle Q(v)\leftarrow Q(v)+\frac{|\mathrm{nbr}(u)|}{|\mathrm{nbr}(v)|}}$
3. return ${\displaystyle \frac{1}{N}\sum _{u\in V}Q(u)}$

• "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item.
• "return" terminates the algorithm and outputs the following value.

Each edge ${\displaystyle \{u,v\}}$ contributes to MacroAvg the quantity ${\displaystyle \frac{|\mathrm{nbr}(v)|}{|\mathrm{nbr}(u)|}+\frac{|\mathrm{nbr}(u)|}{|\mathrm{nbr}(v)|}\ge 2}$, because ${\displaystyle \underset{a,b>0}{min}\frac{a}{b}+\frac{b}{a}=2}$. We thus get

${\displaystyle \text{MacroAvg}=\frac{1}{N}\sum _{u\in V}Q(u)\ge \frac{1}{N}\cdot M\cdot 2=\frac{2M}{N}=\mu }$.

Thus, we have both ${\displaystyle \text{MicroAvg}\ge \mu }$ and ${\displaystyle \text{MacroAvg}\ge \mu }$, but no inequality holds between them.

In a 2023 paper, a parallel paradox, but for negative, antagonistic, or animosity ties, termed the "enmity paradox," was defined and demonstrated by Ghasemian and Christakis. In brief, one's enemies have more enemies than one does, too. This paper also documented diverse phenomena is "mixed worlds" of both hostile and friendly ties.