Exceptions to the Friendship Paradox

The Friendship Paradox says that your friends are likely to have more friends on average than you do. I was wondering whether there are settings in which the statement of the Friendship Paradox does not hold. Below we think about this question in precise mathematical terminology.

Friendships, social networks, and the like are often modelled using simple graphs. People are represented by vertices, and each edge denotes a pair of friends. The set of friends, or neighbors, of a vertex v is defined to be N(v) = \{w \in V(G) : \{v,w\} \in E(G)\}. The number of friends, or the degree of v\in V(G) is set to be \textrm{deg}(v) = \textrm{card}(N(v) and the average number of the friends of a person’s friends is defined by \textrm{ad}(v) = \textrm{avg}\{\textrm{deg}(w) : w \in N(v)\}.

We say that a person (or vertex) v is proud if \textrm{deg}(v) > 0 and \textrm{deg}(v) > \textrm{ad}(v). One interesting version of the question above is: Do there exist graphs such that more than half of the people are proud?

The following insight is elementary, but it was still a surprise for me: It turns out that the share of proud people can be arbitrarily close to 1.. In order to prove this, take any integer m > 4 and consider the complete graph on m points with one edge removed. It is easy to see that the 2 people adjacent to the sole edge that was removed are the only ones that are not proud. So the share of proud people is \frac{m-2}{m} which converges to 1 as m grows large.

About dominiczypen

I'm interested in general topology, order theory, and graph theory. This link takes you to my preprints on arXiv.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s