Skip to main content

Posts

Showing posts from December, 2011

The facebook graph

Putting "six degrees of separation" to the test with graph theory on a very large scale, Facebook analyses the connections between 10% of the worlds population.
Original paper: http://arxiv.org/abs/1111.4503

As one would expect the network is nearly fully connected, with 99.91% of the nodes belonging to a single connected component. The largest subgraph not connected to the major graph consists of about 2000 users.

The degrees of separation for any two facebook users is closer to 4 than 6. In 92% of all pairs of users on facebook; a friend of your friend knows a friend of my friend.

The graph is inherently sparse, duein part to our social ineptness at connecting with any significant fraction of the global population and also by facebook limiting the maximum number of friends to 5000. The median number of friends (degree) globally was 99.

The graph is also highly clustered - "for a median user, 14% of all their friend pairs are themselves friends", and interestingly this…