Friendship paradox친구 역설

It is a sampling bias

Pick a person at random and every person is equally likely: their degree follows the degree distribution \(p(k)\). Pick a friend instead and you arrive by following a link, and a person with \(k\) friends can be reached along \(k\) different links. So a friend is \(k\) times more likely to have \(k\) friends, and the friend’s degree follows

\[ q(k) = \frac{k\,p(k)}{\langle k\rangle}, \qquad \langle k_\text{friend}\rangle = \sum_k k\,q(k) = \frac{\langle k^2\rangle}{\langle k\rangle} \ge \langle k\rangle \]

The inequality holds because \(\langle k^2\rangle - \langle k\rangle^2 = \langle (k-\langle k\rangle)^2\rangle \ge 0\). In fact the gap is exactly \(\langle k_\text{friend}\rangle - \langle k\rangle = \sigma_k^2/\langle k\rangle\): the more unequal the degrees, the stronger the paradox. Hubs are simply easier to see. Run the survey yourself below with three ways of sampling.

“Friends are by definition friendly people, and your circle of friends will be a biased sample of the population because of it.”

M. E. J. Newman, Social Networks 25, 83 (2003)

Two ways to average your friends’ friends

The third sampler above did not land on \(\langle k_\text{friend}\rangle\). Picking a random person and then one of their friends weights every person equally, not every friendship. That gives the second classical version of the paradox, which Feld also wrote down in 1991, the mean of each individual’s mean number of friends’ friends:

\[ \langle k_\text{nn}\rangle = \frac{1}{N}\sum_i k_\text{nn}(i) = \frac{1}{N}\sum_i \frac{1}{k_i}\sum_j a_{ij}k_j = \frac{1}{N}\sum_{(i,j)\in E}\left(\frac{k_j}{k_i}+\frac{k_i}{k_j}\right) \ge \frac{2M}{N} = \langle k\rangle \]

Each edge contributes \(x + 1/x\) with \(x = k_j/k_i\), and \(x + 1/x \ge 2\) for every \(x>0\), so this version holds too. Kumar, Krackhardt and Feld call \(\langle k_\text{friend}\rangle\) the alter-based mean and \(\langle k_\text{nn}\rangle\) the ego-based mean. They are not the same number. Feld’s own example keeps the degrees fixed (four people with three friends and twelve with one) and only changes who is friends with whom. The alter-based mean stays at 2; the ego-based mean does not.

The exact gap between the two

Multiply \(k_\text{nn}(i)\) by \(k_i\) and sum over nodes: \(\sum_i k_i\,k_\text{nn}(i) = \sum_{i,j} a_{ij}k_j = \sum_i k_i^2\), so \(\langle k\,k_\text{nn}\rangle = \langle k^2\rangle\) and \(\langle k_\text{friend}\rangle = \langle k\,k_\text{nn}\rangle/\langle k\rangle\). Subtract \(\langle k_\text{nn}\rangle\) and the difference is a covariance:

\[ \langle k_\text{friend}\rangle - \langle k_\text{nn}\rangle = \frac{\mathrm{Cov}_\text{n}(k, k_\text{nn})}{\langle k\rangle} \]

When well-connected people befriend each other (assortative mixing), the covariance is positive and the alter-based mean is larger. When hubs befriend loners (disassortative mixing), it is negative and the ego-based mean wins. Kumar, Krackhardt and Feld wrote the same gap with degree moments \(\kappa_m = \langle k^m\rangle\) and the inversity \(\rho\), the correlation over oriented edges between one end’s degree and the other end’s inverse degree:

\[ \langle k_\text{nn}\rangle - \langle k_\text{friend}\rangle = \rho\,\sqrt{\frac{\kappa_1\kappa_3-\kappa_2^2}{\kappa_1}\left(\kappa_{-1}-\kappa_1^{-1}\right)} \]

The two forms are identical. Below, rewire a 1,000-node scale-free network without changing anyone’s number of friends, and watch all three agree.

The extreme case: a complete bipartite network

Connect every member of a group of \(m\) to every member of a group of \(n\). Every link joins a degree-\(n\) node to a degree-\(m\) node, so the degree assortativity is \(r = -1\), and

\[ \langle k_\text{nn}\rangle = \frac{1}{m+n}\left(\frac{m}{n}\,mn + \frac{n}{m}\,nm\right) = \frac{m^2+n^2}{m+n} = \frac{mn^3+nm^3}{mn^2+nm^2} = \frac{\langle k^3\rangle}{\langle k^2\rangle} \]

With \(m = 1\) it is a star: the four-person network at the top is \(K_{1,3}\). NetworkX’s nx.complete_bipartite_graph(4, 5) gives \(\langle k_\text{nn}\rangle = 4.5556\), the same as \(\langle k^3\rangle/\langle k^2\rangle\).

Do most people’s friends have more friends?

Both classical versions are statements about averages. The everyday phrasing, “your friends have more friends than you”, sounds like a claim about most people, and the averages do not guarantee it. Two majority-type fractions make the claim precise. The global one compares each node with the mean of its neighbors:

\[ \phi_\text{global} = \frac{1}{N}\sum_i \mathbf{1}_{\{k_i < k_\text{nn}(i)\}} \]

The local one uses the hub centrality \(h_i\), the share of a node’s neighbors with strictly fewer friends. If \(h_i < 1/2\), most of the node’s friends have at least as many friends as it does, a median-based kind of domination:

\[ h_i = \frac{1}{k_i}\sum_{j\in\mathcal{N}(i)} \mathbf{1}_{\{k_j < k_i\}}, \qquad \phi_\text{local} = \frac{1}{N}\sum_i \mathbf{1}_{\{h_i < 1/2\}} \]

Neither fraction is constrained by the classical paradox, and they need not agree with each other. A single very popular friend raises the mean of a node’s neighbor degrees but barely moves the median. Each dot below is a node, placed by its two contrasts: the four quadrants are the four combinations of mean-based and median-based domination.

Your friends are also richer, busier and more cited

The paradox spreads to anything that goes along with having many friends: wealth, productivity, citations, happiness on social media. If an attribute \(x\) tends to grow with degree, your friends tend to have more of it than you do. This is the generalized friendship paradox, which Eom and Jo found among coauthors: most scientists’ collaborators have more papers and citations than they do. Below, each person gets a made-up attribute that follows their degree as strongly as you choose, with a skewed, log-normal spread like income or citations.