Over the past hundred years social relationships have evolved, making us increasingly more connected with those around the world in a wide variety of ways. In this post, I will tell you a story about the connectedness of social relationships, taking us from an early 20th century Hungarian author to an 18th century Swiss mathematician, to one of the largest tech giants of our era, and touch on some cool mathematics along the way.
In an attempt to articulate his observation of the growing interconnectedness within society, in 1929, Hungarian author Frigyes Karinthy famously suggested that any two individuals were connected by 6 friendships, which have been coined “degrees of separation.” In other words, given any other person, say famous actor Will Smith, you should be able to find 5 other people such that the 7 of you are connected by 6 friendships, as depicted below.
Philosophy and media aside, how can we actually mathematically encode and measure social relationships? The answer: graphs. First studied by the famous mathematician Leonhard Euler, a graph is simply a collection of vertices and the edges that connect them. For example, the above picture connecting you to Will Smith is a graph with 7 vertices and 6 edges. Euler famously used graphs to solve the Bridges of Konigsberg problem. Since then, graph theory has proven to be a powerful tool to solve many problems. Google has used graphs to encode the connectedness of websites across the internet, and Facebook has encoded the friendships of their users with their Facebook Friendship Graph. This Facebook Friendship Graph is pretty straight forward:
A vertex <=> A Facebook user
An edge connects two vertices <=> The two users are Facebook friends
To celebrate its 12th birthday, Facebook recently set about to actually compute the average degrees of separation between two Facebook users. In terms of the Facebook Friendship Graph, this amounts to finding the average distance (i.e. minimal edge-path length) between two vertices. This kind of computation can be done by brute force methods for small graphs. However, as of the writing of this post, there are about 1.6 billion Facebook users, and they are highly connected. That means there are over 1018 pairs of vertices whose distance needs to be checked, something that is simply too computationally intensive to do directly. So Facebook instead used a variety of techniques to statistically analyze this enormous data set, including hash functions, the Flajolet–Martin algorithm, and a powerful graph processing program Apache Giraph. Check out their blog post below where they explain their methods in greater detail.
Facebook found that the average distance between any two vertices in the Facebook Friendship Graph is approximately 4.57 so, in their language, there is an average of 3.57 degrees of separation between two users.
You can go to their blog and see the average distance between you and a random other Facebook user. Personally, I am an average distance of 4.15 away (i.e. 3.15 degrees of separation away) from anyone else, confirming my longtime suspicion that I am highly connected.