Facebook's Three and a Half Degree of Separation

Do you know that you can connect to anyone in this world with only six people in between you,No? Well its a proven theory named as Six degrees of Separation.

Now, Do you know in Facebook's research it has been found that the six degrees has been shrunk up to only Three and a half degree separation.

From Facebook

So now what's this Three and a half degree separation?

Facebook is a vast interconnected network of people where you can reach out to anyone you want. In the latest research of Facebook which has happened in earlier this year, they have proved that any two people in this world can be connected by only 3 and a half people away from you.

You eventually want to connect to any person in this world you can possibly be connected to him on Facebook by 3-4 friend-of-friend connection.

From Facebook

 Estimated average degrees of separation between all people on Facebook. The average person is connected to every other person by an average of 3.57 steps. The majority of people have an average between 3 and 4 steps.

Most of the people are having3-4 friends-of-friends connection to everyone on the Facebook.
If you really want to know that how Facebook have worked to accomplish this task then read ahead. Its a very complex algorithm and very to solve

How do they Calculate it?

It is not an easy task to calculate the degrees of separation especially for a giants like Facebook where billions of billions of people are interconnected.

Suppose you have 100 friends on Facebook each of which are having 100 friends on their list so it makes total of 10,000. Now think each of those are also having 100 friends so the count increases to 1,000,000. Now in this many can be overlapped so that need to removed.
This task cannot be done by a single person. In addition this since in real life this can take a speed since single person can have more than 100s of friends and also this has to be done for 1.6billion times.(example taken from Facebook).
For this Facebook relies on an algorithm which is designed by Kang and 8 others at Facebook for determining the hop count distance from the source to the destination.

This algorithm has a base structure of Flajolet-Martin algorithm.

Flajolet-Martin algorithm - How it works?

Imagine you have set of people and you wanted a count of all the unique members in them. First assign a random number to each person, calling it as hash. Approximately half of the people will be having even hash, binary representation of the hash will end with 0. Approximately 1/4 of the people will have a hash divisible by 4;that us, the binary representation ends with 00. In general , 1/2n people will have thew 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 zeros we have seen Intuitively. If there were n zeros, we can expect set to have c*2n unique numbers, where c is some constant. For better accuracy we can do this computation multiple times with different has values. (from Facebook)

Here we just found the biggest number of zeros in friends now for the unique friends and unique friends-of-friends this process has to run recursively for the estimation. 

So friends in conclusion the world is more connected to everyone more than you think.