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.
Computing the at least k friends in common graph
algorithms;graph theory;graphs;social networks;network analysis