7
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.