Fewer Degrees Of Separation With Facebook
Written by Janet Swift   
Saturday, 06 February 2016

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. 

 

fbgraph

 

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.

degofsep

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/2n 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*2n 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? 

fbgraph

More Information

Three and a half degrees of separation

Related Articles

Six Degrees Of Separation Is New

 

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, FacebookGoogle+ or Linkedin.

 

Banner


Google Comics Factory Makes ML Easy
06/10/2019

A comic strip approach to machine learning? Could it possibly work? The hero is a cat, so of course it can.



ReduKtor - Auto Debug For Kotlin
18/09/2019

No, this is not an AI approach but a good old down to earth engineering approach to isolating bugs. It's a technique that you could well apply manually, but as an automatic tool - even better.


More News

 

graphics

 



 

Comments




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

Last Updated ( Wednesday, 21 March 2018 )