This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 47

Facebook degrees of separation

Due: February 23
Points: 3

Facebook recently announced the results of a huge computation analyzing the friend relationships between all its users, and stated that on average each Facebook user is less than 3 degrees separated from every other user.

Read their announcement here.

The article discusses the actual algorithm they used to estimate the big numbers involved in the computation. Look up at least one other source for this algorithm, and then explain briefly, with a small example, what the Flajolet-Martin algorithm does and how it works.