Six degrees of separation is the, already well established, idea that any individual is connected to any other via six network nodes. New research has discovered that the average between Facebook users is just three and a half.

Results of a research study by Sergey Edunov, Carlos Diuk, Ismail Onur Filiz, Smriti Bhagat and Moira Burke was posted on the Facebook blog on Friends Day, February 4th, Facebook's 12th birthday.

The Friends Day post states:

We know that people are more connected today than ever before. Over the past five years, the global Facebook community has more than doubled in size. Today we’re announcing that during that same time period, the degrees of separation between a typical pair of Facebook users has continued to decrease to 3.57 degrees, down from 3.74 degrees in 2011. This is a significant reflection of how closely connected the world has become.

More details are given by the researchers in the post Three and a half degrees of separation which concludes that:

Each person in the world (at least among the 1.59 billion people active on Facebook) is connected to every other person by an average of three and a half other people. 

The initial study of the degree of connectedness of the Facebook graph was done in 2011 by researchers at Cornell, the Università degli Studi di Milano, and Facebook, The computed the average path length, the number of arc in a path, across the 721 million people then using the site, corresponding to 69 billion friendship links, and found that it was 4.74, corresponding to 3.74 intermediaries or "degrees of separation".

Recrunching the Facebook graph in 2016 the corresponding distance 4.57, corresponding to 3.57 intermediaries or "degrees of separation." Within the US, people are connected to each other by an average of 3.46 degrees and majority of the people on Facebook have averages between 2.9 and 4.2 degrees of separation as shown in this chart.

The post aslo outlines how task of calculating degrees of separation in a network with hundreds of billions of edges and how it was accomplished.

Imagine a person with 100 friends. If each of his friends also has 100 friends, then the number of friends-of-friends will be 10,000. If each of those friends-of-friends also has 100 friends then the number of friends-of-friends-of-friends will be 1,000,000. Some of those friends may overlap, so we need to filter down to the unique connections. We're only two hops away and the number is already big. In reality this number grows even faster since most people on Facebook have more than 100 friends. We also need to do this computation 1.6 billion times; that is, for every person on Facebook.

The researchers used existing statistical techniques, in particular the Flajolet-Martin algorithm, which they put into layman's terms:

Imagine you have a set of people and you want to count how many are unique. First you assign each person a random integer; let's call it hash. Approximately 1/2 of the people will have an even hash: the binary representation of the hash will end with 0. Approximately 1/4 of the people will have a hash divisible by 4; that is, the binary representation ends with 00. In general, 1/2ⁿ people will have the binary representation of their hash end with n zeros. Now, we can reverse this and try to count how many different people we have by reading their hash values one by one. To do that, we track the biggest number of zeroes we've seen. Intuitively, if there were n zeroes, we can expect to have c*2ⁿ unique numbers, where c is some constant. For better accuracy we can do this computation multiple times with different hash values.

Remarking that the algorithm maps well to the problem, the researchers explain that they used it to find the biggest number of zeroes among all friends' hashes. Then using a bitwise OR operation on the hash, this process can be repeated recursively to estimate the number of unique friends-of-friends, and then friends-of-friends-of-friends. This computation was done on the entire Facebook friendship graph using the open source Apache Giraph package. 

This may all be true and Facebook makes us better connected, but it leaves the question of the quality of the connections open. Are Facebook friends anything like real friends? 

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info