[FIXED] How does facebook calculate mutual friends?

Issue

In your opinion, how does facebook calculate mutual friends?

Has it cached all mutual friends for each user? Or does it let MySQL calculate through a query each time it displays them? Or does it make a query to the database and then calculate from a list? Or is there another way?

Solution

I believe it is pre-computed and not done when you load the page. How? There are a couple of options to look at this problem. A common way is to look at the data as a graph, where each person is a vertex, and an edge defines a friendship. Iterating through each existing pair of persons, and finding 2 edges paths. The vertexes you went over, are the mutual friends. If you really want to get into it, I would suggest starting with learning about Graph Theory

When dealing with such an amount of data, using MySql and queries won't work. On small amounts of data, it will.

Answered By - Noam

Answer Checked By - Gilberto Lyons (PHPFixing Admin)