Social Network Friendship Paradox

Problem / Observation:

The friendship paradox is the phenomenon first observed by the sociologist Scott L. Feld in 1991 that most people have fewer friends than their friends have, on average. Prove it mathematically.


Update (23 Oct 2014):
Solution: Posted by Mike Earnest and Taz in comments!

Comments

  1. If the friendship graph is (V,E), the average number of friends people have is

    (1/|V|) Sum_{v in V} deg v = 2|E| / |V|

    The average of the average number of friends people's friends have is

    (1/|V|) Sum_{v in V} [ (1/deg v) Sum_{w in v's friends} deg w ]

    = (1/|V|) Sum_{v,w in V, v friends with w} (deg w)/(deg v) (*)

    Consider the summation in (*). For each edge, with endpoints v and w, there are two terms, (deg v)/(deg w) and (deg w)/(deg v). Since a/b + b/a is always at least 2 (to prove this, start with (a - b)^2 >= 0), this implies that (*) is at least (1 / |V|)*2 |E|, completing the proof.

    ReplyDelete
    Replies
    1. Thanks Mike. This solution is so better than any explanation I have read elsewhere. Thanks.

      Delete
  2. The number of friends people have would not be a normal distribution rather it would be left skewed. So majority of people will have only a few friends while only a small number of people will have lots of friends.

    Thanks to this second group (people with lots of friends) are more likely to number in your friends list. When they are actually part of your friends list, they would significantly skew the average number of friends that your friends have. Hence, on average, your friends will have more friends than you.

    ReplyDelete

Post a Comment