Node-based generalized friendship paradox fails

Abstract

The Friendship Paradox-the principle that "your friends have more friends than you do"-is a combinatorial fact about degrees in a graph; but given that many web-based social activities are correlated with a user's degree, this fact has been taken more broadly to suggest the empirical principle that "your friends are also more active than you are." This Generalized Friendship Paradox, the notion that any attribute positively correlated with degree obeys the Friendship Paradox, has been established mathematically in a network-level version that essentially aggregates uniformly over all the edges of a network. Here we show, however, that the natural node-based version of the Generalized Friendship Paradox-which aggregates over nodes, not edges-may fail, even for degree-attribute correlations approaching 1. Whether this version holds depends not only on degree-attribute correlations, but also on the underlying network structure and thus can't be said to be a universal phenomenon. We establish both positive and negative results for this node-based version of the Generalized Friendship Paradox and consider its implications for social-network data.

Figure 1

Starting with an SGPF-failing graph such as this, we could grow it by adding nodes so that each new graph still fails SGFP and the degree-attribute correlation approaches 1.

Figure 2

Adding nodes in a specific way preserves the Singular Generalized Friendship Paradox gap sign and increases the degree-attribute correlation to the limit of 1. This figure is an example of a first step of this process, with new nodes and edges in green.

Figure 3

Degree-attribute correlation for the 8-node example in Fig. 1 as we add pairs of triple-2 and triple-3 nodes.

Figure 4

An anti-SGFP graph such as this may produce differently-signed gaps for $r_{d,a}=0$, depending on the attribute sample.

Figure 5

Plotting $r_{d,a}$ and the gap for 100 Facebook100 networks with “proportion of friends with the same reported gender” (including NULL) as attribute. For 9 schools, the gap is negative while $r_{d,a}$ is positive. These are real-world examples of failing SGFP with attributes positively correlated with degree.

Figure 6

For Facebook100 data, it’s possible to find SGFP-failing attribute samples with $r_{d,a}$ up to 0.45. When we remove social structure with a configuration model, the correlations we find with Simplex optimization are much lower.