# Computing the “at least k friends in common” graph

Suppose we have the graph of a social network with symmetric connections (e.g. Facebook or LinkedIn). Suppose we would like to find all pairs of people who have at least k friends in common, in order to show them friend recommendations.

What is the most efficient way to do this? Does this problem have a name?

Apart from the naive solution (check all pairs - complexity $O(N^2 d)$ where $d$ is the average degree), the best I could come up with is the following:

• For every vertex, gather all pairs of its neighbors. The current vertex is one of their "friends in common".
• Count pairs that occur more than k times.

The complexity is something like $O(N d^2)$ which is strictly better.

It seems that there should be a more efficient solution (though obviously not better than $O(N^2)$ in the worst case), but I can't see any particular structure in the problem pointing toward it.

• That can be done with matrix multiplication, which will be faster for sufficiently large $d$. $\;$ – user12859 Jul 3 '15 at 23:42
• Indeed, I haven't thought of this as an (extremely sparse) matrix multiplication problem. – jkff Jul 4 '15 at 0:00