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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.