Friday, February 05, 2016

3.37 Degrees of Separation

This is pretty interesting: Facebook has a tool that estimates the average number of intermediate people needed to link you, via the shortest path, to anyone else on Facebook. Mine is 3.37, which means the average path length (number of links) to me is 4.37, or that the average number of people in a shortest chain connecting others with me (including me and the person at the end) is 5.37.

What's yours?

An interesting aspect of this is that they use the Flajolet-Martin algorithm to estimate the path length. The paper of Flajolet-Martin deals with a certain correction factor φ, which is defined as follows: φ = 2 eγ α-1, where γ = 0.57721... is Euler's constant and α is the constant Πn ≥ 1 (2n/(2n+1))(-1)t(n), where t(n) is the Thue-Morse sequence, the sequence that counts the parity of the number of 1's in the binary expansion of n.

The Thue-Morse sequence has long been a favorite of mine, and Allouche and I wrote a survey paper about it some time ago, where we mentioned the Flajolet-Martin formula. The Thue-Morse sequence comes up in many different areas of mathematics and computer science. And we also wrote a paper about a constant very similar to α: it is Πn ≥ 0 ((2n+1)/(2n+2))(-1)t(n). Believe it or not, it is possible to evaluate this constant in closed form: it is equal to 2 !

By contrast, nobody knows a similar simple evaluation for α. In fact, I have offered $50 for a proof that α is irrational or transcendental.


Laurence A. Moran said...

Mine is 3.16. How sensitive is this to the number of Friends you have? It doesn't seem to be a big factor as long as you have several Friends.

If I were to set up three Facebook accounts (A, B, and C) where C's only Friend is B and B's only Friend is A then you can't link to C without going through 2 degrees of separation, right? Wouldn't this screw up the results posted on the website?

Jeffrey Shallit said...

Why do you think the weird possibility that you envision, which probably never happens, would "screw up" the results?

Anyway, if you read the link, you will see that they are not computing the average path length explicitly, but rather estimating it using a certain probabilistic counting technique. It is not guaranteed to be perfectly accurate.

Laurence A. Moran said...

Maybe I didn't think this through. The "average" would only be affected if I created several million such groups, right?

Do you know the answer to my first question?

Jeffrey Shallit said...

Yes to the first question.

Adding more friends will improve your average if your friends are 'well-connected'; otherwise it won't. So it doesn't directly depend on the number of friends, just their connectedness.

MathMac said...


Paul C. Anagnostopoulos said...

Mine is 3.2.

~~ Paul

George said...

I'm 3.46, average. I've only been on FB for a few months.